%I #65 Feb 20 2018 21:10:48
%S 1,3,9,26,75,216,622,1791,5157,14849,42756,123111,354484,1020696,
%T 2938977,8462447,24366645,70160958,202020427,581694636,1674922950,
%U 4822748423,13886550633,39984728949,115131438424,331507764639
%N Number of ternary (0,1,2) sequences without a consecutive '012'.
%C A transform of A000244 under the mapping g(x)->(1/(1+x^3))g(x/(1+x^3)). - _Paul Barry_, Oct 20 2004
%C 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
%C 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
%C 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
%D A. Tucker, Applied Combinatorics, 4th ed. p. 277
%H Harvey P. Dale, <a href="/A076264/b076264.txt">Table of n, a(n) for n = 0..1000</a>
%H L. J. Guibas and A. M. Odlyzko, <a href="https://doi.org/10.1016/0097-3165(81)90005-4">String overlaps, pattern matching, and nontransitive games</a>, 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]
%H Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee, Jung Hoon Han, <a href="https://arxiv.org/abs/1709.01344">Proposal of a spin-one chain model with competing dimer and trimer interactions</a>, arXiv:1709.01344 [cond-mat.str-el], 2017.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-1).
%F 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
%F G.f.: 1/(1 - 3x + x^3).
%F a(n) = 3*a(n-1) - a(n-3), n > 0.
%F a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k, k)(-1)^k*3^(n-3k). - _Paul Barry_, Oct 20 2004
%F 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
%e 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
%e G.f. = 1 + 3*x + 9*x^2 + 26*x^3 + 75*x^4 + 216*x^5 + 622*x^6 + 1791*x^7 + ...
%t LinearRecurrence[{3,0,-1},{1,3,9},30] (* _Harvey P. Dale_, Feb 28 2016 *)
%o (PARI) {a(n) = if( n<0, 0, polcoeff( 1 / (1 - 3*x + x^3) + x * O(x^n), n))};
%o (GAP) 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
%Y The g.f. corresponds to row 3 of triangle A225682.
%K nonn,easy
%O 0,2
%A _John L. Drost_, Nov 05 2002