A181140 The number of ways to color n balls in a row with 3 colors with no color runs having lengths greater than 4. 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 4. It can be phrased in terms of tossing a p-faced die n times, requiring each face to have no runs longer than b.

3, 9, 27, 81, 240, 714, 2124, 6318, 18792, 55896, 166260, 494532, 1470960, 4375296, 13014096, 38709768, 115140240, 342478800, 1018685808, 3030029232, 9012668160, 26807724000, 79738214400, 237177271584, 705471756288, 2098389932544

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.

Links

Table of n, a(n) for n=1..26.

Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.

Li Guo and William Sit, Enumeration and Generating Functions for Differential Rota-Baxter Words, Math. Comput. Science 4 (2-3) (2010) 313-337.

Index entries for linear recurrences with constant coefficients, signature (2,2,2,2).

Formula

For this sequence (p=3, b=4):

G.f.: 3t(t^3+t^2+t+1)/(1 - 2t(t^3+t^2+t+1));

a(n+4) = 2(a(n)+a(n+1)+a(n+2)+a(n+3)); a(1)=3, a(2)=9, a(3)=27, a(4)=81.

Example

The first nontrivial value is a(5)=240. These solutions are listed below: 11112,11113,11121,11122,11123,
11131,11132,11133,11211,11212,11213,11221,11222,11223,11231,11232,11233,11311,11312,11313,11321,11322,11323,
11331,11332,11333,12111,12112,12113,12121,12122,12123,12131,12132,12133,12211,12212,12213,12221,12222,12223,
12231,12232,12233,12311,12312,12313,12321,12322,12323,12331,12332,12333,13111,13112,13113,13121,13122,13123,
13131,13132,13133,13211,13212,13213,13221,13222,13223,13231,
13232,13233,13311,13312,13313,13321,13322,13323,13331,13332,13333,21111,21112,21113,21121,21122,21123,21131,
21132,21133,21211,21212,21213,21221,21222,21223,21231,21232,21233,21311,21312,21313,21321,21322,21323,21331,
21332,21333,22111,22112,22113,22121,22122,22123,22131,22132,22133,22211,22212,22213,22221,22223,22231,22232,
22233,22311,22312,22313,22321,22322,22323,22331,22332,22333,23111,23112,23113,23121,23122,23123,23131,23132,
23133,23211,23212,23213,23221,23222,23223,23231,23232,23233,23311,
23312,23313,23321,23322,23323,23331,23332,23333,31111,31112,31113,31121,31122,31123,31131,31132,31133,31211,
31212,31213,31221,31222,31223,31231,31232,31233,31311,31312,31313,31321,31322,31323,31331,31332,31333,32111,
32112,32113,32121,32122,32123,32131,32132,32133,32211,32212,32213,32221,32222,32223,32231,32232,32233,32311,
32312,32313,32321,32322,32323,32331,32332,32333,33111,33112,33113,33121,33122,33123,33131,33132,33133,33211,
33212,33213,33221,33222,33223,33231,33232,33233,33311,33312,33313,33321,33322,33323,33331,33332

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, 81}, 10] computes the next 10 terms after 3, 9, 27, 81. *)

Crossrefs

Cf. A181137, A135492, A121907.

Sequence in context: A274627 A080557 A022014 * A291007 A038002 A272338

Adjacent sequences: A181137 A181138 A181139 * A181141 A181142 A181143

Keyword

nonn,easy

Author

William Sit (wyscc(AT)sci.ccny.cuny.edu), Oct 06 2010

Status

approved