A231430 -id:A231430 - 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.

A340242 Square array read by upward antidiagonals: T(n,k) is the number of n-ary strings of length k containing 000.

Original entry on oeis.org

1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 47, 1, 11, 65, 208, 295, 107, 1, 13, 96, 425, 1021, 1037, 238, 1, 15, 133, 756, 2621, 4831, 3555, 520, 1, 17, 176, 1225, 5611, 15569, 22276, 11961, 1121, 1, 19, 225, 1856, 10627, 40091, 90085, 100768, 39667, 2391

Offset: 2

Robert P. P. McKone, Jan 01 2021

			For n = 4 and k = 5, there are 40 strings: {00000, 00001, 00002, 00003, 00010, 00011, 00012, 00013, 00020, 00021, 00022, 00023, 00030, 00031, 00032, 00033, 01000, 02000, 03000, 10000, 10001, 10002, 10003, 11000, 12000, 13000, 20000, 20001, 20002, 20003, 21000, 22000, 23000, 30000, 30001, 30002, 30003, 31000, 32000, 33000}.
Square table T(n,k):
      k=3: k=4:  k=5:   k=6:    k=7:     k=8:
n=2:    1    3     8     20      47      107
n=3:    1    5    21     81     295     1037
n=4:    1    7    40    208    1021     4831
n=5:    1    9    65    425    2621    15569
n=6:    1   11    96    756    5611    40091
n=7:    1   13   133   1225   10627    88717
n=8:    1   15   176   1856   18425   175967
n=9:    1   17   225   2673   29881   321281

Robert P. P. McKone, Antidiagonals n = 2..100, flattened

Rows: A050231 (n=2), A231430 (n=3).
Columns: A000567 (k=5), A103532 (k=6).
Cf. A340156 (containing 00).
Cf. A341050.
Cf. A000073, A068601.

m[r_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]];
T[n_, k_, r_] := MatrixPower[m[r], k][[1, r + 1]]*n^k;
Reverse[Table[T[n, k - n + 3, 3], {k, 2, 11}, {n, 2, k}], 2] // Flatten

my(x2='x^2+'x+1); T(n,k) = n^k - polcoeff(lift(x2*Mod('x, 'x^3-(n-1)*x2)^k), 2); \\ Kevin Ryde, Jan 02 2021

m(3) = [1 - 1/n, 1/n, 0, 0; 1 - 1/n, 0, 1/n, 0; 1 - 1/n, 0, 0, 1/n; 0, 0, 0, 1], is the probability/transition matrix for three consecutive "0" -> "containing 000".

A341050 Cube array read by upward antidiagonals ignoring zero and empty terms: T(n, k, r) is the number of n-ary strings of length k, containing r consecutive 0's.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 3, 1, 5, 8, 1, 1, 3, 1, 5, 8, 1, 7, 21, 19, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 43, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 47, 1, 11, 65, 208, 295, 94, 1, 1, 3, 1, 5, 8, 1, 7, 21, 20, 1, 9, 40, 81, 48, 1, 11, 65, 208, 297, 107, 1, 13, 96, 425, 1024, 1037, 201

Offset: 2

Robert P. P. McKone, Feb 04 2021

			For n = 5, k = 6 and r = 4, there are 65 strings: {000000, 000001, 000002, 000003, 000004, 000010, 000011, 000012, 000013, 000014, 000020, 000021, 000022, 000023, 000024, 000030, 000031, 000032, 000033, 000034, 000040, 000041, 000042, 000043, 000044, 010000, 020000, 030000, 040000, 100000, 100001, 100002, 100003, 100004, 110000, 120000, 130000, 140000, 200000, 200001, 200002, 200003, 200004, 210000, 220000, 230000, 240000, 300000, 300001, 300002, 300003, 300004, 310000, 320000, 330000, 340000, 400000, 400001, 400002, 400003, 400004, 410000, 420000, 430000, 440000}
The first seven slices of the tetrahedron (or pyramid) are:
-----------------Slice 1-----------------
  1
-----------------Slice 2-----------------
    1
  1  3
-----------------Slice 3-----------------
      1
    1  3
  1  5  8
-----------------Slice 4-----------------
        1
      1  3
    1  5   8
  1  7  21  19
-----------------Slice 5-----------------
          1
        1  3
      1  5   8
    1  7  21  20
  1  9  40  81  43
-----------------Slice 6-----------------
              1
           1    3
        1    5     8
      1   7    21    20
    1   9   40    81    47
  1  11  65   208   295   94
-----------------Slice 7-----------------
                 1
              1     3
           1     5     8
         1    7     21    20
      1    9    40     81      48
    1   11   65    208     297     107
  1  13   96   425    1024    1037    201

Robert P. P. McKone, Antidiagonals n = 2..50, flattened

Cf. A340156 (r=2), A340242 (r=3).
Cf. A008466 (n=2, r=2), A186244 (n=3, r=2), A050231 (n=2, r=3), A231430 (n=3, r=3).
Cf. A005408, A003215, A005917, A022521, A022522, A022523, A022524, A022525, A022526, A022527, A022528, A022529, A022530, A022531, A022532, A022533, A022534, A022535, A022536, A022537, A022538, A022539, A022540 (k=x, r=1, where x is the x-th Nexus Number).
Cf. A000567 [(k=4, r=2),(k=5, r=3),(k=6, r=4),...,(k=x, r=x-2)].
Cf. A103532 [(k=6, r=3),(k=7, r=4),(k=8, r=5),...,(k=x, r=x-3)].

m[r_, n_] := Normal[With[{p = 1/n}, SparseArray[{Band[{1, 2}] -> p, {i_, 1} /; i <= r -> 1 - p, {r + 1, r + 1} -> 1}]]]; T[n_, k_, r_] := MatrixPower[m[r, n], k][[1, r + 1]]*n^k; DeleteCases[Transpose[PadLeft[Reverse[Table[T[n, k, r], {k, 2, 8}, {r, 2, k}, {n, 2, r}], 2]], 2 <-> 3], 0, 3] // Flatten

cp's OEIS Frontend

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

A340242 Square array read by upward antidiagonals: T(n,k) is the number of n-ary strings of length k containing 000.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A341050 Cube array read by upward antidiagonals ignoring zero and empty terms: T(n, k, r) is the number of n-ary strings of length k, containing r consecutive 0's.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica