A181137 - OEIS

%I #28 Apr 30 2023 16:26:40

%S 1,3,9,27,78,228,666,1944,5676,16572,48384,141264,412440,1204176,

%T 3515760,10264752,29969376,87499776,255467808,745873920,2177683008,

%U 6358049472,18563212800,54197890560,158238305664,461998818048,1348870028544,3938214304512

%N The number of ways to color n balls in a row with 3 colors with no color runs having lengths greater than 3.

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

%H Colin Barker, <a href="/A181137/b181137.txt">Table of n, a(n) for n = 0..1000</a>

%H Li Guo and William Sit, <a href="http://dx.doi.org/10.1007/s11786-010-0062-1">Enumeration and Generating Functions for Differential Rota-Baxter Words</a>, Math. Comput. Sci. 4 (2010), 339-358.

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

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

%F a(n+3) = 2(a(n)+a(n+1)+a(n+2)), a(0)=1, a(1)=3, a(2)=9, a(3)=27.

%F a(n) = 3*A119826(n-1). - _R. J. Mathar_, Dec 10 2015

%F G.f.: (1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3). - _Colin Barker_, Jun 28 2019

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

%t (* next[p,z] computes the next member in a sequence and

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

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

%t LinearRecurrence[{2,2,2},{1,3,9,27},30] (* _Harvey P. Dale_, Dec 01 2017 *)

%o (PARI) Vec((1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3) + O(x^30)) \\ _Colin Barker_, Jun 28 2019

%Y 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).

%Y Column 3 in A265624.

%K nonn,easy

%O 0,2

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

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 10 2015