Is $\frac{200!}{(10!)^{20} \cdot 19!}$ an integer or not?

A friend of mine asked me to prove that $$\frac{200!}{(10!)^{20}}$$ is an integer

I used a basic example in which I assumed that there are $200$ objects places in $20$ boxes (which means that effectively there are $10$ objects in one box). One more condition that I adopted was that the boxes are distinguishable but the items within each box are not. Now the number of permutations possible for such an arrangement are : $$ \frac{200!}{\underbrace{10! \cdot 10! \cdot 10!\cdots 10!}_{\text{$20$ times}}}$$ $$\Rightarrow \frac{200!}{(10!) ^{20}}$$

Since these are just ways of arranging, we can be pretty sure that this number is an integer.

Then he made the problem more complex by adding a $19!$ in the denominator, thus making the problem: Is $$\frac{200!}{(10!)^{20} \cdot 19!}$$ an integer or not?

The $19!$ in the denominator seemed to be pretty odd and hence I couldn't find any intuitive way to determine the thing. Can anybody please help me with the problem?

Solution 1:

You assumed the boxes were distinguishable, leading to $\frac{200!}{(10!)^{20}}$, ways to fill the boxes. If you make them indistinguishable, you merge the $20!$ ways of reordering the boxes into one, so that previous answer overcounts each way of filling indistinguishable boxes by a factor of $20!$. Therefore you are left with $\frac{200!}{(10!)^{20}}/20!$ ways to fill 20 indistinguishable boxes, which then must be an integer. After multiplying by $20$ it is of course still an integer.

Solution 2:

We know that $\dfrac{(mn)!}{n!(m!)^n}$ is an integer for $m,n \in \Bbb N$ $^{(*)}$ . Let $n = 20$ and $m = 10$, then $\dfrac{(200)!}{20!(10!)^{20}}$ is an integer.

Multiply by $20$, $\dfrac{(200)!}{19!(10!)^{20}}$ is an integer.

$(*)$ : Prove that $(mn)!$ is divisible by $(n!)\cdot(m!)^n$

Solution 3:

Using induction, this answer says that $$ \frac{(mn)!}{(m!)^nn!}=\prod_{k=1}^n\binom{mk-1}{m-1} $$ Plug in $m=10$ and $n=20$ to get $$ \frac{200!}{10!^{20}\,20!}=\prod_{k=1}^{20}\binom{10k-1}{9} $$ Multiply by $20$ to get $$ \frac{200!}{10!^{20}\,19!}=20\,\prod_{k=1}^{20}\binom{10k-1}{9} $$

Another Approach

Note that $$ \begin{align} \binom{kn}{n} &=\frac{(kn-n+1)(kn-n+2)\cdots(kn-1)\,kn}{1\cdot2\cdots(n-1)\,n}\\ &=\frac{(kn-n+1)(kn-n+2)\cdots(kn-1)\,k}{1\cdot2\cdots(n-1)}\\ &=\binom{kn-1}{n-1}\,k \end{align} $$ Therefore, since we can write a multinomial as a product of binomials, $$ \begin{align} \frac{(mn)!}{n!^m} &=\prod_{k=1}^m\binom{kn}{n}\\ &=\prod_{k=1}^m\binom{kn-1}{n-1}\,k\\ &=m!\,\prod_{k=1}^m\binom{kn-1}{n-1} \end{align} $$ and so $$ \frac{(mn)!}{n!^m\,m!}=\prod_{k=1}^m\binom{kn-1}{n-1} $$ Plug in $m=20$ and $n=10$ and multiply by $20$ to get $$ \frac{200!}{10!^{20}\,19!}=20\,\prod_{k=1}^{20}\binom{10k-1}{9} $$

Solution 4:

A long version: $$\frac{200!}{10!^{20} \cdot 19!}=\frac{30\cdot31\cdot .. \cdot200}{10!^{19}}\cdot \frac{29!}{10!\cdot(29-10)!}=...$$ which is $$...=\frac{30\cdot31\cdot .. \cdot200}{10!^{19}}\cdot \binom{29}{10}=\\ \frac{\color{red}{30} ..\color{red}{40} ..\color{red}{50} ..\color{red}{60}..\color{red}{70}..\color{red}{80}..\color{red}{90}..\color{red}{10^2}..\color{red}{110}..\color{red}{120}..\color{red}{130}..\color{red}{140}..\color{red}{150}..\color{red}{160}..\color{red}{170}..\color{red}{180}..\color{red}{190}..\color{red}{2\cdot10^{2}}}{10!^{19}}\cdot \binom{29}{10}=...$$ $20$ numbers divisible by 10, or $$3\cdot4\cdot5\cdot..\cdot9\cdot11\cdot..\cdot19\cdot20\cdot\frac{31..39\cdot41..49\cdot51..59\cdot..\cdot191..199}{9!^{19}}\cdot \binom{29}{10}=\\ 10\cdot\frac{2..9\cdot11..19\cdot31..39\cdot41..49\cdot51..59\cdot..\cdot191..199}{9!^{19}}\cdot \binom{29}{10}=...$$ cardinality of $\{31,41,51,61,71,81,91,101,111,121,131,141,151,161,171,181,191\}$ is 17 $$...=10\cdot \frac{1..9}{9!}\cdot\frac{11..19}{9!}\cdot\frac{31..39}{9!}\cdot..\cdot\frac{191..199}{9!}\cdot \binom{29}{10}=\\ 10\cdot \binom{9}{9} \cdot \binom{19}{9} \cdot \binom{39}{9}\cdot .. \cdot \binom{199}{9} \cdot \binom{29}{10}$$