A003729 Number of perfect matchings (or domino tilings) in graph C_{5} X P_{2n}.

11, 176, 2911, 48301, 801701, 13307111, 220880176, 3666315811, 60855946601, 1010127453401, 16766766924211, 278305942640176, 4619507031938711, 76677648402694901, 1272746577484955101, 21125893715367851311

Offset: 1

Author

Frans J. Faase

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

Links

• 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
• Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
• Index entries for sequences related to dominoes
• Index entries for linear recurrences with constant coefficients, signature (19, -41, 19, -1).

Programs

Mathematica

Rest[CoefficientList[Series[x (11-33x+18x^2-x^3)/(1-19x+41x^2- 19x^3+ x^4), {x,0,20}],x]] (* or *) LinearRecurrence[{19,-41,19,-1},{11,176,2911,48301},20] (* Harvey P. Dale, Jul 16 2011 *)

Formula

a(n) = 19a(n-1) - 41a(n-2) + 19a(n-3) - a(n-4), n>4.

G.f. x*(11-33*x+18*x^2-x^3)/(1-19*x+41*x^2-19*x^3+x^4) . [From R. J. Mathar, Mar 11 2010]