login
Number of perfect matchings (or domino tilings) in the graph P_9 X P_2n.
6

%I #34 Mar 03 2024 10:14:32

%S 1,55,6336,817991,108435745,14479521761,1937528668711,259423766712000,

%T 34741645659770711,4652799879944138561,623139489426439754945,

%U 83456125990631342400791,11177167872295392172767936,1496943834332592837945956455,200483802581126644843760725601

%N Number of perfect matchings (or domino tilings) in the graph P_9 X P_2n.

%H Sean A. Irvine, <a href="/A028471/b028471.txt">Table of n, a(n) for n = 0..150</a>

%H J. L. Hock and R. B. McQuistan, <a href="https://doi.org/10.1016/0166-218X(84)90083-0">A note on the occupational degeneracy for dimers on a saturated two-dimensional lattice space</a>, Discrete Applied Mathematics, 1984, v.8, 101-104.

%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 <a href="/index/Rec#order_16">Index entries for linear recurrences with constant coefficients</a>, signature (209, -11936, 274208, -3112032, 19456019, -70651107, 152325888, -196664896, 152325888, -70651107, 19456019, -3112032, 274208, -11936, 209, -1).

%F a(n) = 209*a(n-1) - 11936*a(n-2) + 274208*a(n-3) - 3112032*a(n-4) + 19456019*a(n-5) - 70651107*a(n-6) + 152325888*a(n-7) - 196664896*a(n-8) + 152325888*a(n-9) - 70651107*a(n-10) + 19456019*a(n-11) - 3112032*a(n-12) + 274208*a(n-13) - 11936*a(n-14) + 209*a(n-15) - a(n-16). - Jay Anderson (horndude77(AT)gmail.com), Apr 07 2007

%F G.f.: (1 - 154x + 6777x^2 - 123961x^3 + 1132714x^4 - 5684515x^5 + 16401668x^6 - 27757938x^7 + 27757938*x^8 - 16401668x^9 + 5684515x^10 - 1132714x^11 + 123961x^12 -6777x^13 + 154x^14 - x^15)/(1 - 209x + 11936x^2 - 274208x^3 + 3112032x^4 - 19456019x^5 + 70651107x^6 - 152325888x^7 + 196664896x^8 - 152325888x^9 + 70651107x^10 -19456019x^11 + 3112032x^12 - 274208x^13 + 11936x^14 - 209x^15 + x^16). - _Sergey Perepechko_, Nov 23 2012

%t T[_?OddQ, _?OddQ] = 0;

%t T[m_, n_] := Product[2(2+Cos[2 j Pi/(m+1)]+Cos[2 k Pi/(n+1)]), {k, 1, n/2}, {j, 1, m/2}];

%t a[n_] := T[2n, 9] // Round;

%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, May 28 2022 *)

%o (PARI) {a(n) = sqrtint(polresultant(polchebyshev(2*n, 2, x/2), polchebyshev(9, 2, I*x/2)))} \\ _Seiichi Manyama_, Apr 13 2020

%Y Cf. A000045, A001835, A005178, A003775, A028468, A028469, A028470.

%Y Row 9 of array A099390.

%K nonn

%O 0,2

%A _Per H. Lundow_

%E Edited by _N. J. A. Sloane_, Jul 03 2008 at the suggestion of _R. J. Mathar_