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).