login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A119826 Number of ternary words of length n with no 000's. 7
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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) = A000739(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)

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..700

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, M. D. Weiner, n 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).

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

EXAMPLE

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) = A000739(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

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

PROG

(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

CROSSREFS

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

Cf. A000739, A048996, A077835.

Sequence in context: A005774 A273343 A101169 * A027915 A295115 A114982

Adjacent sequences:  A119823 A119824 A119825 * A119827 A119828 A119829

KEYWORD

nonn,easy

AUTHOR

Emeric Deutsch, May 26 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 21:14 EDT 2022. Contains 354110 sequences. (Running on oeis4.)