Exercise 1.4.4 (Number of partitions by pairs)

Proof.

(a)

Write $P_n$ for the number of partitions(-sets) of a set ${𝒮}_{}$ which contains $2n$ elements. Consider a fixed element $a\in S$. This element can be paired with any other element $b$ of ${𝒮}_{}$, in $2n-1$ ways. It remains to partition the $2n-2$ other elements, in $P_{n-1}$ ways. This gives the relation, for $n\ge 2$, $$P_n=(2n-1)P_{n-1}.$$

So $P_{n+1}=(2n+1)P_n(n\ge 1)$.

We prove by induction the property

$$𝒫(n)⟺P_n=\underset{k=1}{\overset{n}{\prod }}(2k-1).$$

If $n=1$, there is only one possibility to partition two elements $a,b$, the unique partition being $\{\{a,b\}\}$. Thus $P_1=1$, and $𝒫(1)$ is true.

Assume that for some $n\ge 1$, $P_n={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{k=1}^n(2k-1)$. Then

$$\begin{array}{llll}\hfill P_{n+1}& =(2n+1)P_n& \hfill & \\ \hfill & =(2n+1)\underset{k=1}{\overset{n}{\prod }}(2k-1)& \hfill & \\ \hfill & =\underset{k=1}{\overset{n+1}{\prod }}(2k-1).& \hfill & \end{array}$$

The induction is done, so for all $n{\text{∈}}^{\text{∗}}$,

$$P_n=\underset{k=1}{\overset{n}{\prod }}(2k-1)=(2n-1)(2n-3)\cdots 5\cdot 3\cdot 1.$$

Moreover

$$\underset{k=1}{\overset{n}{\prod }}(2k-1)=\frac{\underset{k=1}{\overset{n}{\prod }}(2k-1)\underset{k=1}{\overset{n}{\prod }}(2k)}{\underset{k=1}{\overset{n}{\prod }}(2k)}=\frac{(2n)!}{2^{n}n!}.$$

Alternative proof:

Let ${𝒫}^{\prime }$ be the set of ordered partitions $(A_1,\dots ,A_n)$ of $𝒮$ (partition-families), where $|A_i|=2$ for every index $i$, and let $𝒫$ be the set of unordered partitions $\{A_1,\dots ,A_n\}$ with the same conditions for $A_i$ (partition-sets). Consider the map

$$\chi \{\begin{array}{ccc}\hfill {𝒫}^{\prime }\hfill & \hfill \text{→}\hfill & 𝒫\hfill \\ \hfill (A_1,\dots ,A_n)\hfill & \hfill \mapsto \hfill & \{A_1,\dots ,A_n\}\hfill \end{array}$$

Then every element of $𝒫$ has $n!$ pre-images, explicitly the partition-families $(A_{\sigma (1)},\dots ,A_{{\sigma }_{\text{(}}n))}$, where $\sigma$ is any permutation of $S_n$. Therefore

$$n!\cdot |𝒫|=|{𝒫}^{\prime }|.$$

To count the elements of ${𝒫}^{\prime }$, we choose first the two elements of $A_1$ among $2n$ elements, in $\left(\genfrac{}{}{0.0pt}{}{2n}{2}\right)$ ways, then the two elements of $A_2$, in $\left(\genfrac{}{}{0.0pt}{}{2n-2}{2}\right)$ ways, and so on, the two last elements of $A_n$ in $\left(\genfrac{}{}{0.0pt}{}{2}{2}\right)=1$ way. Thus

$$|{𝒫}^{\prime }|=\left(\genfrac{}{}{0.0pt}{}{2n}{2}\right)\left(\genfrac{}{}{0.0pt}{}{2n-2}{2}\right)\cdots \left(\genfrac{}{}{0.0pt}{}{2}{2}\right),$$

and so

$$\begin{array}{llll}\hfill |𝒫|& =\frac{1}{n!}\left(\genfrac{}{}{0.0pt}{}{2n}{2}\right)\left(\genfrac{}{}{0.0pt}{}{2n-2}{2}\right)\cdots \left(\genfrac{}{}{0.0pt}{}{2}{2}\right)& \hfill & \\ \hfill & =\frac{1}{n!}\frac{(2n)!}{(2n-2)!2!}\frac{(2n-2)!}{(2n-4)!2!}\cdots \frac{2!}{0!2!}& \hfill & \\ \hfill & =\frac{(2n)!}{2^{n}n!}.& \hfill & \end{array}$$

This gives the same result.

(b)

By part (a), $\frac{(2n)!}{2^{n}n!}$ is an integer, thus $2^n\mid \frac{(2n)!}{n!}$.

Assume for contradiction that $2^{n+1}\mid \frac{(2n)!}{n!}$. Then $2\mid \frac{(2n)!}{2^{n}n!}$. This is false, since $\frac{(2n)!}{2^{n}n!}=(2n-1)(2n-3)\cdots 5\cdot 3\cdot 1$ is a product of odd numbers, therefore is itself odd. So $2^{n+1}\nmid \frac{(2n)!}{n!}$.

To conclude, $(n+1)(n+2)\cdots (2n)$ is divisible by $2^n$, but not by $2^{n+1}$. □