A119826 -id:A119826 - cp's OEIS frontend

A231430 Number of ternary sequences which contain 000.

0, 0, 0, 1, 5, 21, 81, 295, 1037, 3555, 11961, 39667, 130049, 422403, 1361385, 4359115, 13880129, 43984227, 138795849, 436367131, 1367434577, 4272615603, 13315096089, 41397076939, 128429930465, 397665266595, 1229127726825, 3792875384251, 11686625364785

Offset: 0

Toby Gottfried, Nov 09 2013

nonn

Recurrence formula given below, a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)) based on following recursive construction: To a string of length (n-1) containing 000 add any of {0,1,2}. To a string of length (n-4) NOT containing 000, add 1000 or 2000. These two operations result in the two terms of the formula.

			For n = 3, the only string is 000.
For n = 4, the 5 strings are: 0000,0001,0002,1000,2000.
For n = 5, there are: 1 with 5 0's, 12 with 4 0's, and 8 with just 3; total 21.

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-4,-4,-6).

Cf. A119826 (without 000), A119827 (exactly one 000).

Cf. A186244 (with 00).

t = {0, 0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 4) - t[[-4]])], {n, 4, 30}]; t (* T. D. Noe, Nov 11 2013 *)
(* or *)
nn=28;r=Solve[{s==2x s+2x a+2x b+1,a==x s,b==x a,c==3x c+x b},{s,a,b,c}];CoefficientList[Series[c/.r,{x,0,nn}],x] (* Geoffrey Critzer, Jan 14 2014 *)
CoefficientList[Series[x^3/(1-5x+4x^2+4x^3+6x^4),{x,0,40}],x] (* or *) LinearRecurrence[{5,-4,-4,-6},{0,0,0,1},40] (* Harvey P. Dale, Jul 27 2021 *)

a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)).

G.f.: x^3/(1 - 5*x + 4*x^2 + 4*x^3 +6*x^4). - Geoffrey Critzer, Jan 14 2014

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

Original entry on oeis.org

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, 3938214304512

Offset: 0

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

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.

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.

			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.

Colin Barker, Table of n, a(n) for n = 0..1000
Li Guo and William Sit, Enumeration and Generating Functions for Differential Rota-Baxter Words, Math. Comput. Sci. 4 (2010), 339-358.
Index entries for linear recurrences with constant coefficients, signature (2,2,2).

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

Column 3 in A265624.

(* 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. *)
LinearRecurrence[{2,2,2},{1,3,9,27},30] (* Harvey P. Dale, Dec 01 2017 *)

Vec((1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3) + O(x^30)) \\ Colin Barker, Jun 28 2019

G.f.: 1+3t(t^2+t+1)/(1 - 2t(t^2+t+1)).
a(n+3) = 2(a(n)+a(n+1)+a(n+2)), a(0)=1, a(1)=3, a(2)=9, a(3)=27.
a(n) = 3*A119826(n-1). - R. J. Mathar, Dec 10 2015
G.f.: (1 + x)*(1 + x^2) / (1 - 2*x - 2*x^2 - 2*x^3). - Colin Barker, Jun 28 2019

a(0)=1 prepended by Alois P. Heinz, Dec 10 2015

A119825 Triangle read by rows: T(n,k) is the number of ternary sequences of length n containing k subsequences 000 (consecutively; n,k>=0).

Original entry on oeis.org

1, 3, 9, 26, 1, 76, 4, 1, 222, 16, 4, 1, 648, 60, 16, 4, 1, 1892, 212, 62, 16, 4, 1, 5524, 728, 224, 64, 16, 4, 1, 16128, 2444, 788, 236, 66, 16, 4, 1, 47088, 8064, 2712, 848, 248, 68, 16, 4, 1, 137480, 26256, 9168, 2984, 908, 260, 70, 16, 4, 1, 401392, 84576, 30576

Offset: 0

Emeric Deutsch, May 26 2006

Rows 0 and 1 have one term each; row n (n>=2) have n-1 terms. Sum of entries in row n is 3^n (A000244). T(n,0) = A119826(n) T(n,1) = A119827(n) Sum(k*T(n,k), k>=0)=(n-2)*3^(n-3) = A027741(n-1).

			T(5,2) = 4 because we have 00001, 00002, 10000 and 20000.
Triangle starts:
    1;
    3;
    9;
   26,  1;
   76,  4, 1;
  222, 16, 4, 1;
  ...

Alois P. Heinz, Rows n = 0..150, flattened

Cf. A000244, A119826, A119827, A027741.

G:=(1+(1-t)*z+(1-t)*z^2)/(1-(2+t)*z-2*(1-t)*z^2-2*(1-t)*z^3): Gser:=simplify(series(G,z=0,15)): P[0]:=1: for n from 1 to 12 do P[n]:=sort(coeff(Gser,z^n)) od: 1;3;for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) od; # yields sequence in triangular form

nn=10; f[list_]:=Select[list,#>0&]; a=x^2/(1-y x) +x; Map[f,CoefficientList[Series[(a+1)/(1-2x-2x a),{x,0,nn}],{x,y}]]//Grid (* Geoffrey Critzer, Oct 31 2012 *)

G.f.: G(t,z)=[1+(1-t)z+(1-t)z^2]/[1-(2+t)z-2(1-t)z^2-2(1-t)z^3].

A119827 Number of ternary words of length n with exactly one 000.

Original entry on oeis.org

0, 0, 0, 1, 4, 16, 60, 212, 728, 2444, 8064, 26256, 84576, 270048, 855936, 2696080, 8446912, 26341696, 81812544, 253181888, 781005440, 2402311616, 7370247168, 22558917120, 68901651456, 210037106688, 639127277568, 1941624275200, 5889576530944, 17839902853120

Offset: 0

Emeric Deutsch, May 26 2006

Except for the initial three zeros, convolution of A077835 with itself. Column 1 of A119825.

			a(4)=4 because we have 0001, 0002, 1000 and 2000.

Index entries for linear recurrences with constant coefficients, signature (4,0,-4,-12,-8,-4).

Cf. A077835, A119825, A119826 (without 000), A231430 (one or more 000).

h:=z^3/(1-2*z-2*z^2-2*z^3)^2: hser:=series(h,z=0,33): seq(coeff(hser,z,n), n=0..30);

LinearRecurrence[{4,0,-4,-12,-8,-4},{0,0,0,1,4,16},40] (* Harvey P. Dale, Jan 28 2021 *)

G.f.: z^3/(1-2z-2z^2-2z^3)^2.

A209239 Number of length n words on {0,1,2} with no four consecutive 0's.

Original entry on oeis.org

1, 3, 9, 27, 80, 238, 708, 2106, 6264, 18632, 55420, 164844, 490320, 1458432, 4338032, 12903256, 38380080, 114159600, 339561936, 1010009744, 3004222720, 8935908000, 26579404800, 79059090528, 235157252096, 699463310848

Offset: 0

Geoffrey Critzer, Jan 13 2013

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 377.

D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, J. Int. Seq. 18 (2015) # 15.4.7.
Index entries for linear recurrences with constant coefficients, signature (2,2,2,2).

Cf. A000079, A028859, A119826.

nn=25; CoefficientList[Series[(1-x^4)/(1-3x+2x^5), {x,0,nn}], x]
LinearRecurrence[{2,2,2,2},{1,3,9,27},40] (* Harvey P. Dale, Sep 13 2018 *)

O.g.f.: (1 - x^4)/(1 - 3*x+ 2*x^5) = (1+x)*(1+x^2)/(1-2*x-2*x^2-2*x^3-2*x^4).
a(n) = A160175(n) + A160175(n-1) + A160175(n-2) + A160175(n-3). - R. J. Mathar, Aug 04 2019
a(n) = 2*(a(n-1) + a(n-2) + a(n-3) + a(n-4)) for n>=4, with a(0) = 1, a(1) = 3, a(2) = 9, a(3) = 27. - Taras Goy, Aug 04 2019

A209241 3^n times the expected value of the longest run of 0's in all length n words on {0,1,2}.

Original entry on oeis.org

0, 1, 6, 25, 92, 317, 1054, 3425, 10964, 34729, 109162, 341125, 1061132, 3288713, 10161666, 31318201, 96312696, 295632805, 905955146, 2772234385, 8472129040, 25861509393, 78861419302, 240252829461, 731313754312, 2224352781697

Offset: 0

Geoffrey Critzer, Jan 13 2013

nonn

a(n) is also the sum of length n words on {0,1,2} that have no runs of 0's of length >= i for i >= 1. In other words, A000079 + A028859 + A119826 + A209239 + ...

			a(2) = 6 because for such length 2 words: 00, 01, 02, 10, 11, 12, 20, 21, 22 we have respectively longest zero runs of length 2 + 1 + 1 + 1 + 0 + 0 + 1 + 0 + 0 = 6.

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, Chapter 7.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A119706.

nn=25; CoefficientList[Series[Sum[1/(1-3x)-(1-x^k)/(1-3x+2x^(k+1)), {k,1,nn}], {x,0,nn}], x]

O.g.f.: Sum_{k=1..n} 1/(1-3x)-(1-x^k)/(1-3x+2x^(k+1)).

a(n) = Sum_{k=1..n} A209240(n,k)*k.

cp's OEIS Frontend

A231430 Number of ternary sequences which contain 000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A119825 Triangle read by rows: T(n,k) is the number of ternary sequences of length n containing k subsequences 000 (consecutively; n,k>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A119827 Number of ternary words of length n with exactly one 000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A209239 Number of length n words on {0,1,2} with no four consecutive 0's.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A209241 3^n times the expected value of the longest run of 0's in all length n words on {0,1,2}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula