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

1, 1, 2, 1, 5, 6, 1, 14, 23, 24, 1, 42, 103, 119, 120, 1, 132, 513, 694, 719, 720, 1, 429, 2761, 4582, 5003, 5039, 5040, 1, 1430, 15767, 33324, 39429, 40270, 40319, 40320, 1, 4862, 94359, 261808, 344837, 361302, 362815, 362879, 362880, 1, 16796

Offset: 1

Author

Eric Rains (rains(AT)caltech.edu), N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• tabl

Examples

			Triangle T(n,k) begins:
  1;
  1,   2;
  1,   5,    6;
  1,  14,   23,   24;
  1,  42,  103,  119,  120;
  1, 132,  513,  694,  719,  720;
  1, 429, 2761, 4582, 5003, 5039, 5040;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..45, flattened
• Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A 53 (1990), no. 2, 257-285.

Crossrefs

Rows are partial sums of A047874.

Cf. A047888, A214015.

Programs

Mathematica

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}]];
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[n_] := Table[g[n - k, Min[n - k, k], {k}], {k, 1, n}] // Accumulate;
Table[T[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 24 2016, after Alois P. Heinz *)

Extensions

More terms from Naohiro Nomoto, Mar 01 2002