Perfect matchings of a complete graph and the double factorial

I have a longstanding interest in graph theory applied to statistical mechanics. For example, a few years ago I published a paper in Physical Review E that explores the correspondence between spanning trees and the Ising model on the square lattice (see PDF here). More recently, I became fascinated by perfect matchings.

There is a deep relationship between perfect matchings in graph theory on the one hand and the theory of equilibrium statistical mechanics on the other hand. Perfect matchings are relevant to dimer models and to certain lattice spin models, for instance.

As entertainment and also as a birthday present to myself for my 50th anniversary this week, I decided to figure out for myself exactly why it is that the double factorial appears in the expression for the number {K_{2n}} of perfect matchings of complete graphs of {2n} vertices. The number {K_{2n}} counts the number of different ways of pairing all {2n} vertices with exactly {n} edges, without any vertex being left out or having more than one connecting edge. It turns out that

\displaystyle K_{2n} = (2n-1)!! \ \ \ \ \ (1)

where

\displaystyle (2n-1)!!= {(2n)! \over n!2^n} ~. \ \ \ \ \ (2)

It is important not to confuse the double factorial with the factorial applied twice,

\displaystyle N!! \neq (N!)! ~~, \ \ \ \ \ (3)

rather the double factorial is defined as

\displaystyle {\displaystyle N!!=\prod _{k=0}^{\left\lceil {\frac {N}{2}}\right\rceil -1}(N-2k)} \ \ \ \ \ (4)

where the ceiling function {\lceil x \rceil} gives the smallest integer not smaller than {x}. In other words,

\displaystyle N!! = \left\{ \begin{array}{ll} N(N-2)(N-4)\ldots (2), & \quad {\rm for~ even}~N \\ N(N-2) (N-4)\ldots (1), & \quad{\rm for~odd}  ~N ~~~ .\\ \end{array} \right.  \ \ \ \  (5)

Let us first calculate the number of perfect matchings. Given {2n} vertices, we can pair the 1st vertex with {2n-1} others with a single edge. Once the first edge is assigned, there are {2n-2= 2(n-1)} vertices left that need to be paired. So

\displaystyle K_{2n} = (2n-1) K_{2(n-1)} ~~. \ \ \ \ \ (6)

We can iterate this recursion relation:

\displaystyle \begin{array}{rcl} K_{2n}&=& (2n-1)(2(n-1)-1) (2(n-2)-1) \ldots (5)(3)K_{2} \\ &=& (2n-1)(2n-3)(2n-5)\ldots (1)\\ &=& (2n-1)!! ~~. \end{array}

So this is why the double factorial appears in (1).

To arrive at (2), we proceed to express the double factorial in terms of the standard factorial. First, notice that {2^m m!} can be written as

\displaystyle 2^m m! = (2m)(2m-2)\ldots 2 = (2m)!!, \ \ \ \ \ (7)

so that

\displaystyle (2m)!! = 2^m m! \ \ \ \ \ (8)

For the double factorial with odd arguments {2m - 1} we proceed as follows. Note that the double factorial contains either only odd or only even factors, which can can combine to obtain the standard factorial thus:

\displaystyle n!= n!! (n-1)!! ~~. \ \ \ \ \ (9)

This expression relates the double factorial of odd and even arguments. Let {n=2m}. Then the above gives us

\displaystyle (2m-1)!! = {(2m)! \over (2m)!!} = {(2m)! \over 2^m m!} \ \ \ \ \ (10)

from which follows (2).

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s