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

%I #20 Apr 30 2023 16:26:35

%S 3,9,27,81,240,714,2124,6318,18792,55896,166260,494532,1470960,

%T 4375296,13014096,38709768,115140240,342478800,1018685808,3030029232,

%U 9012668160,26807724000,79738214400,237177271584,705471756288,2098389932544

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

%C Generating function and recurrence for given p and uniform bound b are known.

%C a(n+b) = (p-1)(a(n) + ... + a(n+b-1)),

%C using b initial values a(1)=p, a(2)=p^2, ..., a(b)=p^(b).

%C The g.f. is p G/(1-(p-1)G) where G = t + t^2 + ... + t^b.

%H Martin Burtscher, Igor Szczyrba, and RafaƂ Szczyrba, <a href="https://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.

%H Li Guo and William Sit, <a href="http://dx.doi.org/10.1007/s11786-010-0061-2">Enumeration and Generating Functions for Differential Rota-Baxter Words</a>, Math. Comput. Science 4 (2-3) (2010) 313-337.

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

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

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

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

%e The first nontrivial value is a(5)=240. These solutions are listed below: 11112,11113,11121,11122,11123,

%e 11131,11132,11133,11211,11212,11213,11221,11222,11223,11231,11232,11233,11311,11312,11313,11321,11322,11323,

%e 11331,11332,11333,12111,12112,12113,12121,12122,12123,12131,12132,12133,12211,12212,12213,12221,12222,12223,

%e 12231,12232,12233,12311,12312,12313,12321,12322,12323,12331,12332,12333,13111,13112,13113,13121,13122,13123,

%e 13131,13132,13133,13211,13212,13213,13221,13222,13223,13231,

%e 13232,13233,13311,13312,13313,13321,13322,13323,13331,13332,13333,21111,21112,21113,21121,21122,21123,21131,

%e 21132,21133,21211,21212,21213,21221,21222,21223,21231,21232,21233,21311,21312,21313,21321,21322,21323,21331,

%e 21332,21333,22111,22112,22113,22121,22122,22123,22131,22132,22133,22211,22212,22213,22221,22223,22231,22232,

%e 22233,22311,22312,22313,22321,22322,22323,22331,22332,22333,23111,23112,23113,23121,23122,23123,23131,23132,

%e 23133,23211,23212,23213,23221,23222,23223,23231,23232,23233,23311,

%e 23312,23313,23321,23322,23323,23331,23332,23333,31111,31112,31113,31121,31122,31123,31131,31132,31133,31211,

%e 31212,31213,31221,31222,31223,31231,31232,31233,31311,31312,31313,31321,31322,31323,31331,31332,31333,32111,

%e 32112,32113,32121,32122,32123,32131,32132,32133,32211,32212,32213,32221,32222,32223,32231,32232,32233,32311,

%e 32312,32313,32321,32322,32323,32331,32332,32333,33111,33112,33113,33121,33122,33123,33131,33132,33133,33211,

%e 33212,33213,33221,33222,33223,33231,33232,33233,33311,33312,33313,33321,33322,33323,33331,33332

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

%t where z is the preceding b items on the sequence starting with a(n) where b is the uniform bound on runs.

%t The function sequence[p,z,n] computes the next n terms. *)

%t next[p_,z_]:=(p-1) Apply[Plus,z]

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

%t (* sequence[3,{3,9,27,81},10] computes the next 10 terms after 3,9,27, 81. *)

%Y Cf. A181137, A135492, A121907.

%K nonn,easy

%O 1,1

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