A077835 -id:A077835 - 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

A119827 Number of ternary words of length n with exactly one 000.

Original entry on oeis.org

0, 0, 0, 1, 4, 16, 60, 212, 728, 2444, 8064, 26256, 84576, 270048, 855936, 2696080, 8446912, 26341696, 81812544, 253181888, 781005440, 2402311616, 7370247168, 22558917120, 68901651456, 210037106688, 639127277568, 1941624275200, 5889576530944, 17839902853120

Offset: 0

Emeric Deutsch, May 26 2006

Except for the initial three zeros, convolution of A077835 with itself. Column 1 of A119825.

			a(4)=4 because we have 0001, 0002, 1000 and 2000.

Index entries for linear recurrences with constant coefficients, signature (4,0,-4,-12,-8,-4).

Cf. A077835, A119825, A119826 (without 000), A231430 (one or more 000).

h:=z^3/(1-2*z-2*z^2-2*z^3)^2: hser:=series(h,z=0,33): seq(coeff(hser,z,n), n=0..30);

LinearRecurrence[{4,0,-4,-12,-8,-4},{0,0,0,1,4,16},40] (* Harvey P. Dale, Jan 28 2021 *)

G.f.: z^3/(1-2z-2z^2-2z^3)^2.

A160175 Expansion of 1/(1 - 2x - 2x^2 - 2x^3 - 2x^4).

Original entry on oeis.org

1, 2, 6, 18, 54, 160, 476, 1416, 4212, 12528, 37264, 110840, 329688, 980640, 2916864, 8676064, 25806512, 76760160, 228319200, 679123872, 2020019488, 6008445440, 17871816000, 53158809600, 158118181056, 470314504192, 1398926621696, 4161036233088

Offset: 0

Geoffrey Critzer, May 03 2009, May 06 2009

nonn

a(n) is the number of ways two opposing baseball teams could score a combined total of n runs (tallying the score just prior to each "batter up!") considering the order of the scoring as important. Equivalently, a(n) is the number of 2-colored tilings of an n-board with tiles of length at most 4.

a(n) is the number of compositions (ordered partitions) of n into parts <= 4 with 2 sorts of each part. - Joerg Arndt, Aug 06 2019

Arthur Benjamin and Jennifer Quinn, Proofs that Really Count, Mathematical Association of America, 2003, p. 36.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,2,2,2).

Cf. A077835, A002605, A000079.

m:=30; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(1/(1-2*x-2*x^2-2*x^3-2*x^4))); // G. C. Greubel, Sep 24 2018

RecurrenceTable[{a[n] == 2(a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]), a[0] == 1, a[1] == 2, a[2] == 6, a[3] == 18}, a, {n, 0, 20}]
LinearRecurrence[{2,2,2,2},{1,2,6,18},30] (* Harvey P. Dale, Oct 27 2013 *)
CoefficientList[Series[1/(1-2*x-2*x^2-2*x^3-2*x^4), {x, 0, 50}], x] (* G. C. Greubel, Sep 24 2018 *)

x='x+O('x^30); Vec(1/(1-2*x-2*x^2-2*x^3-2*x^4)) \\ G. C. Greubel, Sep 24 2018

a(n) = 2*(a(n-1) + a(n-2) + a(n-3) + a(n-4)).

More terms from Harvey P. Dale, Oct 27 2013

A077984 Expansion of 1/(1+2x-2x^2+2*x^3).

Original entry on oeis.org

1, -2, 6, -18, 52, -152, 444, -1296, 3784, -11048, 32256, -94176, 274960, -802784, 2343840, -6843168, 19979584, -58333184, 170311872, -497249280, 1451788672, -4238699648, 12375475200, -36131927040, 105492203776, -307999212032, 899246685696, -2625476203008, 7665444201472

Offset: 0

N. J. A. Sloane, Nov 17 2002

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (-2, 2, -2).

Cf. A077835.

a:=[1,-2,6];; for n in [4..30] do a[n]:=-2*a[n-1]+2*a[n-2] - 2*a[n-3]; od; a; # G. C. Greubel, Jun 25 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( 1/(1+2*x-2*x^2+2*x^3) )); // G. C. Greubel, Jun 25 2019

CoefficientList[Series[1/(1+2x-2x^2+2x^3),{x,0,30}],x] (* or *) LinearRecurrence[{-2,2,-2},{1,-2,6},30] (* Harvey P. Dale, Jun 17 2014 *)

my(x='x+O('x^30)); Vec(1/(1+2*x-2*x^2+2*x^3)) \\ G. C. Greubel, Jun 25 2019

(1/(1+2*x-2*x^2+2*x^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jun 25 2019

a(n) = -2*a(n-1) + 2*a(n-2) - 2*a(n-3).
a(n) is the nearest integer to c*d^n where c=0.7166689603... satisfies 67*c^3 - 67*c^2 + 15*c - 1 = 0 and d=-2.9196395658... satisfies d^3 + 2*d^2 - 2*d + 2 = 0.
a(n) = (-1)^n * A077835(n). - R. J. Mathar, Aug 07 2015

A103771 Expansion of 1/(1-4x-4x^2-4x^3).

Original entry on oeis.org

1, 4, 20, 100, 496, 2464, 12240, 60800, 302016, 1500224, 7452160, 37017600, 183879936, 913398784, 4537185280, 22537856000, 111953760256, 556115206144, 2762427289600, 13721985024000, 68162110078976, 338586089570304

Offset: 0

Paul Barry, Feb 15 2005

The sequence with g.f. 1/(1-r*x-r*x^2-r*x^3) has general term Sum_{k=0..n} T(n-k,k)r^(n-k).

Michael De Vlieger, Table of n, a(n) for n = 0..1436
Yassine Otmani, The 2-Pascal Triangle and a Related Riordan Array, J. Int. Seq. (2025) Vol. 28, Issue 3, Art. No. 25.3.5. See p. 19.
Index entries for linear recurrences with constant coefficients, signature (4,4,4).

Cf. A077828, A077835, A000073.

CoefficientList[Series[1/(1 - 4 x - 4 x^2 - 4 x^3), {x, 0, 21}], x] (* Michael De Vlieger, May 07 2025 *)

a(n) = Sum_{k=0..n} T(n-k, k)4^(n-k), where T(n, k) = trinomial coefficients (A027907).

cp's OEIS Frontend

A077935 Duplicate of A077835.

Views

Author

Keywords

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A119827 Number of ternary words of length n with exactly one 000.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A160175 Expansion of 1/(1 - 2*x - 2*x^2 - 2*x^3 - 2*x^4).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A077984 Expansion of 1/(1+2*x-2*x^2+2*x^3).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A103771 Expansion of 1/(1-4x-4x^2-4x^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A160175 Expansion of 1/(1 - 2x - 2x^2 - 2x^3 - 2x^4).

A077984 Expansion of 1/(1+2x-2x^2+2*x^3).