A119827 -id:A119827 - cp's OEIS frontend

A119826 Number of ternary words of length n with no 000's.

1, 3, 9, 26, 76, 222, 648, 1892, 5524, 16128, 47088, 137480, 401392, 1171920, 3421584, 9989792, 29166592, 85155936, 248624640, 725894336, 2119349824, 6187737600, 18065963520, 52746101888, 153999606016, 449623342848, 1312738101504, 3832722100736, 11190167090176, 32671254584832

Offset: 0

Emeric Deutsch, May 26 2006

Column 0 of A119825.
From Wolfdieter Lang, Dec 08 2020: (Start)
The sequence b(n) = a(n-1), for n >= 1, and b(0) = 1, with o.g.f. Gb(x) = (1 - x - x^2 - x^3)*G(x), where G(x) = 1/(1 - 2*x - 2*x^2 - 2*x^3) generates A077835, is the INVERT transform of the tribonacci sequence {Trib(k+2)}_{k >= 1}, with Trib(n) = A000073(n). See the Bernstein and Sloane link for INVERT.
The proof that (1 - 2*x - 2*x^2 - 2*x^3) = (1 - x - x^2 - x^3)*(1 - Sum_{k = 1..M} Trib(k+2)*x^k), for M >= 3, up to terms starting with Trib(M+3)*x^{M+1} can be done by induction, using the tribonacci recurrence. Letting M -> infinity one obtains the o.g.f. of {b(n)}_{n>=0} from the one given by the INVERT transform.
The explicit form of b(n), for n >= 1, is given in terms of the partition array A048996 (M_0-multinomials) with the multivariate row polynomials with indeterminates {Trib(k+2)}_{k = 1..n}. See the example section instead of giving the general baroque partition formula. (End)

			a(4)=76 because among the 3^4=81 ternary words of length 4 only 0000, 0001, 0002, 1000 and 2000 contain 000's.
Partition formula from INVERT with T(n) = Trib(n+2) = A000073(n+2) (see the W. Lang comment above) a(4) = 76 = b(5) = 1*T(5) + (2*T(1)*T(4) + 2*T(2)*T(3)) + (3*T(1)^2*T(3) + 3*T(1)*T(2)^2) + 4*T(1)^3*T(2) + 1*T(1)^5, from row n = 5 of A048996: [1, 2, 2, 3, 3, 4, 1]. - _Wolfdieter Lang_, Dec 08 2020

Alois P. Heinz, Table of n, a(n) for n = 0..700
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 14.
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
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.
Index entries for linear recurrences with constant coefficients, signature (2,2,2).

Cf. A119825, A119827 (exactly one 000), A231430 (one or more 000).

Cf. A000073, A048996, A077835.

g:=(1+z+z^2)/(1-2*z-2*z^2-2*z^3): gser:=series(g,z=0,32): seq(coeff(gser,z,n),n=0..28);
# second Maple program:
a:= n-> (<<0|1|0>, <0|0|1>, <2|2|2>>^n. <<1, 3, 9>>)[1, 1]:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 30 2012

nn=30;CoefficientList[Series[(1-x^3)/(1-3x+2x^4),{x,0,nn}],x]  (* Geoffrey Critzer, Oct 30 2012 *)
LinearRecurrence[{2, 2, 2}, {1, 3, 9}, 30] (* Jean-François Alcover, Dec 25 2015 *)

a(n):=sum(sum(binomial(k-1,m-1)*sum(binomial(j,n-3*k+2*j)*binomial(k,j),j,0,k),k,m,n),m,1,n); /* Vladimir Kruchinin, Apr 25 2011 */

G.f.: (1+z+z^2)/(1-2*z-2*z^2-2*z^3).
a(n-1) = Sum_{m=1..n} Sum_{k=m..n} C(k-1, m-1) * Sum_{j=0..k} C(j, n-3*k+2*j) * C(k, j). - Vladimir Kruchinin, Apr 25 2011
G.f. for sequence with 1 prepended: 1/( 1 - Sum_{k>=1} (x+x^2+x^3)^k). - Joerg Arndt, Sep 30 2012 [This g.f. is then (1 - x - x^2 - x^3)/(1 - 2*x - 2*x^2 - 2*x^3); see the above given INVERT comment. - Wolfdieter Lang, Dec 08 2020]
a(n) = round((3/2)*((r+s+2)/3)^(n+3)/(r^2+s^2+10)), where r=(53+3*sqrt(201))^(1/3), s=(53-3*sqrt(201))^(1/3); r and s are the real roots of the polynomial x^6 - 106*x^3 + 1000. - Anton Nikonov, Jul 11 2013
a(n) = A077835(n) + A077835(n-1) + A077835(n-2). - R. J. Mathar, Aug 07 2015

A231430 Number of ternary sequences which contain 000.

Original entry on oeis.org

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

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

cp's OEIS Frontend

A119826 Number of ternary words of length n with no 000's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A231430 Number of ternary sequences which contain 000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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