%I M4166 N1733 #138 Nov 06 2024 10:19:22

%S 1,6,25,90,300,954,2939,8850,26195,76500,221016,632916,1799125,

%T 5082270,14279725,39935214,111228804,308681550,853904015,2355364650,

%U 6480104231,17786356776,48715278000,133167004200,363372003625,989900286774

%N Expansion of 1/(1 - 3*x + x^2)^2.

%C Convolution of A001906(n), n >= 1 (even-indexed Fibonacci numbers) with itself.

%C A001787 and this sequence arise in counting ordered trees of height at most k where only the rightmost branch at the root actually achieves this height and the count is by the number of edges, with k = 3 for A001787 and k = 4 for this sequence.

%C Gives the number of 3412-avoiding permutations containing exactly one subsequence of type 321. - Dan Daly (ddaly(AT)du.edu), Apr 24 2008

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A001871/b001871.txt">Table of n, a(n) for n = 0..1000</a>

%H Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, <a href="http://jl.baril.u-bourgogne.fr/bmrs.pdf">Catalan words avoiding a pattern of length four</a>, Univ. de Bourgogne (France, 2024). See p. 5.

%H Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, <a href="https://arxiv.org/abs/2203.13205">Honeycombs in the Pascal triangle and beyond</a>, arXiv:2203.13205 [math.HO], 2022. See p. 4.

%H Karl Dilcher and Larry Ericksen, <a href="https://arxiv.org/abs/2405.12024">Polynomials and algebraic curves related to certain binary and b-ary overpartitions</a>, arXiv:2405.12024 [math.CO], 2024. See p. 10.

%H Rigoberto Flórez, Robinson Higuita, and Alexander Ramírez, <a href="https://arxiv.org/abs/1808.01264">The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials</a>, arXiv:1808.01264 [math.NT], 2018.

%H Rigoberto Flórez, Leandro Junes, and José L. Ramírez, <a href="https://doi.org/10.1016/j.disc.2019.06.018">Enumerating several aspects of non-decreasing Dyck paths</a>, Discrete Mathematics, Vol. 342, Issue 11 (2019), 3079-3097. See page 3092.

%H Ricardo Gómez Aíza, <a href="https://arxiv.org/abs/2402.16111">Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis</a>, arXiv:2402.16111 [math.CO], 2024. See p. 23.

%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I</a>, arXiv preprint arXiv:1201.6243, 2012. - From _N. J. A. Sloane_, May 09 2012

%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://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:1302.2274</a>)

%H Eunjeong Lee, Mikiya Masuda, and Seonjeong Park, <a href="https://arxiv.org/abs/2009.02125">On Schubert varieties of complexity one</a>, arXiv:2009.02125 [math.AT], 2020.

%H Valentin Ovsienko and Serge Tabachnikov, <a href="https://arxiv.org/abs/1705.01623">Dual numbers, weighted quivers, and extended Somos and Gale-Robinson sequences</a>, arXiv:1705.01623 [math.CO], 2017. See p. 9.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H John Riordan, <a href="/A001820/a001820.pdf">Notes to N. J. A. Sloane, Jul. 1968</a>

%H John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.

%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>

%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>

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

%F a(n) = (2*(2*n+1)*F(2*(n+1))+3*(n+1)*F(2*n+1))/5 with F(n) = A000045 (Fibonacci numbers).

%F a(n) = -a(-4-n) = ((4*n+2)*F(2*n) + (7*n+5)*F(2*n+1))/5 with F(n) = A000045 (Fibonacci numbers).

%F a(n) = (2*a(n-1) + (n+1)*F(2n+4))/3, where F(n) = A000045 (Fibonacci numbers). - _Emeric Deutsch_, Oct 08 2002

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

%F a(n) = (Sum_{k=0..n} S(k, 3)*S(n-k, 3)), where S(n, x) = U(n, x/2) is the n-th Chebyshev polynomial of the 2nd kind, A049310. - _Paul Barry_, Nov 14 2003

%F a(n) = Sum_{k=1..n+1} F(2k)*F(2(n-k+2)), where F(k) is the k-th Fibonacci number. - Dan Daly (ddaly(AT)du.edu), Apr 24 2008

%F a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4). - _Vincenzo Librandi_, Mar 14 2011

%F a(n) = 2*A001870(n) - A238846(n). - _Philippe Deléham_, Mar 06 2014

%F a(n) ~ (7 + 3*sqrt(5))*n*cos(n*arccos(3/2))/5. - _Stefano Spezia_, Mar 29 2022

%F From _Peter Bala_, Nov 05 2024: (Start)

%F a(n) = Sum_{k = 0..n} (n + 2*k + 1)*binomial(n+k, 2*k).

%F a(n) = (n+1) * hypergeom([-n, n+1, (n+3)/2], [1/2, (n+1)/2], -1/4).

%F Second-order recurrence: n*a(n) = 3*(n + 1)*a(n-1) - (n + 2)*a(n-2) with a(0) = 1 and a(1) = 6. (End)

%p A001871:=1/(z**2-3*z+1)**2; # _Simon Plouffe_ in his 1992 dissertation

%p f:= gfun:-rectoproc({a(n)=6*a(n-1)-11*a(n-2)+6*a(n-3)-a(n-4),

%p a(0)=1,a(1)=6,a(2)=25,a(3)=90},a(n),remember):

%p map(f, [$0..50]); # _Robert Israel_, May 05 2017

%t CoefficientList[Series[1/(1-3x+x^2)^2,{x,0,40}],x] (* _Vincenzo Librandi_, Jun 10 2012 *)

%o (PARI) a(n)=((4*n+2)*fibonacci(2*n)+(7*n+5)*fibonacci(2*n+1))/5

%o (Magma) I:=[1, 6, 25, 90]; [n le 4 select I[n] else 6*Self(n-1)-11*Self(n-2)+6*Self(n-3)-Self(n-4): n in [1..30]]; // _Vincenzo Librandi_, Jun 10 2012

%o (PARI) Vec(1/(1-3*x+x^2)^2 + O(x^100)) \\ _Altug Alkan_, Oct 31 2015

%Y Partial sums of A001870 (one half of odd-indexed A001629(n), n >= 2, Fibonacci convolution).

%Y Cf. A000045, A000051, A001629, A001820, A001906, A002720, A049310, A238846.

%K nonn,easy,changed

%O 0,2

%A _N. J. A. Sloane_

%E Additional comments from _Wolfdieter Lang_, Apr 07 2000