Prove that $\frac{100!}{50!\cdot2^{50}} \in \Bbb{Z}$

I'm trying to prove that :

$$\frac{100!}{50!\cdot2^{50}}$$

is an integer .

For the moment I did the following :

$$\frac{100!}{50!\cdot2^{50}} = \frac{51 \cdot 52 \cdots 99 \cdot 100}{2^{50}}$$

But it still doesn't quite work out .

Hints anyone ?

Thanks

• Think the numbers of multiple of 2, multiple of 4, multiple of 8, ..., etc in {51, 52, ..., 99, 100}.
– Flan
Commented Jul 7, 2013 at 14:40
• Using \displaystyle in the title is depreciated. Commented Jul 7, 2013 at 14:42
• If you make it dependent on $n$, then this is called a double factorial. Commented Jul 8, 2013 at 8:22

$$\frac{(2n)!}{n! 2^{n}} = \frac{\prod\limits_{k=1}^{2n} k}{\prod\limits_{k=1}^{n} (2k)} = \prod_{k=1}^{n} (2k-1) \in \Bbb{Z}.$$

We have $100$ people at a dance class. How many ways are there to divide them into $50$ dance pairs of $2$ people each? (Of course we will pay no attention to gender.)

Clearly there is an integer number of ways. Let us count the ways.

We solve first a different problem. This is a tango class. How many ways are there to divide $100$ people into dance pairs, one person to be called the leader and the other the follower?

Line up the people. There are $100!$ ways to do this. Now go down the line, pairing $1$ and $2$ and calling $1$ the leader, pairing $3$ and $4$ and calling $3$ the leader, and so on.

We obtain each leader-follower division in $50!$ ways, since the groups of $2$ can be permuted. So there are $\dfrac{100!}{50!}$ ways to divide the people into $50$ leader-follower pairs to dance the tango.

Now solve the original problem. To just count the number of democratic pairs, note that interchanging the leader/follower tags produces the same pair division. So each democratic pairing gives rise to $2^{50}$ leader/follower pairings. It follows that there are $\dfrac{100!}{2^{50}\cdot 50!}$ democratic pairings.

Combinatorial argument:

The number of ways to arrange the digits $1,1,2,2,3,3,4,4,5,5,\ldots, 50,50$ in a row is $\frac{100!}{2^{50}}$.

This is clearly a multiple of $50!$, since we can perform any of the $50!$ permutations on the set of 50 elements.

• nice for combinatorial argument! Commented Jul 7, 2013 at 15:10
• It's not so clear to me. How does a permutation of 50 relate to a permutation of 100?
– Mark
Commented Jul 7, 2013 at 18:02
• @Mark If you jointly permute the $1$s, $2$s, and so on ... Commented Jul 8, 2013 at 14:06

$$100!=(1\cdot 3\cdot 5\cdots 99)\cdot (2\cdot 4\cdot 6\cdots 100),$$

where

$$(2\cdot 4\cdot 6\cdots 100)=2^{50}\cdot (1\cdot 2\cdot 3\cdots 50)=2^{50}\cdot 50!$$

so

$$(50\cdot 2)! = 2^{50}\cdot 50!\cdot (1\cdot 3\cdot 5\cdots 99)$$

More generally $$(m\cdot n)! \, =\, m^{n}\ \cdot\ n!\ \cdot\ \prod_{(k,\, j) \ =\ (1,\,1)}^{(n,\, m-1)}\, (m\cdot k-j)$$ Your case is $$n=50, m=2$$ and the product on the right is a natural number.

Prove $51\cdot 52\cdots 100$ is divisible by $2^{50}$. Hint: Count how many multiples of 2, 4, 8... there are in the former expression.

From here and here, we have that the highest power of a prime $p$ dividing $n!$ is given by $$\sum_{k=1}^{\infty}\left\lfloor\dfrac{n}{p^k} \right\rfloor$$ Hence, the highest power of a prime $p$ dividing $\dfrac{n!}{m!}$ is given by $$\sum_{k=1}^{\infty}\left\lfloor\dfrac{n}{p^k} \right\rfloor - \sum_{k=1}^{\infty}\left\lfloor\dfrac{m}{p^k}\right\rfloor$$

I trust you can finish it off from here.

for the number of multiples of $2$:

$$100 = 52 + 2(n_1 - 1)$$ $$n_1 = 25$$

for the number of multiples of $4$:

$$100 = 52 + 4(n_2 - 1)$$ $$n_2 = 13$$

for the number of multiples of $8$:

$$96 = 56 + 8(n_3 - 1)$$ $$n_3 = 6$$

for the number of multiples of $16$:

$$96 = 64 + 16(n_4 - 1)$$ $$n_4 = 3$$

for the number of multiples of $32$:

$$96 = 64 + 32(n_5 - 1)$$ $$n_5 = 2$$

for the number of multiples of $64$:

$$64 = 64 + 64(n_6 - 1)$$ $$n_6 = 1$$

To get the number of $2$'s as factors, add all the $n$'s up, which yields $50$.

This should cancel the $2^{50}$ at the denominator, and thus prove that the expression is an integer.