cp's OEIS Frontend

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

%I A028470 #56 Mar 03 2024 10:13:14
%S A028470 1,1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,
%T A028470 8940739824,82741005829,731164253833,6675498237130,59554200469113,
%U A028470 540061286536921,4841110033666048,43752732573098281,393139145126822985,3547073578562247994,31910388243436817641
%N A028470 Number of perfect matchings in graph P_{8} X P_{n}.
%D A028470 F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H A028470 Alois P. Heinz, <a href="/A028470/b028470.txt">Table of n, a(n) for n = 0..1048</a>
%H A028470 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 A028470 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A028470 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A028470 David Klarner, Jordan Pollack, <a href="http://dx.doi.org/10.1016/0012-365X(80)90098-9">Domino tilings of rectangles with fixed width</a>, Disc. Math. 32 (1980) 45-52
%H A028470 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 A028470 Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors2.ps.gz">Enumeration of matchings in polygraphs</a>, 1998.
%H A028470 R. J. Mathar, <a href="http://arxiv.org/abs/1311.6135">Paving rectangular regions with rectangular tiles,....</a>, arXiv:1311.6135 [math.CO], Table 7.
%H A028470 James A. Sellers, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Sellers/sellers4.html">Domino Tilings and Products of Fibonacci and Pell Numbers</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.2
%H A028470 <a href="/index/Rec#order_16">Index entries for linear recurrences with constant coefficients</a>, signature (1, 76, 69, -921, -584, 4019, 829, -7012, 829, 4019, -584, -921, 69, 76, 1, -1).
%F A028470 Recurrence from Faase web site:
%F A028470 a(1) = 1,
%F A028470 a(2) = 34,
%F A028470 a(3) = 153,
%F A028470 a(4) = 2245,
%F A028470 a(5) = 14824,
%F A028470 a(6) = 167089,
%F A028470 a(7) = 1292697,
%F A028470 a(8) = 12988816,
%F A028470 a(9) = 108435745,
%F A028470 a(10) = 1031151241,
%F A028470 a(11) = 8940739824,
%F A028470 a(12) = 82741005829,
%F A028470 a(13) = 731164253833,
%F A028470 a(14) = 6675498237130,
%F A028470 a(15) = 59554200469113,
%F A028470 a(16) = 540061286536921,
%F A028470 a(17) = 4841110033666048,
%F A028470 a(18) = 43752732573098281,
%F A028470 a(19) = 393139145126822985,
%F A028470 a(20) = 3547073578562247994,
%F A028470 a(21) = 31910388243436817641,
%F A028470 a(22) = 287665106926232833093,
%F A028470 a(23) = 2589464895903294456096,
%F A028470 a(24) = 23333526083922816720025,
%F A028470 a(25) = 210103825878043857266833,
%F A028470 a(26) = 1892830605678515060701072,
%F A028470 a(27) = 17046328120997609883612969,
%F A028470 a(28) = 153554399246902845860302369,
%F A028470 a(29) = 1382974514097522648618420280,
%F A028470 a(30) = 12457255314954679645007780869,
%F A028470 a(31) = 112199448394764215277422176953,
%F A028470 a(32) = 1010618564986361239515088848178, and
%F A028470 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).
%F A028470 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
%p A028470 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=0..50);  # _Alois P. Heinz_, Apr 14 2011
%t A028470 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 *)
%o A028470 (PARI) {a(n) = sqrtint(polresultant(polchebyshev(8, 2, x/2), polchebyshev(n, 2, I*x/2)))} \\ _Seiichi Manyama_, Apr 13 2020
%Y A028470 Row 8 of array A099390.
%K A028470 nonn
%O A028470 0,3
%A A028470 _Per H. Lundow_
%E A028470 Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009
%E A028470 a(0)=1 prepended by _Seiichi Manyama_, Apr 13 2020