login
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.
4

%I #42 Dec 23 2020 10:05:53

%S 1,2,2,12,12,3,108,120,24,4,1280,1520,280,40,5,18750,23400,3930,510,

%T 60,6,326592,423360,65016,7644,840,84,7,6588344,8800008,1241464,

%U 132552,13440,1288,112,8,150994944,206622720,26911296,2622528,244944,22032,1872,144,9

%N 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.

%H Alois P. Heinz, <a href="/A228154/b228154.txt">Rows n = 1..141, flattened</a>

%H Project Euler, <a href="http://projecteuler.net/problem=427">Problem 427: n-sequences</a>

%F Sum_{k=1..n} k * T(n,k) = A228194(n). - _Alois P. Heinz_, Dec 23 2020

%e T(1,1) = 1: [1].

%e T(2,1) = 2: [1,2], [2,1].

%e T(2,2) = 2: [1,1], [2,2].

%e 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].

%e 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].

%e T(3,3) = 3: [1,1,1], [2,2,2], [3,3,3].

%e Triangle T(n,k) begins:

%e . 1;

%e . 2, 2;

%e . 12, 12, 3;

%e . 108, 120, 24, 4;

%e . 1280, 1520, 280, 40, 5;

%e . 18750, 23400, 3930, 510, 60, 6;

%e . 326592, 423360, 65016, 7644, 840, 84, 7;

%e . 6588344, 8800008, 1241464, 132552, 13440, 1288, 112, 8;

%p T:= proc(n) option remember; local b; b:=

%p proc(m, s, i) option remember; `if`(m>i or s>m, 0,

%p `if`(i=1, n, `if`(s=1, (n-1)*add(b(m, h, i-1), h=1..m),

%p b(m, s-1, i-1) +`if`(s=m, b(m-1, s-1, i-1), 0))))

%p end; forget(b);

%p seq(add(b(k, s, n), s=1..k), k=1..n)

%p end:

%p seq(T(n), n=1..12); # _Alois P. Heinz_, Aug 18 2013

%t 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_ *)

%Y Row sums give: A000312.

%Y Column k=1 gives: A055897.

%Y Main diagonal gives: A000027.

%Y Lower diagonal gives: 2*A180291.

%Y Cf. A228194, A228273, A228617.

%K nonn,tabl

%O 1,2

%A _Walt Rorie-Baety_, Aug 15 2013