11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There might be some clever way, but this is where I would start counting primes. Are there enough $2$'s in the numerator? $3$'s? $\endgroup$ – Arthur Aug 15 '17 at 7:23
  • $\begingroup$ Use the fact that every set of $k $ integers will have one integer divisible by $k $. Show that that means $(m+1)(m+2).... (m+k) $ will be divisible by $k! $. And that means $(1*2....10)(11*... 20)...... (191*....200) $ is divisible by $10!*10!*....10!$. $\endgroup$ – fleablood Aug 15 '17 at 7:26
  • $\begingroup$ That's an interesting friend you have there. $\endgroup$ – uniquesolution Aug 15 '17 at 7:30
  • $\begingroup$ To eliminate 19! Not that all k divide 10*k. Then each 10k+1 to 10k+9 is divisible by 9! And 10k/k = 10 so it is divisible by 10 as well. $\endgroup$ – fleablood Aug 15 '17 at 7:34
  • 1
    $\begingroup$ An interesting question (at least I think it would be) is what is the largest integer $k$ so that $k!*10^{20}$ divides $200!$. $\endgroup$ – fleablood Aug 15 '17 at 16:27
9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But this is my answer ... $\endgroup$ – user8277998 Aug 16 '17 at 8:49
  • $\begingroup$ @123: I see... I cited an answer that I wrote and didn't see that you had parenthetically cited the question to which that was an answer. However, without the connection given by the citations, the answers do not look the same. If this bothers you, I will delete my answer. $\endgroup$ – robjohn Aug 16 '17 at 13:01
  • $\begingroup$ @123: I have added another proof of the same identity to differentiate our answers. I will still delete this answer if you think they are too close. $\endgroup$ – robjohn Aug 16 '17 at 13:28
  • $\begingroup$ No, I have no problem with your answer, you can keep it as it is. $\endgroup$ – user8277998 Aug 16 '17 at 14:36
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I would appreciate the down-voters to at least comment ... $\endgroup$ – rtybase Aug 15 '17 at 8:29
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Don't you mean it is divisible by $10!*(k+1)$ ? $\endgroup$ – Jaap Scherphuis Aug 15 '17 at 7:55
  • $\begingroup$ Yeah, I guess I did. $\endgroup$ – fleablood Aug 15 '17 at 16:22
0
$\begingroup$

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);
 }
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.