login
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
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.
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
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved