Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 3 down vote accepted
+100

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.