A242464 Number A(n,k) of n-length words w over a k-ary alphabet {a_1,...,a_k} such that w contains never more than j consecutive letters a_j (for 1<=j<=k); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 3, 0, 0, 1, 4, 8, 4, 0, 0, 1, 5, 15, 21, 5, 0, 0, 1, 6, 24, 56, 54, 7, 0, 0, 1, 7, 35, 115, 208, 140, 9, 0, 0, 1, 8, 48, 204, 550, 773, 362, 12, 0, 0, 1, 9, 63, 329, 1188, 2631, 2872, 937, 16, 0, 0, 1, 10, 80, 496, 2254, 6919, 12584, 10672, 2425, 21, 0, 0

Offset

0,8

Comments

The sequence of column k satisfies a linear recurrence with constant coefficients of order A015614(k+1) for k>1.

Links

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

Formula

G.f. of column k: 1/(1-Sum_{i=1..k} v(i)/(1+v(i))) with v(i) = (x-x^(i+1))/(1-x).

Example

A(0,k) = 1 for all k: the empty word.
A(1,5) = 5: [1], [2], [3], [4], [5].
A(2,4) = 15: [1,2], [1,3], [1,4], [2,1], [2,2], [2,3], [2,4], [3,1], [3,2], [3,3], [3,4], [4,1], [4,2], [4,3], [4,4].
A(3,3) = 21: [1,2,1], [1,2,2], [1,2,3], [1,3,1], [1,3,2], [1,3,3], [2,1,2], [2,1,3], [2,2,1], [2,2,3], [2,3,1], [2,3,2], [2,3,3], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3], [3,3,1], [3,3,2], [3,3,3].
A(4,2) = 5: [1,2,1,2], [1,2,2,1], [2,1,2,1], [2,1,2,2], [2,2,1,2].
A(n,1) = 0 for n>1.
A(n,0) = 0 for n>0.
Square array A(n,k) begins:
  1, 1,  1,   1,     1,     1,      1,      1, ...
  0, 1,  2,   3,     4,     5,      6,      7, ...
  0, 0,  3,   8,    15,    24,     35,     48, ...
  0, 0,  4,  21,    56,   115,    204,    329, ...
  0, 0,  5,  54,   208,   550,   1188,   2254, ...
  0, 0,  7, 140,   773,  2631,   6919,  15443, ...
  0, 0,  9, 362,  2872, 12584,  40295, 105804, ...
  0, 0, 12, 937, 10672, 60191, 234672, 724892, ...

Maple

b:= proc(n, k, c, t) option remember;
      `if`(n=0, 1, add(`if`(c=t and j=c, 0,
       b(n-1, k, j, 1+`if`(j=c, t, 0))), j=1..k))
    end:
A:= (n, k)-> b(n, k, 0$2):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

nn=10; Transpose[Map[PadRight[#, nn]&, Table[CoefficientList[Series[1/(1-Sum[v[i]/(1+v[i])/.v[i]->(z-z^(i+1))/(1-z), {i, 1, n}]), {z, 0, nn}], z], {n, 0, nn}]]]//Grid
(* Second program: *)
b[n_, k_, c_, t_] := b[n, k, c, t] = If[n == 0, 1, Sum[If[c == t && j == c, 0, b[n - 1, k, j, 1 + If[j == c, t, 0]]], {j, 1, k}]];
A[n_, k_] := b[n, k, 0, 0];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 28 2020, after Maple *)

Crossrefs

Columns k=0-10 give: A000007, A019590(n+1), A164001(n+1), A242452, A242495, A242509, A242629, A242630, A242631, A242632, A242633.

Rows n=0-2 give: A000012, A001477, A005563(k-1) for k>0.

Main diagonal gives A242635.

Sequence in context: A309021 A307968 A338501 * A273185 A375467 A373183

Adjacent sequences: A242461 A242462 A242463 * A242465 A242466 A242467

Keyword

nonn,tabl

Author

Geoffrey Critzer and Alois P. Heinz, May 15 2014

Status

approved