A028453 Number of perfect matchings in graph P_{3} X P_{4} X P_{n}.

1, 11, 1845, 117805, 10885344, 858626465, 72926048233, 5978148553531, 498776151252389, 41250197689850048, 3426717195626372141, 284023348462456779971, 23568180558085521390777, 1954547147093759854102489, 162141583663452653562797088, 13448613350628252849236553525

Offset

0,2

Comments

From Steven Kotlarz, Mar 19 2026: (Start)

A transfer-matrix computation uses a 924 X 924 matrix indexed by subsets of the 3 X 4 cross-section having equal numbers of black and white vertices under checkerboard coloring; perfect matchings preserve this balance at each layer interface. Then a(n) is the (0,0)-entry of T^n. The recurrence was recovered from exact transfer-matrix terms and verified against 600 terms.

Satisfies a linear recurrence with constant coefficients of order 265: Sum_{j=0..265} c(j)*a(n-j) = 0 for n >= 265, with c(0)=1 and c(j)=c(265-j) for 0 <= j <= 265. (End)

Links

Steven Kotlarz, Table of n, a(n) for n = 0..519 (terms 0..200 from Alois P. Heinz)

Steven Kotlarz, Python program

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.

Prog

(Python) # See Kotlarz link

Crossrefs

Sequence in context: A297004 A308155 A222874 * A373883 A024151 A114354

Adjacent sequences: A028450 A028451 A028452 * A028454 A028455 A028456

Keyword

nonn

Author

Per H. Lundow

Status

approved