A242632 Number of n-length words w over a 9-ary alphabet {a_1,...,a_9} such that w contains never more than j consecutive letters a_j (for 1<=j<=9).

1, 9, 80, 711, 6318, 56143, 498896, 4433274, 39394819, 350068993, 3110771999, 27642843622, 245638961566, 2182789161071, 19396631915857, 172361736254288, 1531635402139359, 13610370004776711, 120944038906506659, 1074729088326395697, 9550223588843166996

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 (7, 12, 34, 59, 109, 166, 258, 352, 483, 606, 754, 875, 1007, 1087, 1161, 1172, 1167, 1099, 1023, 895, 775, 628, 503, 371, 273, 179, 118, 66, 38, 15, 8).

Crossrefs

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

Formula

G.f.: -(x+1) *(x^4-x^3+x^2-x+1) *(x^4+x^3+x^2+x+1) *(x^2+x+1) *(x^6+x^3+1) *(x^2+1)*(x^4+1) *(x^6+x^5+x^4+x^3+x^2+x+1) *(x^2-x+1) / (8*x^31 +15*x^30 +38*x^29 +66*x^28 +118*x^27 +179*x^26 +273*x^25 +371*x^24 +503*x^23 +628*x^22 +775*x^21 +895*x^20 +1023*x^19 +1099*x^18 +1167*x^17 +1172*x^16 +1161*x^15 +1087*x^14 +1007*x^13 +875*x^12 +754*x^11 +606*x^10 +483*x^9 +352*x^8 +258*x^7 +166*x^6 +109*x^5 +59*x^4 +34*x^3 +12*x^2 +7*x-1).