login
Triangle of numbers T(n,k) = number of permutations of n things with longest increasing subsequence of length <=k (1<=k<=n).
5

%I #21 Jan 12 2024 14:13:18

%S 1,1,2,1,5,6,1,14,23,24,1,42,103,119,120,1,132,513,694,719,720,1,429,

%T 2761,4582,5003,5039,5040,1,1430,15767,33324,39429,40270,40319,40320,

%U 1,4862,94359,261808,344837,361302,362815,362879,362880,1,16796

%N Triangle of numbers T(n,k) = number of permutations of n things with longest increasing subsequence of length <=k (1<=k<=n).

%H Alois P. Heinz, <a href="/A047887/b047887.txt">Rows n = 1..45, flattened</a>

%H Ira M. Gessel, <a href="http://dx.doi.org/10.1016/0097-3165(90)90060-A">Symmetric functions and P-recursiveness</a>, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.

%e Triangle T(n,k) begins:

%e 1;

%e 1, 2;

%e 1, 5, 6;

%e 1, 14, 23, 24;

%e 1, 42, 103, 119, 120;

%e 1, 132, 513, 694, 719, 720;

%e 1, 429, 2761, 4582, 5003, 5039, 5040;

%e ...

%t h[l_] := Module[{n = Length[l]}, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]];

%t g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Array[1 &, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i - 1, Join[l, Array[i &, j]]], {j, 0, n/i}]]];

%t T[n_] := Table[g[n - k, Min[n - k, k], {k}], {k, 1, n}] // Accumulate;

%t Table[T[n], {n, 1, 10}] // Flatten (* _Jean-François Alcover_, Mar 24 2016, after _Alois P. Heinz_ *)

%Y Rows are partial sums of A047874.

%Y Cf. A047888, A214015.

%K nonn,easy,nice,tabl

%O 1,3

%A Eric Rains (rains(AT)caltech.edu), _N. J. A. Sloane_

%E More terms from _Naohiro Nomoto_, Mar 01 2002