login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 16
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:

  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;

  ...

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 12:13 EST 2022. Contains 350477 sequences. (Running on oeis4.)