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.
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
Examples
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, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..120, flattened
Crossrefs
Programs
-
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 *)
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).
Comments