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

Author

Emeric Deutsch, May 26 2006

Keywords

• nonn
• easy

Comments

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)

Examples

			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
		

Links

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

Crossrefs

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

Cf. A000073, A048996, A077835.

Programs

Maple

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

Mathematica

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

Maxima

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 */

Formula

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