Fall 2011 Strategic Practice 1: Section 2 (Story Proofs) - Question 6
Give a story proof that $\frac{(2n)!}{2^{n}\cdot n!}=(2n-1)(2n-3)\cdot \cdot \cdot 3\cdot 1$.
Solution: Take 2n people, and count how many ways there are to form n partnerships. We can do this by lining up the people in a row and then saying the first two are a pair, the next two are a pair, etc. This overcounts by a factor of 2^n x n! since the order of pairs doesn't matter, nor does the order within each pair. Alternatively, count the number of possibilities by noting that there are 2n - 1 choices for the partner of person 1, then 2n - 3 choices for person 2 (or person 3, if person 2 was already paired to person 1), etc.
"Mathematics is the logic of certainty, but statistics is the logic of uncertainty."