7

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?

Gridley Quayle
  • 1,659
  • 3
    It counts in two different ways the number of ways to divide $2n$ people into $n$ teams of $2$ people. – André Nicolas Mar 22 '15 at 23:44
  • @AndréNicolas That is an explanation of the RHS, but I am unsure of how this relates to the LHS. In other words, why is the number of ways to partition a set of size $2n$ into $n$ sets of size $2$ equal to the product of the odd integers. In isolation, what does the product of the odd numbers count? Is it the permutations of a set such that no element retains it's original position? – Gridley Quayle Mar 22 '15 at 23:51
  • Technically, the double factorial also includes $2\cdot 4\cdots 2n$. What you have here is $(2n-1)!!$. – Thomas Andrews Mar 22 '15 at 23:51
  • The number of pairings of $2n$ elements is $2n-1$ times the number of pairings of $2n-2$ elements. Then work by induction @GridleyQuayle – Thomas Andrews Mar 22 '15 at 23:55
  • 1
    Line up the people in ascending order of age, or beauty, or student number. The youngest person has $2n-1$ choices for her team mate. For each of these choices, the youngest person not yet chosen has $2n-3$ choices for her team mate. For each of these choices, the youngest person not yet on a team has $2n-5$ choices, and so on. I think of this product as the natural way to count the number of divisions into teams, and the "right-hand side" way as less obvious. – André Nicolas Mar 23 '15 at 01:40

1 Answers1

3

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.

Andrew Woods
  • 3,672