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

Question

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?

Answer 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.

Answer 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$

Answer 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} $$

Answer 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}$$

Answer 5

Consider $V=(10k+1)*....*(10k+9) $.

By your reasoning, ${10k+9 \choose 9}=(10k+1)*....*(10k+9)/9! $ is an integer.

And $10(k+1)/10(k+1)$ is an integer.

So $(10k+1)*....*(10 (k+1)) $ is divisible by $9!*10*(k+1)=10!*(k+1)$.

So $200! $ is divisible by $10!*1*10!*2*10!*3*.....*10!*19=(10!)^{20}*19! $

Answer 6

I computed the answer just for fun using Java, and it's indeed an integer!

41355508127520659545494261323391337886154686759988983912363570790033502473625361601944917427369977161391866491251801111884812210789772970682172860398969828337097889527312353089859289462934116034461288917394623420753412096000000

import java.math.BigDecimal;
import java.math.RoundingMode;

public class JustForFun{
 public static void main(String []args){
    BigDecimal thFact = new BigDecimal("1");
    BigDecimal tenFact = null, ntFact = null, tenFactPow20 = null;
    /* Computes 200! and stores it in a */ 
    for (int i = 1; i <= 200; i++) {
        thFact = thFact.multiply(new BigDecimal(i + ""));
        /* stores 10! in b */
        if (i == 10)
            tenFact = thFact;
        /* stores 19! in c */
        if (i == 19)
            ntFact = thFact;
    }
    tenFactPow20 = tenFact.pow(20);
    tenFactPow20 = tenFactPow20.multiply(ntFact);
    thFact = thFact.divide(tenFactPow20);
    System.out.println(thFact);
 }
}

Answer 7

Since I am pushing 70 yrs old, it seems appropriate to dinosaur-excerpt "Elementary Number Theory" 1938 (Uspensky and Heaslett).

For real # $r$, let $\lfloor r\rfloor \equiv$ the floor of $r$.

Let $p$ be any prime #.
Let $V_p(n) : n ~\in ~\mathbb{Z^+} ~\equiv~$ the largest exponent $\alpha$ such that $p^{\alpha} | n$.
That is, if $\alpha = V_p(n),$ then $p^{(\alpha + 1)} \not | ~n.$

From Uspensky and Heaslett, $V_p(n!) = \left\lfloor\frac{n}{p^1}\right\rfloor ~+~ \left\lfloor\frac{n}{p^2}\right\rfloor ~+~ \left\lfloor\frac{n}{p^3}\right\rfloor ~+~ \left\lfloor\frac{n}{p^4}\right\rfloor \cdots $

Clearly, given two positive integers $A,B$, $~\frac{A}{B}$ will be an integer $\iff$
for every prime # $p$ that occurs in the prime factorization of $B$,
$V_p(B) \leq V_p(A).$

It is immediate, that given the OP's original question, the only prime #'s that need to be checked are those prime #'s that are $\leq 19.$ Further, you can see at a glance the prime #'s 11, 13, 17, and 19 can not pose a problem.

Therefore, the problem reduces to manually applying Uspenky and Heaslett's formula to the numerator and denominator of the OP's original query with respect to the prime #'s 2,3,5,7.

Empirically, they each check out okay. Therefore, the fraction is an integer.

In your face $21^{\text{st}}$ century!