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

%I #62 Sep 08 2022 08:44:50

%S 1,1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799,

%T 106912793,536948224,2720246633,13704300553,69289288909,349519610713,

%U 1765722581057,8911652846951,45005025662792,227191499132401,1147185247901449,5791672851807479

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

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

%D R. P. Stanley, Enumerative Combinatorics I, p. 292.

%H Alois P. Heinz, <a href="/A028468/b028468.txt">Table of n, a(n) for n = 0..450</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 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 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], 2013, Table 5.

%H Thotsaporn ”Aek” Thanatipanonda, <a href="https://www.fq.math.ca/Papers1/57-5/thanatipanonda.pdf">Statistics of Domino Tilings on a Rectangular Board</a>, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.

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

%F From _N. J. A. Sloane_, Feb 03 2009: (Start)

%F a(1) = 1,

%F a(2) = 13,

%F a(3) = 41,

%F a(4) = 281,

%F a(5) = 1183,

%F a(6) = 6728,

%F a(7) = 31529,

%F a(8) = 167089,

%F a(9) = 817991,

%F a(10) = 4213133,

%F a(11) = 21001799,

%F a(12) = 106912793,

%F a(13) = 536948224,

%F a(14) = 2720246633, and

%F a(n) = 40*a(n-2) - 416*a(n-4) + 1224*a(n-6) - 1224*a(n-8) + 416*a(n-10) - 40*a(n-12) + a(n-14). (From Faase's web page.) (End)

%F G.f.: (x^2-2*x-1)*(x^4+2*x^3-3*x^2-2*x+1) / ( (1-x) *(1+x) *(x^3-5*x^2+6*x-1) *(x^3+6*x^2+5*x+1) ).

%F a(n) = a(n-1)+20*a(n-2)+10*a(n-3)-38*a(n-4)-10*a(n-5)+20*a(n-6)-a(n-7)-a(n-8). - _Sergey Perepechko_, Sep 23 2018

%p seq(coeff(series((1+2*x-x^2)*(x^4+2*x^3-3*x^2-2*x+1)/((x-1)*(x+1)*(x^3-5*x^2+6*x-1)*(x^3+6*x^2+5*x+1)),x,n+1), x, n), n = 0 .. 25); # _Muniru A Asiru_, Nov 23 2018

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

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

%t LinearRecurrence[{1, 20, 10, -38, -10, 20, -1, -1}, {1, 1, 13, 41, 281, 1183, 6728, 31529}, 30] (* _Vincenzo Librandi_, Nov 24 2018 *)

%o (PARI) my(x='x+O('x^30)); Vec(-(x^2-2*x-1)*(x^4+2*x^3-3*x^2-2*x+1)/((x-1)*(1+x)*(x^3-5*x^2+6*x-1)*(x^3+6*x^2+5*x+1))) \\ _Altug Alkan_, Mar 23 2016

%o (Magma) m:=30; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!( (x^2-2*x-1)*(x^4+2*x^3-3*x^2-2*x+1)/((1-x^2)*(x^3-5*x^2+6*x-1)*(x^3+ 6*x^2+5*x+1)) )); // _G. C. Greubel_, Nov 25 2018

%o (Sage) s=((x^2-2*x-1)*(x^4+2*x^3-3*x^2-2*x+1)/((1-x^2)*(x^3-5*x^2+6*x-1) *(x^3+6*x^2+5*x+1))).series(x,30); s.coefficients(x, sparse=False) # _G. C. Greubel_, Nov 25 2018

%Y Row 6 of arrays A099390, A189006.

%Y Column k=2 of A251072.

%Y Cf. A005178.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, _Per H. Lundow_