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
Examples
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
Links
- 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).
Programs
-
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. *)
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.
Comments