login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, Nov 25 2010
LINKS
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) = ((2*k - 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
MATHEMATICA
t[n_, k_] := If[n<=2k, ((2k-n+1)*Binomial[n+1, n-k]/(n+1))^2, 0]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Amiram Eldar, Nov 26 2018 *)
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
Sequence in context: A122388 A094918 A110146 * A303499 A108944 A117377
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Dec 22 2006
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:34 EDT 2024. Contains 370952 sequences. (Running on oeis4.)