# Recurrence for perfect matchings revisited.

I like to study combinatorics a bit as a hobby, and recently a question I found interesting was posed asking to derive a recurrence for the generating function $G_n(x)$, the ordinary generating function for perfect matchings on the set $[2n]=\{1,2,\dots,2n\}$, where the coefficient of $x^s$ is the number $s$ of short edges. A short edge is an edge with form $\{i,i+1\}$.

The recurrence was $$G_n(x)=(x+2n-2)G_{n-1}(x)+(1-x)\frac{d}{dx}G_{n-1}(x).$$

Why does it hold?

I rearranged this as $$G_n(x)=xG_{n-1}(x)+(2n-2)G_{n-1}(x)+\frac{d}{dx}G_{n-1}(x)-x\frac{d}{dx}G_{n-1}(x).$$ Looking at the individual coefficients of the summands, I see that:

• The coefficient of $x^s$ in $G_n(x)$ is the number of perfect matchings on $[2n]$ with $s$ short edges.

• The coefficient of $x^s$ in $xG_{n-1}(x)$ is the number of perfect matchings on $[2n-2]$ with $s-1$ short edges.

• The coefficient of $x^s$ in $(2n-2)G_{n-1}(x)$ is $2n-2$ times the number of perfect matchings on $[2n-2]$ with $s$ short edges.

• The coefficient of $x^s$ in $\frac{d}{dx}G_{n-1}(x)$ is $s+1$ times the number of perfect matchings on $[2n-2]$ with $s+1$ short edges.

• The coefficient of $x^s$ in $x\frac{d}{dx}G_{n-1}(x)$ is $s$ times the number of perfect matchings on $[2n-2]$ with $s$ short edges.

Denoting these quantities as $A$, $B$, $C$, $D$, and $E$, respectively, it should be that $A=B+C+D-E$. Is there some clever way to show that the four possibilities in the RHS count all possibilities? I believe this would show that the identity is true. Thank you.

With Michael Lugo's suggestion, it's probably better to consider $A+E=B+C+D$. So I'm trying to determine why $$(2n,s)+s(2n-2,s)=(2n-2,s-1)+(2n-2)(2n-2,s)+(s+1)(2n-2,s+1)$$ where $(x,y)$ represents the number of perfect matchings on $x$ points with $y$ short edges.

-
Just a thought: bijective proofs and subtraction don't play well together. You might want to rewrite that as $A+E = B+C+D$ and look for a bijection between the sets counted by $A$ and $E$ and those counted by $B, C$ and $D$. – Michael Lugo Jan 30 '12 at 23:40
Good point, thanks for the suggestion, @MichaelLugo. I thought about this on and off, and still don't see a clever way to count them. Perhaps I'll post a bounty soon. – Waldott Jan 31 '12 at 8:27

The way to see this is to look at the edge containing $2n$. Fix a matching on $\{1,\ldots,2n\}$ containing $s$ short edges, and let $2n$ be paired with the vertex $j\in\{1,\ldots,2n-1\}$. We then have the following possibilities:

(a) $j=2n-1$. After removing the edge $\{2n-1,2n\}$, we are left with a matching on $\{1,\ldots,2n-2\}$ with $s-1$ short edges.

(b) $j\in\{2,\ldots,2n-2\}$, and $\{j-1,j+1\}$ is an edge. In this case, if the edge $\{j,2n\}$ is removed and the vertices $j+1$, $\ldots$, $2n-1$ are renumbered as $j$, $\ldots$, $2n-2$, the edge $\{j-1,j+1\}$ will become the short edge $\{j-1,j\}$, so we will have a matching on $\{1,\ldots,2n-2\}$ with $s+1$ short edges.

(c) The remaining possibility is that either $j=1$ or, although $j\in\{2,\ldots,2n-2\}$, $\{j-1,j+1\}$ is not an edge. In this case, if we remove $\{j,2n\}$ and renumber the vertices $j+1$, $\ldots$, $2n-1$ as in (b), the number of short edges will not increase, so we will have a matching on $\{1,\ldots,2n-2\}$ with $s$ short edges.

This construction gives a bijection between matchings on $\{1,\ldots,2n\}$ and pairs consisting of a $j$ in $\{1,\ldots,2n-1\}$ and a matching on $\{1,\ldots,2n-2\}$. Also, given a matching on $\{1,\ldots,2n-2\}$ with $s+1$ short edges, there will be $s+1$ ways to pick a $j$ as in (b), since we can place $j$ in the middle of each short edge. Similarly, given a matching on $\{1,\ldots,2n-2\}$ with $s$ short edges, there are $2n-2-s$ ways to pick a $j$ as in (c), since out of the $2n-2$ possible choices in $\{1,\ldots,2n-2\}$, only the $j$s that would fall in the middle of the $s$ short edges are ruled out. Therefore, if $(x,y)$ is the number of perfect matchings on $\{1,\ldots,x\}$ with $y$ short edges,

$$(2n,s)=(2n-2,s-1)+(s+1)(2n-2,s+1)+(2n-s-2)(2n-2,s),$$

as desired.

-
Many thanks David, I will try to award the bounty soon if no other answers appear. – Waldott Feb 3 '12 at 5:05