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

1, 1, 13, 41, 281, 1183, 6728, 31529, 167089, 817991, 4213133, 21001799, 106912793, 536948224, 2720246633, 13704300553, 69289288909, 349519610713, 1765722581057, 8911652846951, 45005025662792, 227191499132401, 1147185247901449, 5791672851807479

Offset: 0

Author

N. J. A. Sloane, Per H. Lundow

Keywords

• nonn
• easy

References

• F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
• R. P. Stanley, Enumerative Combinatorics I, p. 292.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450
• 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 and 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: tatami and non-tatami tilings, arXiv:1311.6135 [math.CO], 2013, Table 5.
• Thotsaporn "Aek" Thanatipanonda, Statistics of Domino Tilings on a Rectangular Board, Fibonacci Quart. 57 (2019), no. 5, 145-153. See p. 151.
• Index entries for linear recurrences with constant coefficients, signature (1,20,10,-38,-10,20,-1,-1).

Crossrefs

Row 6 of arrays A099390, A189006.

Column k=2 of A251072.

Cf. A005178.

Programs

Magma

m:=30; R:=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

Maple

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

Mathematica

a[n_] := Product[2(2 + Cos[(2 k Pi)/7] + Cos[(2 j Pi)/(n+1)]), {k, 1, 3}, {j, 1, n/2}] // Round;
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Aug 19 2018, after A099390 *)
LinearRecurrence[{1, 20, 10, -38, -10, 20, -1, -1}, {1, 1, 13, 41, 281, 1183, 6728, 31529}, 30] (* Vincenzo Librandi, Nov 24 2018 *)

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

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

Formula

From N. J. A. Sloane, Feb 03 2009: (Start)

a(1) = 1,

a(2) = 13,

a(3) = 41,

a(4) = 281,

a(5) = 1183,

a(6) = 6728,

a(7) = 31529,

a(8) = 167089,

a(9) = 817991,

a(10) = 4213133,

a(11) = 21001799,

a(12) = 106912793,

a(13) = 536948224,

a(14) = 2720246633, and

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)

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) ).

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