login
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.
16

%I #36 Nov 02 2018 22:51:42

%S 1,0,1,0,3,1,0,10,16,1,0,35,175,45,1,0,126,1771,1131,96,1,0,462,17906,

%T 23611,4501,175,1,0,1716,184920,461154,161876,13588,288,1,0,6435,

%U 1958979,8837823,5179791,759501,34245,441,1,0,24310,21253375,169844455,157279903,36156355,2785525,75925,640,1

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

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

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

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

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

%H Alois P. Heinz, <a href="/A245667/b245667.txt">Rows n = 0..18, flattened</a>

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

%e T(3,3) = 1: [1,2,3].

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 3, 1;

%e 0, 10, 16, 1;

%e 0, 35, 175, 45, 1;

%e 0, 126, 1771, 1131, 96, 1;

%e 0, 462, 17906, 23611, 4501, 175, 1;

%e 0, 1716, 184920, 461154, 161876, 13588, 288, 1;

%e ...

%p b:= proc(n, l) option remember; `if`(n=0, 1, add(b(n-1, [seq(min(l[j],

%p `if`(j=1 or l[j-1]<i, i, l[j])), j=1..nops(l))]), i=1..l[-1]))

%p end:

%p A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), b(n, [n$k])):

%p T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):

%p seq(seq(T(n, k), k=0..n), n=0..9);

%t 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]]<i, i, l[[j]]]], {j, 1, Length[l]}]], {i, 1, l[[-1]]}]]; A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Array[n&, k]]]; T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 9}] // Flatten (* _Jean-François Alcover_, Feb 04 2015, after _Alois P. Heinz_ *)

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

%Y Main diagonal gives A000012.

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

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

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

%Y Row sums give A000312.

%Y Cf. A047874, A239295, A239299, A275576.

%K nonn,tabl

%O 0,5

%A _Alois P. Heinz_, Jul 28 2014