Counting Perfect Matchings along a Chain (Transfer/State Recurrence)

The problem

A perfect matching of a graph $G$ is a set $M$ of edges that covers every vertex exactly once — each vertex is an endpoint of one and only one edge of $M$. We want $\#PM(G)$, the number of such matchings. In general this is hard (#P-complete), but when $G$ has a linear, repetitive structure — a path, a ladder, a chain of identical blocks (diamonds, squares, triangles) — it collapses to a tiny recurrence.

Key idea: cut the chain and track a boundary state

Process the blocks of the chain from left to right, $B_1, B_2, \dots, B_n$, sharing a single junction vertex between consecutive blocks. Make a vertical cut after block $i$. Almost every vertex to the left of the cut is already matched among themselves; the only information that crosses the cut is the status of the junction vertex $s_i$ on the boundary:

• state $A$ — $s_i$ is already matched by an edge lying inside blocks $1..i$;
• state $B$ — $s_i$ is still free, to be matched later (i.e. inside block $i+1$).

Let $a_i,b_i$ be the number of partial matchings of $B_1\dots B_i$ ending in each state. The recurrence comes from asking: how can one more block be attached, given the incoming state? Because every block is identical, the same transition rule repeats, so this is exactly a transfer-matrix computation:

$\begin{pmatrix} a_i \\ b_i \end{pmatrix} = T\begin{pmatrix} a_{i-1} \\ b_{i-1} \end{pmatrix},\qquad T=\begin{pmatrix} p & q \\ r & s \end{pmatrix}.$

The entries of $T$ are read off the single block: count, for each (incoming boundary state $\to$ outgoing boundary state), the number of ways to match the interior vertices of one block. The answer is the total in the accepting state after the last block (the boundary vertex of the closed end must end up matched).

How to apply it

1. Decompose the graph into the repeated block and identify the shared junction vertices.
2. Choose the state = the matched/free status of the current boundary vertex (sometimes a pair of boundary vertices for a ladder — then there are more states).
3. Build the transition. For each incoming state, enumerate the ways to match every interior vertex of one block, recording the resulting outgoing state. This gives $a_i,b_i$ in terms of $a_{i-1},b_{i-1}$.
4. Set base cases for the empty/first block and read off the final accepting count, or just iterate the recurrence $n$ times.

For paths and many simple chains the two states merge into a single linear recurrence — often the Fibonacci one. Example: the number of perfect matchings of the $2\times n$ grid (ladder) satisfies $f_n=f_{n-1}+f_{n-2}$ with $f_0=f_1=1$, the Fibonacci numbers, because each new column is either matched by one vertical edge (state carries over) or by two horizontals that also consume the previous column.

Mini-example: chain of $n$ diamonds

Take the structure from the konkur figure: a horizontal spine $s_0,s_1,\dots,s_n$, and between $s_{i-1}$ and $s_i$ a top vertex $t_i$ and bottom vertex $b_i$, with block $i$ being the $K_4$ on $\{s_{i-1},s_i,t_i,b_i\}$ (both diagonals present, so the spine edge $s_{i-1}s_i$ and the rung $t_ib_i$ exist).

State = is the left spine vertex $s_{i-1}$ matched from outside this block? Per block we must cover $t_i$ and $b_i$, plus possibly $s_{i-1}$, ending by reporting whether $s_i$ is matched. Enumerating the legal interior choices of one $K_4$ block gives the transfer matrix, and letting $M_n$ be the number of perfect matchings of the whole chain yields the clean recurrence

$M_n = M_{n-1} + 2,\qquad M_1 = 3,$

because once the diamonds to the left are matched, the current diamond either reuses the spine edge to pass an already-matched $s_{i-1}$ forward (adding a fixed local factor) or absorbs $s_{i-1}$ via $t_i$ or $b_i$. Iterating, $M_n = 2n+1$, so the $5$-diamond chain has $M_5 = 2\cdot 5 + 1 = 11$ perfect matchings — matching the figure with $6+2\cdot5=16$ vertices and $8$ matched edges.

Exam trick: Do not try to enumerate all $8$-edge subsets. Find the boundary state that crosses each cut (usually just "is this one vertex matched yet?"), write the per-block transition once, and ride the recurrence — most chain figures collapse to a Fibonacci-like or arithmetic formula like $2n+1$.