|
| |
|
|
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
|
Table of n, a(n) for n=1..26.
|
|
|
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
|
| |
|
|
