

A076264


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


22



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

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(n2)*rho(9) + b(n1)*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 9gon. 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 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


REFERENCES

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


LINKS

Harvey P. Dale, Table of n, a(n) for n = 0..1000
L. J. Guibas and A. M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981), 183208. [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]
Index entries for linear recurrences with constant coefficients, signature (3,0,1).


FORMULA

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(n1)  a(n3), n > 0.
a(n) = Sum_{k=0..floor(n/3)} binomial(n2k, k)(1)^k*3^(n3k).  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


EXAMPLE

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 + ...


MATHEMATICA

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


PROG

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


CROSSREFS

The g.f. corresponds to row 3 of triangle A225682.
Sequence in context: A171277 A289806 A000243 * A018919 A123941 A005774
Adjacent sequences: A076261 A076262 A076263 * A076265 A076266 A076267


KEYWORD

nonn,easy


AUTHOR

John L. Drost, Nov 05 2002


STATUS

approved



