|
%I #38 Dec 28 2020 04:24:10
%S 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,
%T 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,
%U 63,329,1188,2631,2872,937,16,0,0,1,10,80,496,2254,6919,12584,10672,2425,21,0,0
%N 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.
%C The sequence of column k satisfies a linear recurrence with constant coefficients of order A015614(k+1) for k>1.
%H Alois P. Heinz, <a href="/A242464/b242464.txt">Antidiagonals n = 0..120, flattened</a>
%F 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).
%e A(0,k) = 1 for all k: the empty word.
%e A(1,5) = 5: [1], [2], [3], [4], [5].
%e 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].
%e 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].
%e A(4,2) = 5: [1,2,1,2], [1,2,2,1], [2,1,2,1], [2,1,2,2], [2,2,1,2].
%e A(n,1) = 0 for n>1.
%e A(n,0) = 0 for n>0.
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 2, 3, 4, 5, 6, 7, ...
%e 0, 0, 3, 8, 15, 24, 35, 48, ...
%e 0, 0, 4, 21, 56, 115, 204, 329, ...
%e 0, 0, 5, 54, 208, 550, 1188, 2254, ...
%e 0, 0, 7, 140, 773, 2631, 6919, 15443, ...
%e 0, 0, 9, 362, 2872, 12584, 40295, 105804, ...
%e 0, 0, 12, 937, 10672, 60191, 234672, 724892, ...
%p b:= proc(n, k, c, t) option remember;
%p `if`(n=0, 1, add(`if`(c=t and j=c, 0,
%p b(n-1, k, j, 1+`if`(j=c, t, 0))), j=1..k))
%p end:
%p A:= (n, k)-> b(n, k, 0$2):
%p seq(seq(A(n, d-n), n=0..d), d=0..12);
%t 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
%t (* Second program: *)
%t 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}]];
%t A[n_, k_] := b[n, k, 0, 0];
%t Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 28 2020, after Maple *)
%Y Columns k=0-10 give: A000007, A019590(n+1), A164001(n+1), A242452, A242495, A242509, A242629, A242630, A242631, A242632, A242633.
%Y Rows n=0-2 give: A000012, A001477, A005563(k-1) for k>0.
%Y Main diagonal gives A242635.
%K nonn,tabl
%O 0,8
%A _Geoffrey Critzer_ and _Alois P. Heinz_, May 15 2014
|
