|
%I #56 Oct 12 2022 08:41:39
%S 1,3,9,26,76,222,648,1892,5524,16128,47088,137480,401392,1171920,
%T 3421584,9989792,29166592,85155936,248624640,725894336,2119349824,
%U 6187737600,18065963520,52746101888,153999606016,449623342848,1312738101504,3832722100736,11190167090176,32671254584832
%N Number of ternary words of length n with no 000's.
%C Column 0 of A119825.
%C From _Wolfdieter Lang_, Dec 08 2020: (Start)
%C 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.
%C 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.
%C 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)
%H Alois P. Heinz, <a href="/A119826/b119826.txt">Table of n, a(n) for n = 0..700</a>
%H M. Bernstein and N. J. A. Sloane, <a href="https://arxiv.org/abs/math/0205301">Some canonical sequences of integers</a>, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210.
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,2).
%F G.f. (1+z+z^2)/(1-2*z-2*z^2-2*z^3).
%F 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
%F 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]
%F 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
%F a(n) = A077835(n) + A077835(n-1) + A077835(n-2). - _R. J. Mathar_, Aug 07 2015
%e a(4)=76 because among the 3^4=81 ternary words of length 4 only 0000, 0001, 0002, 1000 and 2000 contain 000's.
%e 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
%p 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);
%p # second Maple program:
%p a:= n-> (<<0|1|0>, <0|0|1>, <2|2|2>>^n. <<1, 3, 9>>)[1, 1]:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Oct 30 2012
%t nn=30;CoefficientList[Series[(1-x^3)/(1-3x+2x^4),{x,0,nn}],x] (* _Geoffrey Critzer_, Oct 30 2012 *)
%t LinearRecurrence[{2, 2, 2}, {1, 3, 9}, 30] (* _Jean-François Alcover_, Dec 25 2015 *)
%o (Maxima)
%o 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
%Y Cf. A119825, A119827 (exactly one 000), A231430 (one or more 000).
%Y Cf. A000739, A048996, A077835.
%K nonn,easy
%O 0,2
%A _Emeric Deutsch_, May 26 2006
|
