A071101 Expansion of (5 + 6*x + 3*x^2 - 2*x^3) / (1 - 2*x - 2*x^2 - 2*x^3 + x^4) in powers of x.

5, 16, 45, 130, 377, 1088, 3145, 9090, 26269, 75920, 219413, 634114, 1832625, 5296384, 15306833, 44237570, 127848949, 369490320, 1067846845, 3086134658, 8919094697, 25776662080, 74495936025, 215297250946, 622220603405, 1798250918672, 5197041610021

Offset: 0

Author

N. J. A. Sloane, May 28 2002

Keywords

• nonn
• easy

Comments

Number of tilings of the 2-mod-4 pillow of order n is a perfect square times a(n). [Propp, 1999, p. 272]

Examples

			G.f. = 5 + 16*x + 45*x^2 + 130*x^3 + 377*x^4 + 1088*x^5 + 3145*x^6 + 9090*x^7 + ...
		

References

• J. Propp, Enumeration of matchings: problems and progress, pp. 255-291 in L. J. Billera et al., eds, New Perspectives in Algebraic Combinatorics, Cambridge, 1999 (see Problem 12).

Links

• A.H.M. Smeets, Table of n, a(n) for n = 0..2169
• J. Propp, Updated article
• J. Propp, Enumeration of matchings: problems and progress, in L. J. Billera et al. (eds.), New Perspectives in Algebraic Combinatorics
• Index entries for linear recurrences with constant coefficients, signature (2,2,2,-1).

Crossrefs

Cf. A112835, A138573.

Programs

GAP

a:=[5,16,45,130];; for n in [5..30] do a[n]:=2*a[n-1]+2*a[n-2] +2*a[n-3]-a[n-4]; od; a; # Muniru A Asiru, Sep 12 2018

Magma

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (5+6*x+3*x^2-2*x^3)/(1-2*x-2*x^2-2*x^3+x^4) )); // G. C. Greubel, Jul 29 2019

Maple

seq(coeff(series((5+6*x+3*x^2-2*x^3)/(1-2*x-2*x^2-2*x^3+x^4),x,n+1), x, n), n = 0 .. 30); # Muniru A Asiru, Sep 12 2018

Mathematica

Table[Abs[Fibonacci[n+3, 1+I]]^2, {n,0,30}] (* Vladimir Reshetnikov, Oct 05 2016 *)
CoefficientList[Series[(5+6*x+3*x^2-2*x^3)/(1-2*x-2*x^2-2*x^3+x^4), {x, 0, 30}], x] (* Stefano Spezia, Sep 12 2018 *)
LinearRecurrence[{2,2,2,-1},{5,16,45,130},30] (* Harvey P. Dale, Oct 03 2024 *)

PARI

{a(n) = my(m = abs(n+3)); polcoeff( (x - x^3) / (1 - 2*x - 2*x^2 - 2*x^3 + x^4) + x * O(x^m), m)};  /* Michael Somos, Dec 15 2011 */

PARI

x='x+O('x^33); Vec((5+6*x+3*x^2-2*x^3)/(1-2*x-2*x^2-2*x^3+x^4)) \\ Altug Alkan, Sep 12 2018

Python

from math import log
a0,a1,a2,a3,n = 130,45,16,5,3
print(0,a3)
print(1,a2)
print(2,a1)
print(3,a0)
while log(a0)/log(10) < 1000:
    a0,a1,a2,a3,n = 2*(a0+a1+a2)-a3,a0,a1,a2,n+1
    print(n,a0) # A.H.M. Smeets, Sep 12 2018

Sage

((5+6*x+3*x^2-2*x^3)/(1-2*x-2*x^2-2*x^3+x^4)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Jul 29 2019

Formula

G.f.: (5 + 6*x + 3*x^2 - 2*x^3) / (1 - 2*x - 2*x^2 - 2*x^3 + x^4).

a(-n) = a(-6 + n). a(-1) = 2, a(-2) = 1, a(-3) = 0. a(n) = 2*a(n-1) + 2*a(n-2) + 2*a(n-3) - a(n-4). - Michael Somos, Dec 15 2011

A112835(2*n + 3) = a(n).

Lim_{n -> inf} a(n)/a(n-1) = A318605. - A.H.M. Smeets, Sep 12 2018