A274018 -id:A274018 - cp's OEIS frontend

A076264 Number of ternary (0,1,2) sequences without a consecutive '012'.

1, 3, 9, 26, 75, 216, 622, 1791, 5157, 14849, 42756, 123111, 354484, 1020696, 2938977, 8462447, 24366645, 70160958, 202020427, 581694636, 1674922950, 4822748423, 13886550633, 39984728949, 115131438424, 331507764639

Offset: 0

John L. Drost, Nov 05 2002

A transform of A000244 under the mapping g(x)->(1/(1+x^3))g(x/(1+x^3)). - Paul Barry, Oct 20 2004
b(n) := (-1)^n*a(n) appears in the formula for the nonpositive powers of rho(9) := 2*cos(Pi/9), when written in the power basis of the algebraic number field Q(rho(9)) of degree 3. See A187360 for the minimal polynomial C(9, x) of rho(9), and a link to the Q(2*cos(pi/n)) paper. 1/rho(9) = -3*1 + 0*rho(9) + 1*rho(9)^2 (see A230079, row n=5). 1/rho(9)^n = b(n)*1 + b(n-2)*rho(9) + b(n-1)*rho(9)^2, n >= 0, with b(-1) = 0 = b(-2). - Wolfdieter Lang, Nov 04 2013
The limit b(n+1)/b(n) = -a(n+1)/a(n) for n -> infinity is -tau(9) := -(1 + rho(9)) = 1/(2*cos(Pi*5/9)), approximately -2.445622407. tau(9) is known to be the length ratio (longest diagonal)/side in the regular 9-gon. This limit follows from the b(n)-recurrence and the solutions of X^3 + 3*X^2 - 1 = 0, which are given by the inverse of the known solutions of the minimal polynomial C(9, x) of rho(9) (see A187360). The other two X solutions are 1/rho(9) = -3 + rho(9)^2, approximately 0.5320888860 and 1/(2*cos(Pi*7/9)) = 1 + rho(9) - rho(9)^2, approximately -0.6527036445, and they are therefore irrelevant for this sequence. - Wolfdieter Lang, Nov 08 2013
a(n) is also the number of ternary (0,1,2) sequences of length n without a consecutive '110' because the patterns A=012 and B=110 have the same autocorrelation, i.e., AA=100=BB, in the sense of Guibas and Odlysko (1981). (A cyclic version of this sequence can be found in sequence A274018.) - Petros Hadjicostas, Sep 12 2017

			1/rho(9)^3 = -26*1 - 3*rho(9) + 9*rho(9)^2, (approximately 0.15064426) with rho(9) given in the Nov 04 2013 comment above. - _Wolfdieter Lang_, Nov 04 2013
G.f. = 1 + 3*x + 9*x^2 + 26*x^3 + 75*x^4 + 216*x^5 + 622*x^6 + 1791*x^7 + ...

A. Tucker, Applied Combinatorics, 4th ed. p. 277

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Taras Goy and Mark Shattuck, Toeplitz-Hessenberg determinant formulas for the sequence F_n-1, Online J. Anal. Comb. (2025) Vol. 19, Paper 1, 1-26. See p. 12.
Leo J. Guibas and Andrew M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981), 183-208. [Comment: The authors use generating functions in terms of z^{-1}. To get the g.f. of the sequence, as shown below in the FORMULA section, let x=z^{-1} and perform simple algebra. There are some minor typos in Theorem 2.1, p. 191, that can be easily corrected by looking at the proof. - _Petros Hadjicostas_, Sep 12 2017]
Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee, and Jung Hoon Han, Proposal of a spin-one chain model with competing dimer and trimer interactions, arXiv:1709.01344 [cond-mat.str-el], 2017.
Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

The g.f. corresponds to row 3 of triangle A225682.

List([0..25],n->Sum([0..Int(n/3)],k->Binomial(n-2*k,k)*(-1)^k*3^(n-3*k))); # Muniru A Asiru, Feb 20 2018

LinearRecurrence[{3,0,-1},{1,3,9},30] (* Harvey P. Dale, Feb 28 2016 *)

{a(n) = if( n<0, 0, polcoeff( 1 / (1 - 3*x + x^3) + x * O(x^n), n))};

a(n) is asymptotic to g*c^n where c = cos(Pi/18)/cos(7*Pi/18) and g is the largest real root of 81*x^3 - 81*x^2 - 9*x + 1 = 0. - Benoit Cloitre, Nov 06 2002
G.f.: 1/(1 - 3x + x^3).
a(n) = 3*a(n-1) - a(n-3), n > 0.
a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k, k)(-1)^k*3^(n-3k). - Paul Barry, Oct 20 2004
a(n) = middle term in M^(n+1) * [1 0 0], where M = the 3 X 3 matrix [2 1 1 / 1 1 0 / 1 0 0]. Right term = A052536(n), left term = A052536(n+1). - Gary W. Adamson, Sep 05 2005

A215885 a(n) = 3*a(n-1) - a(n-3), with a(0) = 3, a(1) = 3, and a(2) = 9.

Original entry on oeis.org

3, 3, 9, 24, 69, 198, 570, 1641, 4725, 13605, 39174, 112797, 324786, 935184, 2692755, 7753479, 22325253, 64283004, 185095533, 532961346, 1534601034, 4418707569, 12723161361, 36634883049, 105485941578, 303734663373, 874569107070, 2518221379632, 7250929475523

Offset: 0

Roman Witula, Aug 25 2012

The Berndt-type sequence number 5a for the argument 2Pi/9 defined by the first relation from the section "Formula". We see that a(n) is equal to the sum of the n-th negative powers of the c(j) := 2*cos(2*Pi*j/9), j=1,2,4 (the A215664(n) is equal to the respective n-th positive powers, further both sequences can be obtained from the two-sided recurrence relation: X(n+3) = 3*X(n+1) - X(n), n in Z, with X(-1) = X(0) = 3, and X(1) = 0).
From the last formula in Witula's comments to A215664 it follows that 2*(-1)^n*a(n) = A215664(n)^2 - A215664(2*n).
The following decomposition holds true: (X - c(1)^(-n))*(X - c(2)^(-n))*(X - c(4)^(-n)) = X^3 - a(n)*X^2 - (-1)^n*A215664(n)*X - (-1)^n.
For n >= 1, a(n) is the number of cyclic (0,1,2)-compositions of n that avoid the pattern 110 provided the positions of the parts of the composition on the circle are fixed. (Similar comments hold for the pattern 012 and for the pattern 001.) - Petros Hadjicostas, Sep 13 2017
See the Maple program by Edlin and Zeilberger for counting the q-ary cyclic compositions of n that avoid one or more patterns provided the positions of the parts of the composition are fixed on the circle. The program is located at D. Zeilberger's personal website (see links). For the sequence here, q=3 and the pattern is A=110. - Petros Hadjicostas, Sep 13 2017

			For n=3, we have a(3) = 3^3 - 3 = 24 ternary cyclic compositions of n=3 (with fixed positions on the circle for the parts) that avoid 110 because we have to exclude 110, 101, and 011. - _Petros Hadjicostas_, Sep 13 2017

Michael De Vlieger, Table of n, a(n) for n = 0..1999
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math. 25 (2000), 228-232.
A. E. Edlin and D. Zeilberger, Maple program; Local copy
Kai Wang, Fibonacci Numbers And Trigonometric Functions Outline, (2019).
Roman Witula, Ramanujan Type Trigonometric Formulae, Demonstratio Math. 45 (2012), 779-796.
Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

Cf. A130880, A147704, A215664, A215665, A215666, A274018.

Mathematica
```
LinearRecurrence[{3,0,-1}, {3,3,9}, 50]
```

my(x='x+O('x^30)); Vec(3*(1-2*x)/(1-3*x+x^3)) \\ Altug Alkan, Sep 13 2017

a(n) = 3*A147704(n).
a(n) = c(1)^(-n) + c(2)^(-n) + c(4)^(-n) = (-c(1)*c(2))^n + (-c(1)*c(4))^n + (-c(2)*c(4))^n, where c(j) := 2*cos(2*Pi*j/9).
G.f.: Sum_{n>=0} a(n)*x^n = 3-3*x*(x^2-1)/(1-3*x+x^3) = 3*(1-2*x)/(1-3*x+x^3).
G.f. of Edlin and Zeilberger (2000): 1+Sum_{n>=1} a(n)*x^n = 1-3*x*(x^2-1)/(1-3*x+x^3) = (1-2*x^3)/(1-3*x+x^3). - Petros Hadjicostas, Sep 13 2017
a(n) = ceiling(r^n) for n >= 1, where r = 1/A130880 is the largest root of x^3 - 3*x^2 + 1. - Tamas Lengyel, Feb 20 2022

A274017 Number of n-bead binary necklaces (no turning over allowed) that avoid the subsequence 110.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 6, 6, 9, 11, 16, 20, 32, 42, 65, 95, 144, 212, 330, 494, 767, 1171, 1812, 2788, 4342, 6714, 10463, 16275, 25416, 39652, 62076, 97110, 152289, 238839, 375168, 589528, 927556, 1459962, 2300349, 3626243, 5721046, 9030452, 14264310, 22542398, 35646313, 56393863, 89264836, 141358276, 223959712

Offset: 0

Marko Riedel, Jun 06 2016

nonn

The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).

The proofs of all my formulas below become evident once it is realized that A001612(n) gives the number of cyclic sequences of length n consisting of zeros and ones that avoid the pattern 001 (or equivalently, the pattern 110) provided the positions of zeros and ones on a circle are fixed. Everything else follows from the material that can be found in A001612. - Petros Hadjicostas, Jan 11 2017

			The following necklace
     1-1
    /   \
   0     0
   |     |
   1     1
    \   /
     0-0
contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.
a(8) = 9: 00000000, 00000001, 00000101, 00001001, 00010001, 00010101, 00100101, 01010101, 11111111.
a(9) = 11: 000000000, 000000001, 000000101, 000001001, 000010001, 000010101, 000100101, 000101001, 001001001, 001010101, 111111111.

Petros Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
Petros Hadjicostas, Proof of two formulas for a(n).
Marko Riedel, Maple code for this sequence.
Math Stackexchange, Marko Riedel et al. Counting circular sequences.

Cf. A000010, A000031, A000045, A000204, A000358, A001612, A093305, A274018, A274019, A274020.

From Petros Hadjicostas, Jan 11 2017: (Start)
For all the formulas below, assume n>=1.
a(n) = 1 + A000358(n). (Notice the different offsets.)
a(n) = 1 + (1/n) * Sum_{d|n} totient(n/d)*(Fibonacci(d-1)+Fibonacci(d+1)).
a(n) = (1/n) * Sum_{d divides n} totient(n/d)*A001612(d).
G.f.: 1/(1-x) + Sum_{k>=1} (phi(k)/k) * log(1/(1-B(x^k))) where B(x) = x*(1+x). (This is a modification of a formula due to Joerg Arndt.)
G.f.: 1 + Sum_{k>=1} (phi(k)/k) * log(1/C(x^k)) where C(x) = (1-x)*(1-B(x)). (End)
a(n) = 1 + (1/n) * Sum_{d|n} A000010(n/d)*A000204(d). [After the second formula above given by Hadjicostas]. - Antti Karttunen, Jan 12 2017

A274019 Number of n-bead quaternary necklaces (no turning over allowed) that avoid the subsequence 110.

Original entry on oeis.org

1, 4, 10, 23, 66, 192, 636, 2092, 7228, 25175, 89212, 318808, 1150444, 4177908, 15268494, 56078527, 206903020, 766342160, 2848351388, 10619472284, 39702648534, 148806583111, 558999381656, 2104255629608, 7936108068008, 29982733437844, 113456750715426, 429964269551767, 1631663320986086

Offset: 0

Marko Riedel, Jun 06 2016

nonn

The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).

Because A(x) = Sum_{n>=1} a(n)*x^n = 1 - Sum_{n>=1} (phi(n)/n)*log(1-B(x^n)), where B(x) = q*x - x^3 and q = 4, we may find sequence (c(n): n>=1) that satisfies a(n) = (1/n)*Sum_{d|n} phi(n/d)*c(d) for n>=1 by using the formula Sum_{n>=1} c(n)*x^n = C(x) = x*(dB/dx)/(1-B(x)). In our case, C(x) = x*(d(q*x-x^3)/dx)/(1-(q*x-x^3)) = (q*x - 3*x^3)/(1 - q*x + x^3). This implies that c(1) = q, c(2) = q^2, c(3) = q^3 - 3, and c(n) = q*c(n-1) - c(n-3) for n>=4. This comment applies not only to this sequence, but also to sequences A274017, A274018 and A274020 as well (corresponding to cases q=2, 3, and 5, respectively). - Petros Hadjicostas, Jan 31 2018

			The following necklace
.   1-1
.  /   \
. 0     0
. |     |
. 1     3
.  \   /
.   0-2
contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.

P. Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
Math Stackexchange, Marko Riedel et al., Counting circular sequences.
Marko Riedel, Maple code for this sequence.

Cf. A000031, A274017, A274018, A274020.

G.f.: 1 - Sum_{n>=1} (phi(n)/n)*log(x^(3*n)-q*x^n+1), where q=4 is the number of symbols in the alphabet we are using. - Petros Hadjicostas, Sep 12 2017

Define sequence (c(n): n>=1) by c(1) = q, c(2) = q^2, c(3) = q^3-3, and c(n) = q*c(n-1) - c(n-3) for n>=4. Then a(n) = (1/n)*Sum_{d|n} phi(n/d)*c(d) for n>=1. (Here q=4.) - Petros Hadjicostas, Jan 29 2018

A274020 Number of n-bead 5-ary necklaces (no turning over allowed) that avoid the subsequence 110.

Original entry on oeis.org

1, 5, 15, 44, 160, 604, 2510, 10545, 45825, 201669, 900307, 4057625, 18447565, 84444000, 388878560, 1799985435, 8368841895, 39062428790, 182961584260, 859612223990, 4049955449888, 19128675877279, 90553562670495, 429560546547595, 2041573370075675, 9719864998575489, 46350124359578975, 221352533355568044

Offset: 0

Marko Riedel, Jun 06 2016

nonn

The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).

			The following necklace:
.    1-1
.   /   \
.  0     0
.  |     |
.  1     3
.   \   /
.    2-4
contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.

P. Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern", Discrete Mathematics, 341 (2018), 1662-1674.
Math Stackexchange, Marko Riedel et al., Counting circular sequences.
Marko Riedel, Maple code for this sequence.

Cf. A000031, A274017, A274018, A274019.

G.f.: 1 - Sum_{n>=1} (phi(n)/n)*log(x^(3*n)-q*x^n+1), where q=5 is the number of symbols in the alphabet we are using. - Petros Hadjicostas, Sep 12 2017

Define sequence (c(n): n>=1) by c(1) = q, c(2) = q^2, c(3) = q^3-3, and c(n) = q*c(n-1) - c(n-3) for n>=4. Then a(n) = (1/n)*Sum_{d|n} phi(n/d)*c(d) for n>=1. (Here q=5.) - Petros Hadjicostas, Jan 29 2018

cp's OEIS Frontend

A076264 Number of ternary (0,1,2) sequences without a consecutive '012'.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Formula

A215885 a(n) = 3*a(n-1) - a(n-3), with a(0) = 3, a(1) = 3, and a(2) = 9.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A274017 Number of n-bead binary necklaces (no turning over allowed) that avoid the subsequence 110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A274019 Number of n-bead quaternary necklaces (no turning over allowed) that avoid the subsequence 110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A274020 Number of n-bead 5-ary necklaces (no turning over allowed) that avoid the subsequence 110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula