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 (0<=k<=n).

1, 0, 1, 0, 1, 1, 0, 0, 4, 1, 0, 0, 4, 9, 1, 0, 0, 0, 25, 16, 1, 0, 0, 0, 25, 81, 25, 1, 0, 0, 0, 0, 196, 196, 36, 1, 0, 0, 0, 0, 196, 784, 400, 49, 1, 0, 0, 0, 0, 0, 1764, 2304, 729, 64, 1, 0, 0, 0, 0, 0, 1764, 8100, 5625, 1225, 81, 1, 0, 0, 0, 0, 0, 0, 17424, 27225, 12100, 1936, 100, 1, 0, 0, 0, 0, 0, 0, 17424, 88209, 75625, 23716, 2916, 121, 1

Offset: 0

Author

Emeric Deutsch, Dec 22 2006

Keywords

• nonn
• tabl
• easy

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

Examples

			T(4,2) = 4 because we have 2143, 3142, 2413 and 3412.
Triangle starts:
  1;
  0, 1;
  0, 1, 1;
  0, 0, 4,  1;
  0, 0, 4,  9,  1;
  0, 0, 0, 25, 16,  1;
  0, 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.
		

Links

• Alois P. Heinz, Rows n = 0..150, flattened
• 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.

Crossrefs

Cf. A000108, A001246, A001700, A071799, A132889.

T(n+1,n) gives A000290.

Programs

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 0 to 13 do seq(T(n,k),k=0..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 *)

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

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.]

Sum_{k=n+1..2*n+1} (-1)^(n+k+1) * T(2*n+1,k) = binomial(2*n+1,n) = A001700(n). - Peter Bala, Nov 03 2024

From Alois P. Heinz, Nov 04 2024: (Start)

Sum_{k=0..n} k * T(n,k) = A132889(n).

2 * Sum_{k=0..2n} (2n-k) * T(2n,k) = A071799(n) for n>=1. (End)

Extensions

Row and column 0 inserted by Alois P. Heinz, Nov 04 2024