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,2

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).

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).

Example

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.

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 *)

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.

Sequence in context: A127358 A077849 A135473 * A190139 A335807 A005580

Adjacent sequences: A242449 A242450 A242451 * A242453 A242454 A242455

Keyword

nonn,easy

Author

Geoffrey Critzer and Alois P. Heinz, May 14 2014

Status

approved