A275576 -id:A275576 - cp's OEIS frontend

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

Alois P. Heinz, Jul 28 2014

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

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

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

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.

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

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

A275577 Sums of lengths of longest (not necessarily strictly) increasing subsequences of all n^n length-n lists of integers from {1,2,...,n}.

Original entry on oeis.org

1, 7, 63, 716, 10050, 167707, 3246985, 71601112, 1772086842, 48644809445, 1466863148619, 48202848917302, 1714563272612502

Offset: 1

Jeffrey Shallit, Aug 02 2016

			For n = 2 there are 4 such sequences:  (1,1), (1,2), (2,1), and (2,2).
The corresponding lengths of longest (not necessarily strictly) increasing subsequences of these is 2, 2, 1, 2, so a(2) =7.

Cf. A003316, which computes the same thing for permutations.

Cf. A275576, which computes the same thing for strictly increasing subsequences.

a(8)-a(13) from Alois P. Heinz, Nov 02 2018

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica