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

A072335 Expansion of 1/((1-x^2)(1-4x+x^2)).

Original entry on oeis.org

1, 4, 16, 60, 225, 840, 3136, 11704, 43681, 163020, 608400, 2270580, 8473921, 31625104, 118026496, 440480880, 1643897025, 6135107220, 22896531856, 85451020204, 318907548961, 1190179175640, 4441809153600, 16577057438760, 61866420601441, 230888624967004

Offset: 0

N. J. A. Sloane, Jul 15 2002

M. R. Bremner, Free associative algebras, noncommutative Grobner bases, and universal associative envelopes for nonassociative structures, arXiv preprint arXiv:1303.0920, 2013
N. J. A. Sloane, Transforms
Index entries for sequences related to Chebyshev polynomials.
Index entries for linear recurrences with constant coefficients, signature (4,0,-4,1).

EULER transform of A072279 (with its initial 1 omitted).
A001353(n)^2 is a bisection of a(n).
Cf. A225682.

CoefficientList[Series[1/((1-x^2)*(1-4x+x^2)),{x,0,30}],x] (* or *) LinearRecurrence[{4,0,-4,1},{1,4,16,60},30] (* Harvey P. Dale, Aug 22 2015 *)

Vec(1/((1-x^2)*(1-4*x+x^2))+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

a(n) = (1/12)*((7-4*sqrt(3))*(2-sqrt(3))^n+(7+4*sqrt(3))*(2+sqrt(3))^n-3+(-1)^n). Recurrence: a(n) = 4*a(n-1)-4*a(n-3)+a(n-4).
a(n)=sum{k=0..floor(n/2), U(n-2k, 2)} - Paul Barry, Nov 15 2003
The g.f. can also be written as 1/(1-4*x+4*x^3-x^4), which relates this sequence to the family of sequences described in A225682.

A200781 G.f.: 1/(1-5x+10x^3-5*x^4).

Original entry on oeis.org

1, 5, 25, 115, 530, 2425, 11100, 50775, 232275, 1062500, 4860250, 22232375, 101698250, 465201250, 2127983750, 9734098125, 44526969375, 203681015625, 931704015625, 4261920875000, 19495429065625, 89178510250000, 407931862578125, 1866014626609375, 8535765175875000, 39045399804843750, 178606512071015625, 817004981729375000

Offset: 0

R. H. Hardin, Nov 22 2011

nonn

Number of words of length n over an alphabet of size 5 which do not contain any strictly decreasing factor (consecutive subword) of length 3. For alphabets of size 2, 3, 4, 6 see A000079, A076264, A072335, A200782.

Equivalently, number of 0..4 arrays x(0..n-1) of n elements without any two consecutive increases.

			Some solutions for n=5:
..1....3....4....0....1....0....4....0....2....1....4....1....2....2....4....4
..3....4....4....2....1....0....3....3....1....4....1....1....4....4....3....3
..3....1....0....2....0....2....0....3....3....0....4....3....0....1....4....4
..2....0....2....4....4....0....3....2....0....0....3....2....0....2....1....3
..4....4....2....2....0....3....3....2....1....0....4....1....3....1....0....2

R. H. Hardin and N. J. A. Sloane, Table of n, a(n) for n = 0..249 [The first 210 terms were computed by R. H. Hardin]
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14. See Th. 3.13.
Index entries for linear recurrences with constant coefficients, signature (5,0,-10,5).

The g.f. corresponds to row 5 of triangle A225682.
Column 4 of A200785.
Cf. A076264, A072335, A200782.

Vec(1/(1-5*x+10*x^3-5*x^4) + O(x^30)) \\ Jinyuan Wang, Mar 10 2020

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

Edited by N. J. A. Sloane, May 21 2013

A200782 Expansion of 1 / (1 - 6x + 20x^3 - 15*x^4 + x^6).

Original entry on oeis.org

1, 6, 36, 196, 1071, 5796, 31395, 169884, 919413, 4975322, 26924106, 145698840, 788446400, 4266656226, 23088902733, 124944995676, 676136621430, 3658895818470, 19800020091895, 107147296401684, 579824822459421, 3137707025200000

Offset: 0

R. H. Hardin, Nov 22 2011

a(n) is the number of words of length n over an alphabet of size 6 which do not contain any strictly decreasing factor (consecutive subword) of length 3.
Equivalently, dimensions of homogeneous components of the universal associative envelope for a certain nonassociative triple system [Bremner].
This is the g.f. corresponding to row 6 of A225682.

			a(n) is also the number of words of length n over an alphabet of size 6 which do not contain any strictly increasing factor of length 3. Some solutions for n=5:
..5....5....0....3....2....4....3....3....3....3....0....3....3....1....0....1
..1....5....0....0....4....5....1....1....3....5....1....0....2....0....3....4
..3....5....1....0....4....3....1....4....5....0....1....5....1....0....0....3
..0....0....0....4....1....1....1....4....2....4....1....1....2....5....4....1
..1....4....2....0....0....0....1....3....1....4....3....2....2....2....4....5

R. H. Hardin and N. J. Sloane, Table of n, a(n) for n = 0..239 [The first 210 terms were computed by R. H. Hardin]
M. R. Bremner, Free associative algebras, noncommutative Grobner bases, and universal associative envelopes for nonassociative structures, arXiv:1303.0920 [math.RA], 2013
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14. See Th. 3.13.
Index entries for linear recurrences with constant coefficients, signature (6,0,-20,15,0,-1).

Column 5 of A200785.

G.f. corresponds to row 6 of A225682.

CoefficientList[Series[1 / (1 - 6*x + 20*x^3 - 15*x^4 + x^6), {x, 0, 20}], x] (* Vaclav Kotesovec, Jan 26 2015 *)
LinearRecurrence[{6,0,-20,15,0,-1},{1,6,36,196,1071,5796},30] (* Harvey P. Dale, Jul 28 2019 *)

Vec(1/(1-6*x+20*x^3-15*x^4+x^6) + O(x^30)) \\ Michel Marcus, Jan 26 2015

G.f.: 1 / (1 - 6*x + 20*x^3 - 15*x^4 + x^6).

a(n) = 6*a(n-1) - 20*a(n-3) + 15*a(n-4) - a(n-6).

Entry revised by N. J. A. Sloane, May 17 2013, merging this with A225381

Typo in name corrected by Michel Marcus, Jan 26 2015

A200783 G.f.: 1/(1-7x+35x^3-35x^4+7x^6-x^7).

Original entry on oeis.org

1, 7, 49, 308, 1946, 12152, 75992, 474566, 2964416, 18514405, 115637431, 722234149, 4510869636, 28173535572, 175963587528, 1099016234232, 6864129384252, 42871313869692, 267761500599901, 1672358840069239, 10445056851917149, 65236724277810632, 407449213173792062, 2544806826734163992, 15894107968042546424, 99269879914558590146

Offset: 0

R. H. Hardin Nov 22 2011

nonn

Number of words of length n over an alphabet of size 7 which do not contain any strictly decreasing factor (consecutive subword) of length 3.

Number of 0..6 arrays x(0..n-1) of n elements without any two consecutive increases.

			Some solutions for n=5
..6....2....6....3....4....4....6....6....5....3....2....4....5....0....5....5
..4....5....0....4....1....6....4....5....1....1....2....6....6....6....3....6
..4....4....0....4....5....3....5....5....5....1....5....3....3....6....4....2
..3....6....2....5....5....2....2....4....5....5....3....3....2....1....4....5
..4....5....0....3....1....0....4....3....5....5....2....1....0....0....5....3

R. H. Hardin and N. J. Sloane, Table of n, a(n) for n = 0..249 [The first 210 terms were computed by R. H. Hardin]
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14. See Th. 3.13.
Index entries for linear recurrences with constant coefficients, signature (7, 0, -35, 35, 0, -7, 1).

Column 6 of A200785.

G.f. corresponds to row 7 of A225682.

CoefficientList[Series[1/(1-7x+35x^3-35x^4+7x^6-x^7),{x,0,30}],x] (* or *) LinearRecurrence[{7,0,-35,35,0,-7,1},{1,7,49,308,1946,12152,75992},30] (* Harvey P. Dale, Jul 23 2014 *)

a(n) = 7*a(n-1) - 35*a(n-3) + 35*a(n-4) - 7*a(n-6) + a(n-7).

Edited by N. J. A. Sloane, May 21 2013

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

A072335 Expansion of 1/((1-x^2)*(1-4*x+x^2)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A200781 G.f.: 1/(1-5*x+10*x^3-5*x^4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A200782 Expansion of 1 / (1 - 6*x + 20*x^3 - 15*x^4 + x^6).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A200783 G.f.: 1/(1-7*x+35*x^3-35*x^4+7*x^6-x^7).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A072335 Expansion of 1/((1-x^2)(1-4x+x^2)).

A200781 G.f.: 1/(1-5x+10x^3-5*x^4).

A200782 Expansion of 1 / (1 - 6x + 20x^3 - 15*x^4 + x^6).

A200783 G.f.: 1/(1-7x+35x^3-35x^4+7x^6-x^7).