A242631 Number of n-length words w over an 8-ary alphabet {a_1,...,a_8} such that w contains never more than j consecutive letters a_j (for 1<=j<=8).

1, 8, 63, 496, 3904, 30729, 241871, 1903792, 14984945, 117948062, 928381475, 7307387240, 57517205708, 452723914009, 3563437058402, 28048184061555, 220770176730345, 1737705044525640, 13677657310833723, 107658264618591797, 847389408675004032, 6669890253930098674

Offset: 0

Author

Geoffrey Critzer and Alois P. Heinz, May 19 2014

Keywords

• nonn
• easy

Links

• Geoffrey Critzer and Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (5, 16, 39, 79, 144, 229, 345, 480, 631, 782, 927, 1039, 1119, 1148, 1128, 1056, 950, 809, 659, 507, 369, 249, 159, 90, 46, 20, 7).

Crossrefs

Column k=8 of A242464.

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-> b(n, 8, 0$2):
seq(a(n), n=0..30);

Formula

G.f.: -(x^2+x+1) *(x^6+x^3+1) *(x+1) *(x^2+1) *(x^4+1) *(x^6+x^5+x^4+x^3+x^2+x+1) *(x^2-x+1) *(x^4+x^3+x^2+x+1) / (7*x^27 +20*x^26 +46*x^25 +90*x^24 +159*x^23 +249*x^22 +369*x^21 +507*x^20 +659*x^19 +809*x^18 +950*x^17 +1056*x^16 +1128*x^15 +1148*x^14 +1119*x^13 +1039*x^12 +927*x^11 +782*x^10 +631*x^9 +480*x^8 +345*x^7 +229*x^6 +144*x^5 +79*x^4 +39*x^3 +16*x^2 +5*x-1).