OFFSET
0,2
COMMENTS
The rational g.f. and b-file extension were validated by an exact layer-by-layer transfer-matrix computation for C_4 X C_4 X P_n. A boundary mask records which of the 16 vertices of the current C_4 X C_4 layer are already matched to the previous layer; enumerating all matchings within the layer and to the next layer gives 12870 reachable states. This direct DP reproduces the terms through n=309. Moreover, the order-71 recurrence holds as an identity of the full 12870-state boundary vector at step 71, so it continues to hold for the DP sequence by linearity of the transfer. - Steven Kotlarz, Jun 20 2026
REFERENCES
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
Steven Kotlarz, Table of n, a(n) for n = 0..309
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Steven Kotlarz, PARI/GP program for the rational generating function
Steven Kotlarz, Python program for the rational generating function
FORMULA
From Steven Kotlarz, Jun 20 2026: (Start)
G.f.: A(x) = P(x)/Q(x), where P and Q are given in the linked PARI and Python programs as coefficient lists in ascending powers of x.
Q(x) is anti-self-reciprocal: x^71*Q(1/x) = -Q(x). Hence Q(x) = (1-x)*R(x), where R is palindromic, irreducible over Z, and has degree 70.
Equivalently, a(n) = Sum_{j=1..71} c(j)*a(n-j) for n >= 71, where c(j) = -q(j), q(j) is the coefficient of x^j in Q(x), and the q(j) are listed in the linked PARI and Python programs.
a(n) ~ C*r^n, where r = 1651.9278654906032774943075923169356008699629758821... is the largest real root of Q(x), equivalently 1/r is the smallest positive root of Q(x). (End)
EXAMPLE
a(1) = 272 is the number of perfect matchings of C_4 X C_4 X P_1, i.e., of the 4 X 4 torus graph C_4 X C_4.
G.f.: 1 + 272*x + 589185*x^2 + 930336768*x^3 + 1545853411969*x^4 + ...
PROG
(PARI) \\ See Steven Kotlarz PARI/GP program link.
(Python) # See Steven Kotlarz Python program link.
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(10)-a(11) from Alois P. Heinz, Dec 10 2013
STATUS
approved