login
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).
3

%I #31 Nov 04 2024 17:12:31

%S 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,

%T 196,196,36,1,0,0,0,0,196,784,400,49,1,0,0,0,0,0,1764,2304,729,64,1,0,

%U 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

%N 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).

%C The row sums are the Catalan numbers (A000108). T(2n,n) = (C(n))^2 = A001246(n), where the C(n) are the Catalan numbers.

%C Also T(n,k) = Number of Dyck paths of semilength n with midpoint height = 2*k - n. _David Scambler_, Nov 25 2010

%H Alois P. Heinz, <a href="/A126217/b126217.txt">Rows n = 0..150, flattened</a>

%H E. Deutsch, A. J. Hildebrand and H. S. Wilf, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v9i2r12">Longest increasing subsequences in pattern-restricted permutations</a>, The Electronic Journal of Combinatorics, 9(2), 2003, #R12.

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

%F 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

%F From _Alois P. Heinz_, Nov 04 2024: (Start)

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

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

%e T(4,2) = 4 because we have 2143, 3142, 2413 and 3412.

%e Triangle starts:

%e 1;

%e 0, 1;

%e 0, 1, 1;

%e 0, 0, 4, 1;

%e 0, 0, 4, 9, 1;

%e 0, 0, 0, 25, 16, 1;

%e 0, 0, 0, 25, 81, 25, 1;

%e ...

%e T(4,2) = 4 because 2*2 - 4 = zero and Dyck 4-paths with midpoint height of zero are UUDDUUDD, UUDDUDUD, UDUDUUDD and UDUDUDUD.

%p 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

%t 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 *)

%o (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

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

%Y T(n+1,n) gives A000290.

%K nonn,tabl,easy,changed

%O 0,9

%A _Emeric Deutsch_, Dec 22 2006

%E Row and column 0 inserted by _Alois P. Heinz_, Nov 04 2024