Question

Give a combinatorial proof that 2n divides n! Whenever n is an even positive integer. (Hint: Use Theorem 3 in Section 6.5 to count the number of permutations of 2n objects where there are two indistinguishable objects of n different types.

Short answer

This quantity is a positive integer, this implies that \(2m|\left( {2m} \right)!\)

Step-by-step solution

Given

\(n\) is an even positive integer.

Proof:

Let us calculate the number of different permutations of\(2m\)objects, where there are\(2\)indistinguishable objects of\(m\)types viz.

Type\(1\), type

\(2\),…and type\(m\).

First the\(2\)number of type\(1\)objects can be placed among the possible\(2m\)positions in

\(\left( \begin{aligned}{l}2m\\2\end{aligned} \right)\)ways, and then the type\(2\)objects can be placed in two the remaining \(2m - 2\)places in exactly .

\(\left( \begin{aligned}{l}2m - 2\\2\end{aligned} \right)\)Ways and so on .

Thus, the total number of permutation

\(\left( \begin{aligned}{l}2m\\2\end{aligned} \right).\left( \begin{aligned}{l}2m - 2\\2\end{aligned} \right)....\left( \begin{aligned}{l}2\\2\end{aligned} \right) = \frac{{\left( {2m} \right)!}}{{\left( {2m - 2} \right)!2!}} = \frac{{\left( {2m} \right)!}}{{{{\left( {2!} \right)}^m}}}\)

Since, this quantity is a positive integer, this implies that\(2m|\left( {2m} \right)!\)or in other words if\(n\)is an even integer then\({2^{\frac{n}{2}}}|n!\)

Hence proved .