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 of perfect matchings of complete graphs of vertices. The number counts the number of different ways of pairing all vertices with exactly edges, without any vertex being left out or having more than one connecting edge. It turns out that

where

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

rather the double factorial is defined as

where the ceiling function gives the smallest integer not smaller than . In other words,

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

We can iterate this recursion relation:

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 can be written as

so that

For the double factorial with odd arguments 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:

This expression relates the double factorial of odd and even arguments. Let . Then the above gives us

from which follows (2).