OFFSET
0,2
COMMENTS
The rational g.f. and b-file extension were validated by an exact layer-by-layer transfer-matrix computation for P_3 X C_4 X P_n. A boundary mask records which of the 12 vertices of the current P_3 X C_4 layer are already matched to the previous layer; enumerating all matchings within the layer and to the next layer gives 924 reachable states. This direct DP reproduces the terms through n=460. Moreover, the order-83 recurrence holds as an identity of the full 924-state boundary vector at step 83, 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..460 (first 201 terms from Alois P. Heinz)
Steven Kotlarz, PARI/GP program for the rational generating function
Steven Kotlarz, Python program for the rational generating function
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
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 self-reciprocal: Q(x) = x^83*Q(1/x), and Q(x) = (1+x)*R(x), where R is palindromic, irreducible over Z, and has degree 82.
P(x) is anti-self-reciprocal: P(x) = -x^81*P(1/x). Hence A(1/x) = -x^2*A(x).
Equivalently, if Q(x) = 1 + Sum_{j=1..83} q(j)*x^j, then a(n) = -Sum_{j=1..83} q(j)*a(n-j) for n >= 83.
a(n) ~ C*r^n, where r = 145.5477203498858991690498096193638698200954885... is the largest real root of Q(x). The number r is a root of the irreducible degree-82 factor R(x); r + 1/r has degree 41. (End)
EXAMPLE
a(1) = 32 is the number of perfect matchings of P_3 X C_4 X P_1, i.e., of the graph P_3 X C_4.
G.f.: 1 + 32*x + 6345*x^2 + 862112*x^3 + 127027769*x^4 + ...
PROG
(PARI) \\ See Steven Kotlarz PARI/GP program link.
(Python) # See Steven Kotlarz Python program link.
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved