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

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, 156, 96, 30, 6, 0, 0, 7, 188, 519, 436, 175, 42, 7, 0, 0, 8, 404, 1680, 1916, 980, 288, 56, 8, 0, 0, 9, 856, 5349, 8232, 5345, 1914, 441, 72, 9, 0

Offset

0,8

Links

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

Project Euler, Problem 427: n-sequences

Example

A(4,1) = 4 = 1+1+1+1: [1], [2], [3], [4].
A(1,4) = 4: [1,1,1,1].
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].
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].
Square array A(n,k) begins:
  0, 0,  0,   0,    0,     0,      0,       0, ...
  0, 1,  2,   3,    4,     5,      6,       7, ...
  0, 2,  6,  16,   38,    86,    188,     404, ...
  0, 3, 12,  45,  156,   519,   1680,    5349, ...
  0, 4, 20,  96,  436,  1916,   8232,   34840, ...
  0, 5, 30, 175,  980,  5345,  28610,  151115, ...
  0, 6, 42, 288, 1914, 12450,  79716,  504492, ...
  0, 7, 56, 441, 3388, 25571, 190428, 1403689, ...

Maple

b:= proc(n, m, s, i) option remember; `if`(m>i or s>m, 0,
      `if`(i=0, 1, `if`(i=1, n, `if`(s=1, (n-1)*add(
         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)))))
    end:
A:= (n, k)-> add(m*add(b(n, m, s, k), s=1..m), m=1..k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

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

Crossrefs

Columns k=0-3 give: A000004, A001477, A002378, A152618(n+1).

Rows n=0-2 give: A000004, A001477, 2*A102712.

Main diagonal gives: A228194.

Cf. A228275.

Sequence in context: A185651 A265080 A228275 * A341317 A101164 A229079

Adjacent sequences: A228247 A228248 A228249 * A228251 A228252 A228253

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 18 2013

Status

approved