|
| |
|
|
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).
|
|
2
|
|
|
|
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;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
The row sums are the Catalan numbers (A000108). T(2n,n)=(C(n))^2=A001246(n), where the C(n) are the Catalan numbers.
Also T(n,k) = Number of Dyck paths of semilength n with midpoint height = 2*k-n. David Scambler (dscambler AT bmm.com), Nov 25 2010
|
|
|
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.
|
|
|
LINKS
|
Table of n, a(n) for n=1..73.
|
|
|
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. [N.B.: floor((n+1)/2) <= k <=> n/2 <= k.]
|
|
|
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;
T(4,2)=4 because 2*2-4 = zero and Dyck 4-paths with midpoint height of zero are UUDDUUDD, UUDDUDUD, UDUDUUDD and UDUDUDUD.
|
|
|
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
|
|
|
PROG
|
(PARI) T(n, k)=if(n<=2*k, (2*k-n+1)*binomial(n+1, n-k)\(n+1))^2 \\ [M. F. Hasler, Nov 24 2010]
|
|
|
CROSSREFS
|
Cf. A000108, A001246.
Sequence in context: A122388 A094918 A110146 * A108944 A117377 A046784
Adjacent sequences: A126214 A126215 A126216 * A126218 A126219 A126220
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Emeric Deutsch, Dec 22 2006
|
|
|
STATUS
|
approved
|
| |
|
|
