A228273 T(n,k) is the number of s in {1,...,n}^n having longest ending contiguous subsequence with the same value of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 2, 2, 0, 18, 6, 3, 0, 192, 48, 12, 4, 0, 2500, 500, 100, 20, 5, 0, 38880, 6480, 1080, 180, 30, 6, 0, 705894, 100842, 14406, 2058, 294, 42, 7, 0, 14680064, 1835008, 229376, 28672, 3584, 448, 56, 8, 0, 344373768, 38263752, 4251528, 472392, 52488, 5832, 648, 72, 9

Offset

0,5

Links

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

Formula

T(0,0) = 1, else T(n,k) = 0 for k<1 or k>n, else T(n,n) = n, else T(n,k) = (n-1)*n^(n-k).

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

Sum_{k=0..n} k*T(n,k) = A031972(n).

Example

T(0,0) = 1: [].
T(1,1) = 1: [1].
T(2,1) = 2: [1,2], [2,1].
T(2,2) = 2: [1,1], [2,2].
T(3,1) = 18: [1,1,2], [1,1,3], [1,2,1], [1,2,3], [1,3,1], [1,3,2], [2,1,2], [2,1,3], [2,2,1], [2,2,3], [2,3,1], [2,3,2], [3,1,2], [3,1,3], [3,2,1], [3,2,3], [3,3,1], [3,3,2].
T(3,2) = 6: [1,2,2], [1,3,3], [2,1,1], [2,3,3], [3,1,1], [3,2,2].
T(3,3) = 3: [1,1,1], [2,2,2], [3,3,3].
Triangle T(n,k) begins:
  1;
  0,        1;
  0,        2,       2;
  0,       18,       6,      3;
  0,      192,      48,     12,     4;
  0,     2500,     500,    100,    20,    5;
  0,    38880,    6480,   1080,   180,   30,   6;
  0,   705894,  100842,  14406,  2058,  294,  42,  7;
  0, 14680064, 1835008, 229376, 28672, 3584, 448, 56,  8;

Maple

T:= (n, k)-> `if`(n=0 and k=0, 1, `if`(k<1 or k>n, 0,
             `if`(k=n, n, (n-1)*n^(n-k)))):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

f[0, 0]=1;
f[n_, k_]:=Which[1<=k<=n-1, n^(n-k)*(n-1), k<1, 0, k==n, n, k>n, 0];
Table[Table[f[n, k], {k, 0, n}], {n, 0, 10}]//Grid (* Geoffrey Critzer, May 19 2014 *)

Crossrefs

Row sums give: A000312.

Columns k=0-4 give: A000007, A066274(n) = 2*A081131(n) for n>1, A053506(n) for n>2, A055865(n-1) = A085389(n-1) for n>3, A085390(n-1) for n>4.

Main diagonal gives: A028310.

Lower diagonals include (offsets may differ): A002378, A045991, A085537, A085538, A085539.

Cf. A228154, A228617.

Sequence in context: A091466 A134085 A151339 * A069521 A245687 A228617

Adjacent sequences: A228270 A228271 A228272 * A228274 A228275 A228276

Keyword

nonn,tabl,easy

Author

Alois P. Heinz, Aug 19 2013

Status

approved