login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033506 Number of matchings in graph P_{3} X P_{n}. 4
1, 3, 22, 131, 823, 5096, 31687, 196785, 1222550, 7594361, 47177097, 293066688, 1820552297, 11309395995, 70254767718, 436427542283, 2711118571311, 16841658983944, 104621568809247, 649916534985369, 4037327172325542 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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.

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

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

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

PROG

(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

(MAGMA) R<x>:=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

(Sage)

def A033506_list(prec):

    P.<x> = 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

(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

CROSSREFS

Column 3 of triangle A210662. Row sums of A100245.

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

Sequence in context: A006283 A232017 A100511 * A091639 A091636 A321003

Adjacent sequences:  A033503 A033504 A033505 * A033507 A033508 A033509

KEYWORD

nonn

AUTHOR

Per H. Lundow

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 9 05:12 EDT 2020. Contains 336319 sequences. (Running on oeis4.)