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
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer and Alois P. Heinz, May 15 2014
STATUS
approved