login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028470 Number of perfect matchings in graph P_{8} X P_{n}. 7
1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 1031151241, 8940739824, 82741005829, 731164253833, 6675498237130, 59554200469113, 540061286536921, 4841110033666048, 43752732573098281, 393139145126822985, 3547073578562247994, 31910388243436817641 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

REFERENCES

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..300

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamilton cycles in product graphs

F. Faase, Results from the counting program

David Klarner, Jordan Pollack, Domino tilings of rectangles with fixed width, Disc. Math. 32 (1980) 45-52

Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden.

Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

R. J. Mathar, Paving rectangular regions with rectangular tiles,...., arXiv:1311.6135 [math.CO], Table 7.

James A. Sellers, Domino Tilings and Products of Fibonacci and Pell Numbers, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2

FORMULA

Recurrence from Faase web site:

a(1) = 1,

a(2) = 34,

a(3) = 153,

a(4) = 2245,

a(5) = 14824,

a(6) = 167089,

a(7) = 1292697,

a(8) = 12988816,

a(9) = 108435745,

a(10) = 1031151241,

a(11) = 8940739824,

a(12) = 82741005829,

a(13) = 731164253833,

a(14) = 6675498237130,

a(15) = 59554200469113,

a(16) = 540061286536921,

a(17) = 4841110033666048,

a(18) = 43752732573098281,

a(19) = 393139145126822985,

a(20) = 3547073578562247994,

a(21) = 31910388243436817641,

a(22) = 287665106926232833093,

a(23) = 2589464895903294456096,

a(24) = 23333526083922816720025,

a(25) = 210103825878043857266833,

a(26) = 1892830605678515060701072,

a(27) = 17046328120997609883612969,

a(28) = 153554399246902845860302369,

a(29) = 1382974514097522648618420280,

a(30) = 12457255314954679645007780869,

a(31) = 112199448394764215277422176953,

a(32) = 1010618564986361239515088848178, and

a(n) = 153a(n-2) - 7480a(n-4) + 151623a(n-6) - 1552087a(n-8) + 8933976a(n-10) - 30536233a(n-12) + 63544113a(n-14) - 81114784a(n-16) + 63544113a(n-18) - 30536233a(n-20) + 8933976a(n-22) - 1552087a(n-24) + 151623a(n-26) - 7480a(n-28) + 153a(n-30) - a(n-32).

G.f.: (1 -43*x^2 -26*x^3 +360*x^4 +110*x^5 -1033*x^6 +1033*x^8 -110*x^9 -360*x^10 +26*x^11 +43*x^12 -x^14) /(1 -x -76*x^2 -69*x^3 +921*x^4 +584*x^5 -4019*x^6 -829*x^7 +7012*x^8 -829*x^9 -4019*x^10 +584*x^11 +921*x^12 -69*x^13 -76*x^14 -x^15 +x^16). - Sergey Perepechko, Nov 22 2012

MAPLE

a:= n-> (Matrix(16, (i, j)-> `if` (i=j-1, 1, `if` (i=16, [-1, 1, 76, 69, -921, -584, 4019, 829, -7012][min(j, 18-j)], 0)))^n. <<seq([1292697, 167089, 14824, 2245, 153, 34, 1, 1, 0][min(k, 18-k)], k=1..16)>>)[10, 1]: seq(a(n), n=1..50);  # Alois P. Heinz, Apr 14 2011

CROSSREFS

Row 8 of array A099390.

Sequence in context: A159744 A192398 A167241 * A221806 A212407 A190607

Adjacent sequences:  A028467 A028468 A028469 * A028471 A028472 A028473

KEYWORD

nonn

AUTHOR

Per H. Lundow

EXTENSIONS

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 30 08:46 EDT 2017. Contains 287302 sequences.