

A126217


Triangle read by rows: T(n,k) is the number of 321avoiding 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*kn. David Scambler (dscambler AT bmm.com), Nov 25 2010


REFERENCES

E. Deutsch, A. J. Hildebrand and H. S. Wilf, Longest increasing subsequences in patternrestricted permutations, The Electronic Journal of Combinatorics, 9(2), 2003, #R12.


LINKS

Table of n, a(n) for n=1..73.


FORMULA

T(n,k)=[(2kn+1)C(n+1,nk)/(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*24 = zero and Dyck 4paths 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*kn+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*kn+1)*binomial(n+1, nk)\(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



