1.4: Problem 4:
  1. Suppose that \(S\) contains \(2n\) elements and that \(S\) is partitioned into \(n\) disjoint subsets each one containing exactly two elements of \(S\). Show that this can be done in precisely $$ \begin{align*} (2n -1) \cdot (2n - 3) \cdot 5 \cdot 3 \cdot 1 = \frac{(2n)!}{2^nn!} \end{align*} $$
  2. Show that \((n+1)(n+2) \cdots (2n)\) is divisible by \(2^n\), but not by \(2^{n+1}\).

Proof

(1) Suppose we have \(2n\) elements. We want to partition \(S\) into \(n\) disjoint sets. There \((2n)!\) possible ways to order \(2n\) elements. But then order of \(n\) groups doesn’t matter so we need to divide by \(n!\). Furthermore, for any group of elements \(a\) and \(b\), \(\{a,b\}=\{b,a\}\). So we need to divide by 2 for each pair. Since we have \(n\) pairs, then we need to divide by \(2^n\). Therefore, the number of ways is

$$ \begin{align*} \frac{(2n)!}{n!2^n} \end{align*} $$

Another way to look at this is by fixing an element and then picking its paired element. There are \(2n-1\) ways to pick which element to pair it with. Next, we fix another element. Now we have \(2n-3\) elements to pair it with. If we do this for each element we will get

$$ \begin{align*} (2n -1) \cdot (2n - 3) \cdot 5 \cdot 3 \cdot 1 \end{align*} $$

(2) We first recognize that this product is precisely

$$ \begin{align*} \frac{(2n)!}{n!} = (n+1)(n+2) \cdots (2n) \end{align*} $$

Then, this becomes a question of counting the number of times \(2\) divides this fraction and if it at least \(n\) which means that \(2^n\) can divide it. By lecture, to know the number of times a prime (in this case 2) divides \(\frac{(2n)!}{n!}\) is

$$ \begin{align*} &\floor{\frac{2n}{2}} + \floor{\frac{2n}{2^2}} + \floor{\frac{2n}{2^3}} + \cdots \\ - &\floor{\frac{n}{2}} - \floor{\frac{n}{2^2}} - \floor{\frac{n}{2^3}} - \cdots \\ &= \sum_k^{\infty} \floor{\frac{2n}{2^k}} - \floor{\frac{n}{2^k}} \end{align*} $$

But now notice that all the middle fractions do cancel except for the first and very last. The very last fraction is 0. Therefore,

$$ \begin{align*} \sum_k^{\infty} \floor{\frac{2n}{2^k}} - \floor{\frac{n}{2^k}} = \floor{\frac{2n}{2^0}} = n \end{align*} $$

From this we see that we have exactly \(n\) 2’s so 2^\(n\) is divisble by \(\frac{(2n)!}{n!}\) but not \(\frac{(2n)!}{n!}\)

References