|
%I #24 Sep 21 2018 22:30:05
%S 0,0,0,0,1,0,0,2,2,0,0,3,6,3,0,0,4,16,12,4,0,0,5,38,45,20,5,0,0,6,86,
%T 156,96,30,6,0,0,7,188,519,436,175,42,7,0,0,8,404,1680,1916,980,288,
%U 56,8,0,0,9,856,5349,8232,5345,1914,441,72,9,0
%N Total sum A(n,k) of lengths of longest contiguous subsequences with the same value over all s in {1,...,n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%H Alois P. Heinz, <a href="/A228250/b228250.txt">Antidiagonals n = 0..140, flattened</a>
%H Project Euler, <a href="https://projecteuler.net/problem=427">Problem 427: n-sequences</a>
%e A(4,1) = 4 = 1+1+1+1: [1], [2], [3], [4].
%e A(1,4) = 4: [1,1,1,1].
%e A(3,2) = 12 = 2+1+1+1+2+1+1+1+2: [1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3].
%e A(2,3) = 16 = 3+2+1+2+2+1+2+3: [1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1], [2,2,2].
%e Square array A(n,k) begins:
%e 0, 0, 0, 0, 0, 0, 0, 0, ...
%e 0, 1, 2, 3, 4, 5, 6, 7, ...
%e 0, 2, 6, 16, 38, 86, 188, 404, ...
%e 0, 3, 12, 45, 156, 519, 1680, 5349, ...
%e 0, 4, 20, 96, 436, 1916, 8232, 34840, ...
%e 0, 5, 30, 175, 980, 5345, 28610, 151115, ...
%e 0, 6, 42, 288, 1914, 12450, 79716, 504492, ...
%e 0, 7, 56, 441, 3388, 25571, 190428, 1403689, ...
%p b:= proc(n, m, s, i) option remember; `if`(m>i or s>m, 0,
%p `if`(i=0, 1, `if`(i=1, n, `if`(s=1, (n-1)*add(
%p b(n, m, h, i-1), h=1..m), b(n, m, s-1, i-1)+
%p `if`(s=m, b(n, m-1, s-1, i-1), 0)))))
%p end:
%p A:= (n, k)-> add(m*add(b(n, m, s, k), s=1..m), m=1..k):
%p seq(seq(A(n, d-n), n=0..d), d=0..12);
%t b[n_, m_, s_, i_] := b[n, m, s, i] = If[m>i || s>m, 0, If[i == 0, 1, If[i == 1, n, If[s == 1, (n-1)*Sum[b[n, m, h, i-1], {h, 1, m}], b[n, m, s-1, i-1] + If[s == m, b[n, m-1, s-1, i-1], 0]]]]]; A[n_, k_] := Sum[m*Sum[b[n, m, s, k], {s, 1, m}], {m, 1, k}]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Jan 19 2015, after _Alois P. Heinz_ *)
%Y Columns k=0-3 give: A000004, A001477, A002378, A152618(n+1).
%Y Rows n=0-2 give: A000004, A001477, 2*A102712.
%Y Main diagonal gives: A228194.
%Y Cf. A228275.
%K nonn,tabl
%O 0,8
%A _Alois P. Heinz_, Aug 18 2013
|
