Combinatorial interpretation of double factorial.

Question

Using some basic algebra (and proved afterwards using induction), I found that:

$$ 1 \cdot 3 \cdot ... (2n-1) = \frac{(2n)!}{2^n \cdot n!}$$

After a bit of research, I found out that this is known as the 'double factorial', is there a combinatorial interpretation/proof for this result?

Answer 1

André Nicolas gives the clue, "It counts in two different ways the number of ways to divide 2n people into n teams of 2 people."

The left-hand side

Consider the following procedure:

• Select the youngest person who has not yet been put in a two-person team.
• Match them with another so far unselected person.

This produces $1\cdot(2n-1)\cdot1\cdot(2n-3)\cdot\ldots\cdot(3)\cdot1\cdot(1)$, which is the left-hand side. The procedure can give any matching, and from any matching we can reconstruct the choices we made.

The right-hand side

Suppose we ask the two-person teams to form a line. There are $2n$ persons, and thus $(2n)!$ possible lines. But for any given ordering, the pairs can be reordered (with the left person remaining on the left) in $n!$ ways, and the relative order (inside the pairs) independently in $2^n$ ways. This produces the right-hand side.