|
Search: id:A126217
|
|
|
| A126217 |
|
Triangle read by rows: T(n,k) is the number of 321-avoiding permutations of {1,2,...,n} having longest increasing subsequence of length k (1<=k<=n). |
|
+0
3
|
|
| 1, 1, 1, 0, 4, 1, 0, 4, 9, 1, 0, 0, 25, 16, 1, 0, 0, 25, 81, 25, 1, 0, 0, 0, 196, 196, 36, 1, 0, 0, 0, 196, 784, 400, 49, 1, 0, 0, 0, 0, 1764, 2304, 729, 64, 1, 0, 0, 0, 0, 1764, 8100, 5625, 1225, 81, 1, 0, 0, 0, 0, 0, 17424, 27225, 12100, 1936, 100, 1, 0, 0, 0, 0, 0, 17424, 88209
(list; table; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
The row sums are the Catalan numbers (A000108). T(2n,n)=(C(n))^2=A001246(n), where the C(n) are the Catalan numbers.
|
|
REFERENCES
|
E. Deutsch, A. J. Hildebrand, and H. S. Wilf, Longest increasing subsequences in pattern-restricted permutations, The Electronic Journal of Combinatorics, 9(2), 2003, #R12.
|
|
FORMULA
|
T(n,k)=[(2k-n+1)C(n+1,n-k)/(n+1)]^2 if floor((n+1)/2)<=k<=n; T(n,k)=0 otherwise.
|
|
EXAMPLE
|
T(4,2)=4 because we have 2143, 3142,2413, and 3412.
Triangle starts:
1;
1,1;
0,4,1;
0,4,9,1;
0,0,25,16,1;
0,0,25,81,25,1;
|
|
MAPLE
|
T:=proc(n, k) if floor((n+1)/2)<=k and k<=n then ((2*k-n+1)*binomial(n+1, k+1)/(n+1))^2 else 0 fi end: for n from 1 to 13 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form
|
|
CROSSREFS
|
Cf. A000108, A001246.
Sequence in context: A122388 A094918 A110146 this_sequence A108944 A117377 A046784
Adjacent sequences: A126214 A126215 A126216 this_sequence A126218 A126219 A126220
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Dec 22 2006
|
|
|
Search completed in 0.002 seconds
|
