login
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.
4

%I #30 Aug 07 2015 16:52:49

%S 1,3,8,21,54,140,362,937,2425,6275,16239,42024,108751,281430,728295,

%T 1884709,4877320,12621710,32662931,84526348,218740428,566064618,

%U 1464883079,3790878933,9810177543,25387142435,65697791726,170015189725,439971633412,1138574962157

%N 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.

%H Fung Lam, <a href="/A242452/b242452.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,4,3,2).

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

%e 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.

%t 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]

%t (* 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 *)

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

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

%Y Column k=3 of A242464.

%K nonn,easy

%O 0,2

%A _Geoffrey Critzer_ and _Alois P. Heinz_, May 14 2014