A245667 Number T(n,k) of sequences in {1,...,n}^n with longest increasing subsequence of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 3, 1, 0, 10, 16, 1, 0, 35, 175, 45, 1, 0, 126, 1771, 1131, 96, 1, 0, 462, 17906, 23611, 4501, 175, 1, 0, 1716, 184920, 461154, 161876, 13588, 288, 1, 0, 6435, 1958979, 8837823, 5179791, 759501, 34245, 441, 1, 0, 24310, 21253375, 169844455, 157279903, 36156355, 2785525, 75925, 640, 1

Offset: 0

Author

Alois P. Heinz, Jul 28 2014

Keywords

• nonn
• tabl

Comments

Sum_{k=0..1} T(n,k) = A088218(n).

Sum_{k=0..2} T(n,k) = A239295(n).

Sum_{k=0..3} T(n,k) = A239299(n).

Sum_{k=1..n} k * T(n,k) = A275576(n).

Examples

			T(3,1) = 10: [1,1,1], [2,1,1], [2,2,1], [2,2,2], [3,1,1], [3,2,1], [3,2,2], [3,3,1], [3,3,2], [3,3,3].
T(3,3) = 1: [1,2,3].
Triangle T(n,k) begins:
  1;
  0,    1;
  0,    3,      1;
  0,   10,     16,      1;
  0,   35,    175,     45,      1;
  0,  126,   1771,   1131,     96,     1;
  0,  462,  17906,  23611,   4501,   175,   1;
  0, 1716, 184920, 461154, 161876, 13588, 288,  1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..18, flattened

Crossrefs

Columns k=0-10 give: A000007, A088218 or A001700(n-1) for n>0, A268869, A268870, A268871, A268872, A268873, A268874, A268875, A268876, A268877.

Main diagonal gives A000012.

T(n,n-1) gives A152618(n) for n>0.

T(n,n-2) gives A268936(n).

T(2n,n) gives A268949(n).

Row sums give A000312.

Cf. A047874, A239295, A239299, A275576.

Programs

Maple

b:= proc(n, l) option remember; `if`(n=0, 1, add(b(n-1, [seq(min(l[j],
      `if`(j=1 or l[j-1] `if`(k=0, `if`(n=0, 1, 0), b(n, [n$k])):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..9);

Mathematica

b[n_, l_List] := b[n, l] = If[n == 0, 1, Sum[b[n-1, Table[Min[l[[j]], If[j == 1 || l[[j-1]]Jean-François Alcover, Feb 04 2015, after Alois P. Heinz *)