|
|
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.
|
|
11
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|