login
a(0)=1, a(1)=2, a(2)=5, a(n) = 3*a(n+2) - a(n+3).
3

%I #49 May 14 2024 17:26:58

%S 1,2,5,14,40,115,331,953,2744,7901,22750,65506,188617,543101,1563797,

%T 4502774,12965221,37331866,107492824,309513251,891207887,2566130837,

%U 7388879260,21275429893,61260158842,176391597266,507899361905

%N a(0)=1, a(1)=2, a(2)=5, a(n) = 3*a(n+2) - a(n+3).

%C Equals the INVERT transform of the Pell sequence prefaced with a "1": (1, 1, 2, 5, 12, 29, ...). - _Gary W. Adamson_, May 01 2009

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1034">Encyclopedia of Combinatorial Structures 1034</a>

%H Elena Barcucci, Antonio Bernini, and Renzo Pinzani, <a href="https://doi.org/10.1051/ita/2024007">Sequences from Fibonacci to Catalan: A combinatorial interpretation via Dyck paths</a>, RAIRO-Theor. Inf. Appl. (2024) Vol. 58, Art. No. 8. See p. 14.

%H Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, <a href="https://arxiv.org/abs/2405.05357">Flattened Catalan Words</a>, arXiv:2405.05357 [math.CO], 2024. See p. 14.

%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="https://www.emis.de/journals/INTEGERS/papers/p16/p16.Abstract.html">Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II</a>, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16; <a href="http://arxiv.org/abs/1302.2274">arXiv preprint</a>, arXiv:1302.2274 [math.CO], 2013.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,0,-1).

%F G.f.: -(-1+x+x^2)/(1-3*x+x^3).

%F a(n) = Sum((1/9)*(1+2*_alpha+_alpha^2)*_alpha^(-1-n), _alpha=RootOf(1-3*_Z+_Z^3)). [in Maple notation]

%F a(n)/a(n-1) tends to 2.8793852... = 1/(2*cos(4*Pi/9)), a root of x^3 -3x^2 + 1 (the characteristic polynomial of the 3 X 3 matrix). The latter polynomial is a factor (with (x + 1)) of the 4th degree polynomial of A066170: x^4 - 2x^3 - 3x^2 + x + 1. Given the 3 X 3 matrix [0 1 0 / 0 0 1 / -1 0 3], (M^n)*[1 1 1] = [a(n-2), a(n-1), a(n)]. - _Gary W. Adamson_, Feb 29 2004

%F a(n) = A076264(n)-A076264(n-1)-A076264(n-2). - _R. J. Mathar_, Feb 27 2019

%p spec := [S,{S=Sequence(Union(Prod(Sequence(Union(Prod(Z,Z),Z)),Z),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);

%t LinearRecurrence[{3,0,-1},{1,2,5},30] (* _Harvey P. Dale_, Dec 26 2015 *)

%Y Cf. A066170, A076264.

%K easy,nonn

%O 0,2

%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000

%E More terms from _James A. Sellers_, Jun 05 2000