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

1, 6, 25, 90, 300, 954, 2939, 8850, 26195, 76500, 221016, 632916, 1799125, 5082270, 14279725, 39935214, 111228804, 308681550, 853904015, 2355364650, 6480104231, 17786356776, 48715278000, 133167004200, 363372003625, 989900286774

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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

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.

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

References

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

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Jean-Luc Baril, Toufik Mansour, José L. Ramírez, and Mark Shattuck, Catalan words avoiding a pattern of length four, Univ. de Bourgogne (France, 2024). See p. 5.
• Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 4.
• Karl Dilcher and Larry Ericksen, Polynomials and algebraic curves related to certain binary and b-ary overpartitions, arXiv:2405.12024 [math.CO], 2024. See p. 10.
• Rigoberto Flórez, Robinson Higuita, and Alexander Ramírez, The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials, arXiv:1808.01264 [math.NT], 2018.
• Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Enumerating several aspects of non-decreasing Dyck paths, Discrete Mathematics, Vol. 342, Issue 11 (2019), 3079-3097. See page 3092.
• Rigoberto Flórez, Leandro Junes, Luisa M. Montoya, and José L. Ramírez, Counting Subwords in Non-Decreasing Dyck Paths, Journal of Integer Sequences, Vol. 28 (2025), Article 25.1.6. See pp. 6, 15, 17, 19.
• Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
• Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243, 2012. - From _N. J. A. Sloane_, May 09 2012
• Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
• Eunjeong Lee, Mikiya Masuda, and Seonjeong Park, On Schubert varieties of complexity one, arXiv:2009.02125 [math.AT], 2020.
• Valentin Ovsienko and Serge Tabachnikov, Dual numbers, weighted quivers, and extended Somos and Gale-Robinson sequences, arXiv:1705.01623 [math.CO], 2017. See p. 9.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
• John Riordan, Notes to N. J. A. Sloane, Jul. 1968
• John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
• Index entries for sequences related to Chebyshev polynomials.
• Index entries for two-way infinite sequences
• Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Crossrefs

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

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

Programs

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

Maple

f:= gfun:-rectoproc({a(n)=6*a(n-1)-11*a(n-2)+6*a(n-3)-a(n-4),
a(0)=1,a(1)=6,a(2)=25,a(3)=90},a(n),remember):
map(f, [$0..50]); # Robert Israel, May 05 2017
# alternative
A001871 := proc(n)
    option remember ;
    if n <= 3 then
        op(n+1,[1,6,25,90]) ;
    else
        6*procname(n-1)-11*procname(n-2)+6*procname(n-3)-procname(n-4) ;
    end if;
end proc:
seq(A001871(n),n=0..10) ; # R. J. Mathar, Dec 16 2024

Mathematica

CoefficientList[Series[1/(1-3x+x^2)^2,{x,0,40}],x] (* Vincenzo Librandi, Jun 10 2012 *)

PARI

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

PARI

Vec(1/(1-3*x+x^2)^2 + O(x^100)) \\ Altug Alkan, Oct 31 2015

Formula

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

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

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

G.f.: 1/(1 - 3*x + x^2)^2. - Simon Plouffe in his 1992 dissertation

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

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

a(n) = 6*a(n-1) - 11*a(n-2) + 6*a(n-3) - a(n-4). - Vincenzo Librandi, Mar 14 2011

a(n) = 2*A001870(n) - A238846(n). - Philippe Deléham, Mar 06 2014

a(n) ~ (7 + 3*sqrt(5))*n*cos(n*arccos(3/2))/5. - Stefano Spezia, Mar 29 2022

From Peter Bala, Nov 05 2024: (Start)

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

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

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)

E.g.f.: exp(3*x/2)*(5*(5 + 18*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(9 + 40*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Mar 04 2025

Extensions

Additional comments from Wolfdieter Lang, Apr 07 2000