This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A181137 The number of ways to color n balls in a row with 3 colors with no color runs having lengths greater than 3. 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 dice n times, requiring each face having no runs longer than b. 1
 3, 9, 27, 78, 228, 666, 1944, 5676, 16572, 48384, 141264, 412440, 1204176, 3515760, 10264752, 29969376, 87499776, 255467808, 745873920, 2177683008, 6358049472, 18563212800, 54197890560, 158238305664, 461998818048, 1348870028544 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS 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. [To editor: sorry, this corrects an error in the previous submission: the 1 should not be the leading term when base is 1.) REFERENCES Li Guo and William Sit, Enumeration and Generating Functions for Differential Rota-Baxter Words, in preparation, 2010. LINKS FORMULA For this sequence (p=3,b=3), G.f. 3t(t^2+t+1)/(1 - 2t(t^2+t+1)). a{n+3) = 2(a(n)+a(n+1)+a(n+2)), a(1)=3, a(2)=9, a(3)=27 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. *) 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). Sequence in context: A152169 A006810 A090401 * A113041 A026289 A027129 Adjacent sequences:  A181134 A181135 A181136 * A181138 A181139 A181140 KEYWORD nonn AUTHOR William Sit (wyscc(AT)sci.ccny.cuny.edu), Oct 06 2010 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .