|
| |
|
|
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
|
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
|
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.
|
|
|
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
|
|
|
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]:
|
|
|
MATHEMATICA
|
nn=30; CoefficientList[Series[(1-x^3)/(1-3x+2x^4), {x, 0, nn}], x] (* Geoffrey Critzer, Oct 30 2012 *)
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
