login
Number of perfect matchings in graph P_{7} X P_{2n}.
8

%I #26 Mar 03 2024 10:09:43

%S 1,21,781,31529,1292697,53175517,2188978117,90124167441,3710708201969,

%T 152783289861989,6290652543875133,259009513044645817,

%U 10664383939345916681,439092316687230373293,18079062471131097321077

%N Number of perfect matchings in graph P_{7} X P_{2n}.

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

%H Alois P. Heinz, <a href="/A028469/b028469.txt">Table of n, a(n) for n = 0..500</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>

%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>

%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors.pdf">Computation of matching polynomials and the number of 1-factors in polygraphs</a>, Research report, No 12, 1996, Department of Math., Umea University, Sweden.

%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors2.ps.gz">Enumeration of matchings in polygraphs</a>, 1998.

%H R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving Rectangular Regions with Rectangular Tiles: Tatami and Non-Tatami Tilings</a>, arXiv:1311.6135 [math.CO], Table 6.

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (56, -672, 2632, -4094, 2632, -672, 56, -1).

%F G.f.: (-x^7 +35*x^6 -277*x^5 +727*x^4 -727*x^3 +277*x^2 -35*x +1) / (x^8 -56*x^7 +672*x^6 -2632*x^5 +4094*x^4 -2632*x^3 +672*x^2 -56*x +1).

%F (Faase:) If b(n) denotes the number of perfect matchings in P_7 X P_n we have:

%F b(1) = 0,

%F b(2) = 21,

%F b(3) = 0,

%F b(4) = 781,

%F b(5) = 0,

%F b(6) = 31529,

%F b(7) = 0,

%F b(8) = 1292697,

%F b(9) = 0,

%F b(10) = 53175517,

%F b(11) = 0,

%F b(12) = 2188978117,

%F b(13) = 0,

%F b(14) = 90124167441,

%F b(15) = 0,

%F b(16) = 3710708201969, and

%F b(n) = 56b(n-2) - 672b(n-4) + 2632b(n-6) - 4094b(n-8) + 2632b(n-10) - 672b(n-12) + 56b(n-14) - b(n-16).

%t a[n_] := Product[2(2+Cos[k Pi/4]+Cos[2j Pi/(2n+1)]), {k, 1, 3}, {j, 1, n}] // Round;

%t Table[a[n], {n, 0, 14}] (* _Jean-François Alcover_, Aug 20 2018 *)

%Y Row 7 of array A099390.

%K nonn

%O 0,2

%A _Per H. Lundow_

%E Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009