A245667 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,5

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

LINKS

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

EXAMPLE

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:

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;

...

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]<i, i, l[j])), j=1..nops(l))]), i=1..l[-1]))

end:

A:= (n, k)-> `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]]<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 *)

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.

Sequence in context: A202995 A191578 A288385 * A067176 A249480 A271704

Adjacent sequences: A245664 A245665 A245666 * A245668 A245669 A245670

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jul 28 2014

STATUS

approved