cp's OEIS Frontend

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.

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