A242452 Number of length n words on {1,2,3} with no more than one consecutive 1 and no more than two consecutive 2's and no more than three consecutive 3's.

1, 3, 8, 21, 54, 140, 362, 937, 2425, 6275, 16239, 42024, 108751, 281430, 728295, 1884709, 4877320, 12621710, 32662931, 84526348, 218740428, 566064618, 1464883079, 3790878933, 9810177543, 25387142435, 65697791726, 170015189725, 439971633412, 1138574962157

Offset: 0

Author

Geoffrey Critzer and Alois P. Heinz, May 14 2014

Keywords

• nonn
• easy

Examples

			a(3) = 21 because there are 27 length 3 words on {1,2,3} but we don't count: 111, 112, 113, 211, 222, 311.
		

Links

• Fung Lam, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (1,2,4,3,2).

Crossrefs

Cf. A000931 (binary words with at most one consecutive 1 and two consecutive 2's; offset=-8 for n>0).

Cf. A007283 (ternary words with no consecutive like letters).

Column k=3 of A242464.

Programs

Mathematica

nn=20;CoefficientList[Series[1/(1-Sum[v[i]/(1+v[i])/.v[i]->(z-z^(i+1))/(1-z),{i,1,3}]),{z,0,nn}],z]
(* replacing the 3 in this code with a positive integer k will return the number of words on {1,2,...,k} with no more than one consecutive 1 and no more than two consecutive 2's and ... no more than k consecutive k's *)

Formula

G.f.: (1 + x)*(1 + x^2)*(1 + x + x^2)/(1 - x - 2*x^2 - 4*x^3 - 3*x^4 - 2*x^5).