A028470 Number of perfect matchings in graph P_{8} X P_{n}.

1, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 1031151241, 8940739824, 82741005829, 731164253833, 6675498237130, 59554200469113, 540061286536921, 4841110033666048, 43752732573098281, 393139145126822985, 3547073578562247994, 31910388243436817641

Offset: 0

Author

Per H. Lundow

Keywords

• nonn

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 = 0..1048
• 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 Hamiltonian 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
• Index entries for linear recurrences with constant coefficients, signature (1, 76, 69, -921, -584, 4019, 829, -7012, 829, 4019, -584, -921, 69, 76, 1, -1).

Crossrefs

Row 8 of array A099390.

Programs

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. <>)[10, 1]: seq(a(n), n=0..50);  # Alois P. Heinz, Apr 14 2011

Mathematica

a[n_] := Product[2(2+Cos[(2j Pi)/9] + Cos[(2k Pi)/(n+1)]), {k, 1, n/2}, {j, 1, 4}] // Round; Join[{1}, Array[a, 21]] (* Jean-François Alcover, Aug 11 2018; a(0)=1 prepended by Georg Fischer, Apr 17 2020 *)

PARI

{a(n) = sqrtint(polresultant(polchebyshev(8, 2, x/2), polchebyshev(n, 2, I*x/2)))} \\ Seiichi Manyama, Apr 13 2020

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

Extensions

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

a(0)=1 prepended by Seiichi Manyama, Apr 13 2020