A033506 Number of matchings in graph P_{3} X P_{n}.

1, 3, 22, 131, 823, 5096, 31687, 196785, 1222550, 7594361, 47177097, 293066688, 1820552297, 11309395995, 70254767718, 436427542283, 2711118571311, 16841658983944, 104621568809247, 649916534985369, 4037327172325542

Offset: 0

Author

Per H. Lundow

Keywords

• nonn

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 50, 999.
• Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Svenja Huntemann, Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
• David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020).
• Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
• R. C. Read, The dimer problem for narrow rectangular arrays: A unified method of solution, and some extensions, Aequationes Mathematicae, 24 (1982), 47-65.
• Eric Weisstein's World of Mathematics, Grid Graph
• Eric Weisstein's World of Mathematics, Independent Edge Set
• Eric Weisstein's World of Mathematics, Matching
• Index entries for linear recurrences with constant coefficients, signature (4,14,0,-10,0,1).

Crossrefs

Column 3 of triangle A210662. Row sums of A100245.

Cf. A030186, A033507, A033508, A033509, A033510, A033511.

Programs

GAP

a:=[1,3,22,131,823,5096];; for n in [7..30] do a[n]:=4*a[n-1] +14*a[n-2]-10*a[n-4]+a[n-6]; od; a; # G. C. Greubel, Oct 26 2019

Magma

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

Maple

seq(coeff(series((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5 )), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 26 2019

Mathematica

CoefficientList[Series[(1-2x-x^2)(1+x-x^2)/((1+x)(1-5x-9x^2+9x^3+x^4-x^5) ), {x, 0, 30}], x] (* Harvey P. Dale, Dec 05 2014 *)
LinearRecurrence[{4, 14, 0, -10, 0, 1}, {1, 3, 22, 131, 823, 5096}, 30] (* Harvey P. Dale, Dec 05 2014 *)
Table[RootSum[-1 +# +9#^2 -9#^3 -5#^4 +#^5 &, 1436541#^n + 3941068#^(n+1) -6086452#^(n+2) -2800519#^(n+3) +591744#^(n+4) &]/10204570 -(-1)^n/5, {n, 20}] (* Eric W. Weisstein, Oct 02 2017 *)

PARI

my(x='x+O('x^30)); Vec((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2 +9*x^3+x^4-x^5))) \\ G. C. Greubel, Oct 26 2019

Sage

def A033506_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) ).list()
A033506_list(30) # G. C. Greubel, Oct 26 2019

Formula

G.f.: (1-2*x-x^2)*(1+x-x^2)/((1+x)*(1-5*x-9*x^2+9*x^3+x^4-x^5)). - Sergey Perepechko, Apr 19 2013