A033508 Number of matchings in graph P_{5} X P_{n}.

1, 8, 228, 5096, 120465, 2810694, 65805403, 1539222016, 36012826776, 842518533590, 19711134149599, 461148537211748, 10788744980331535, 252406631116215534, 5905146419664967132, 138153075553825008696

Offset: 0

Author

Per H. Lundow

Keywords

• nonn

Comments

These are the row sums of the following triangle of the matchings of P_5 X P_n with k>=0 monomers (A003775 appears in the first column):

1;

0, 3, 0, 4, 0, 1;

8, 0, 56, 0, 94, 0, 56, 0, 13, 0, 1;

0, 106, 0, 757, 0, 1670, 0, 1597, 0, 758, 0, 185, 0, 22, 0, 1;

95, 0, 2111, 0, 12181, 0, 29580, 0, 36771, 0, 25835, 0, 10769, 0, 2696, 0, 395, 0, 31, 0, 1;

0, 2180, 0, 35104, 0, 192672, 0, 510752, 0, 762180, 0, 695848, 0, 407620, 0, 157000, 0, 39979, 0, 6632, 0, 686, 0, 40, 0, 1;

1183, 0, 52614, 0, 611633, 0, 3146447, 0, 8803727, 0, 14957414, 0, 16492039, 0, 12307901, 0, 6380454, 0, 2329148, 0, 600254, 0, 108186, 0, 13295, 0, 1058, 0, 49, 0, 1;

0, 37924, 0, 1054776, 0, 10405842, 0, 51732687, 0, 151233778, 0, 283790459, 0, 361377070, 0, 324069497, 0, 209807278, 0, 99625091, 0, 34985010, 0, 9096697, 0, 1740018, 0, 240905, 0, 23414, 0, 1511, 0, 58, 0, 1;

- R. J. Mathar, May 06 2016

Links

• F. Cazals, Monomer-Dimer Tilings, 1997.
• 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.

Crossrefs

Column 5 of triangle A210662.

Programs

Maple

# The following g.f. is for the sequence a(0)=1, a(1)=8, a(2)=228, etc.
Gf:= (1-6*x-113*x^2+88*x^3+1794*x^4-1994*x^5-6956*x^6+7532*x^7+
11175*x^8-9448*x^9-9255*x^10+4700*x^11+3820*x^12-870*x^13-654*x^14+
68*x^15+45*x^16-2*x^17-x^18)/(1-14*x-229*x^2+16*x^3+4757*x^4-898*x^5-
35106*x^6+26564*x^7+74665*x^8-60482*x^9-73623*x^10+50158*x^11+
38553*x^12-17604*x^13-10366*x^14+2538*x^15+1281*x^16-140*x^17-65*x^18+
2*x^19+x^20):
expr:=convert(series(Gf,x,21),polynom):
seq(coeff(expr,x,j),j=0..20);
# Sergey Perepechko, Apr 26 2013

Formula

For g.f. see Maple program. - Sergey Perepechko, Apr 26 2013