OFFSET
0,2
COMMENTS
This sequence is a special case of the general problem for coloring n balls in a row with p colors where each color has a given maximum run-length. In this example, the bounds are uniformly 3. It can be phrased in terms of tossing a p-faced die n times, requiring each face to have no runs longer than b.
Generating function and recurrence for given p and uniform bound b are known. a(n+b) = (p-1)(a(n)+ ... + a(n+b-1)), using b initial values a(1)=p, a(2)=p^2, ..., a(b)=p^(b) The g.f. is p*G/(1-(p-1)*G) where G = t + t^2 + ... + t^b.
LINKS
Colin Barker, Table of n, a(n) for n = 0..1000
Li Guo and William Sit, Enumeration and Generating Functions for Differential Rota-Baxter Words, Math. Comput. Sci. 4 (2010), 339-358.
Index entries for linear recurrences with constant coefficients, signature (2,2,2).
FORMULA
G.f.: 1+3t(t^2+t+1)/(1 - 2t(t^2+t+1)).
a(n+3) = 2(a(n)+a(n+1)+a(n+2)), a(0)=1, a(1)=3, a(2)=9, a(3)=27.
a(n) = 3*A119826(n-1). - R. J. Mathar, Dec 10 2015
G.f.: (1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3). - Colin Barker, Jun 28 2019
EXAMPLE
For p=3 and b=3, a(4)=78. The colorings are: 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211, 1212, 1213, 1221, 1222, 1223, 1231, 1232, 1233, 1311, 1312, 1313, 1321, 1322, 1323, 1331, 1332, 1333, 2111, 2112, 2113, 2121, 2122, 2123, 2131, 2132, 2133, 2211, 2212, 2213, 2221, 2223, 2231, 2232, 2233, 2311, 2312, 2313, 2321, 2322, 2323, 2331, 2332, 2333, 3111, 3112, 3113, 3121, 3122, 3123, 3131, 3132, 3133, 3211, 3212, 3213, 3221, 3222, 3223, 3231, 3232, 3233, 3311, 3312, 3313, 3321, 3322, 3323, 3331, 3332.
MATHEMATICA
(* next[p, z] computes the next member in a sequence and
next[p, z] = a(n+b)= (p-1)( c(b)+ ... + c(n+b-1)) where z is the preceding b items on the sequence starting with a(n) where b is the uniform bound on runs.
The function sequence[p, z, n] computes the next n terms. *) next[p_, z_]:=(p-1) Apply[Plus, z] sequence[p_, z_, n_]:=Module[{y=z, seq=z, m=n, b=Length[z]}, While[m>0, seq = Join[seq, {next[p, y]}]; y = Take[seq, -b]; m-- ]; seq] (* sequence[3, {3, 9, 27}, 10] computes the next 10 terms after 3, 9, 27. *)
LinearRecurrence[{2, 2, 2}, {1, 3, 9, 27}, 30] (* Harvey P. Dale, Dec 01 2017 *)
PROG
(PARI) Vec((1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3) + O(x^30)) \\ Colin Barker, Jun 28 2019
CROSSREFS
A135492 is sequence[2, {2, 4, 6, 8}, n-4], for colorings of n balls in a row with p=2 colors so no color has run length more than 4. A135491 coloring of 2 balls in a row with p=2 colors so no color has run length more than 3. In general 2 colorings are like coin tossing. The example here is 3 colorings (tossing 3-sided dice).
Column 3 in A265624.
KEYWORD
nonn,easy
AUTHOR
William Sit (wyscc(AT)sci.ccny.cuny.edu), Oct 06 2010
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Dec 10 2015
STATUS
approved