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

1, 2, 2, 12, 12, 3, 108, 120, 24, 4, 1280, 1520, 280, 40, 5, 18750, 23400, 3930, 510, 60, 6, 326592, 423360, 65016, 7644, 840, 84, 7, 6588344, 8800008, 1241464, 132552, 13440, 1288, 112, 8, 150994944, 206622720, 26911296, 2622528, 244944, 22032, 1872, 144, 9

Offset: 1

Author

Walt Rorie-Baety, Aug 15 2013

Keywords

• nonn
• tabl

Examples

			T(1,1) =  1: [1].
T(2,1) =  2: [1,2], [2,1].
T(2,2) =  2: [1,1], [2,2].
T(3,1) = 12: [1,2,1], [1,2,3], [1,3,1], [1,3,2], [2,1,2], [2,1,3], [2,3,1], [2,3,2], [3,1,2], [3,1,3], [3,2,1], [3,2,3].
T(3,2) = 12: [1,1,2], [1,1,3], [1,2,2], [1,3,3], [2,1,1], [2,2,1], [2,2,3], [2,3,3], [3,1,1], [3,2,2], [3,3,1], [3,3,2].
T(3,3) =  3: [1,1,1], [2,2,2], [3,3,3].
Triangle T(n,k) begins:
.       1;
.       2,       2;
.      12,      12,       3;
.     108,     120,      24,      4;
.    1280,    1520,     280,     40,     5;
.   18750,   23400,    3930,    510,    60,    6;
.  326592,  423360,   65016,   7644,   840,   84,   7;
. 6588344, 8800008, 1241464, 132552, 13440, 1288, 112,  8;
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Project Euler, Problem 427: n-sequences

Crossrefs

Row sums give: A000312.

Column k=1 gives: A055897.

Main diagonal gives: A000027.

Lower diagonal gives: 2*A180291.

Cf. A228194, A228273, A228617.

Programs

Maple

T:= proc(n) option remember; local b; b:=
      proc(m, s, i) option remember; `if`(m>i or s>m, 0,
        `if`(i=1, n, `if`(s=1, (n-1)*add(b(m, h, i-1), h=1..m),
         b(m, s-1, i-1) +`if`(s=m, b(m-1, s-1, i-1), 0))))
      end; forget(b);
      seq(add(b(k, s, n), s=1..k), k=1..n)
    end:
seq(T(n), n=1..12);  # Alois P. Heinz, Aug 18 2013

Mathematica

T[n_] := T[n] = Module[{b}, b[m_, s_, i_] := b[m, s, i] = If[m>i || s>m, 0, If[i == 1, n, If[s == 1, (n-1)*Sum[b[m, h, i-1], {h, 1, m}], b[m, s-1, i-1] + If[s == m, b[m-1, s-1, i-1], 0]]]]; Table[Sum[b[k, s, n], {s, 1, k}], {k, 1, n}]]; Table[ T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Alois P. Heinz *)

Formula

Sum_{k=1..n} k * T(n,k) = A228194(n). - Alois P. Heinz, Dec 23 2020