Let m, n be positive integers, prove that m!n! is a divisor or (m+n)!
Please, help

- Loser66

Let m, n be positive integers, prove that m!n! is a divisor or (m+n)!
Please, help

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- mom.

*of

- ParthKohli

\[\frac{(m+n)!}{m!n!}\]This expression happens to be the number of ways you can divide \(m+n\) objects into two groups of \(m\) and \(n\) objects. Which is obviously integral.

- ParthKohli

Or you could think of it as the coefficient of \(x^m y^n\) in the expansion of \((x+y)^{m+n}\)

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- Loser66

This is my attempt but I doubt myself when it is so easy.
WLOG m < n < m+n
hence m ! is a divisor of n!
and n! is a divisor of (m+n)!

- ParthKohli

Eh, you want to take that route. It's pretty clear that your expression is \(\large \binom{m+n}{m}\) but still...\[\frac{(m+n)!}{m!n!}\]\[= \frac{(m+1)(m+2)(m+3) \cdots (m+n)}{1\cdot 2 \cdots \cdot n}\]Pigeonhole Principle tells us that in a series of consecutive \(n\) numbers, we have at least one that is divisible by \(n\), at least one divisible by \(n-1\), and so on.

- Loser66

Hold on, that is what we have to prove.

- Loser66

Only thing I think I can expand is
(m+n)! = (m+n) (m+n -1) (m+n-2) .........(m+n -m) (n-1) (n-2).....2*1

- Loser66

the last part is n!

- ganeshie8

combinatoric method that PK has shown earlier is a legitimate proof

- Loser66

One more thing, my prof gives me hint: You may use the fact that \( [x] +[y]\leq [x+y]\)
where [ ] is floor function

- ganeshie8

If you have \(m+n\) people in your class, then the number of ways of choosing \(m\) people for basketball team is given by \(\dbinom{m+n}{m}\).
Clearly, the number of choices cannot be a fraction.

- ganeshie8

I know that proof using floor funciton, one sec...

- ganeshie8

consider the prime factorization of \(n!\).
do you remember how to get the exponent of a prime \(p\) ?

- ganeshie8

for example, what is the exponent of \(3\) in the prime factorization of \(20!\) ?

- Loser66

yes, it is
\[\lfloor x/p\rfloor+\lfloor x/p^2\rfloor+.....\]

- ganeshie8

good, remember that, we're going to need that in the proof using floor functions

- Loser66

Show me, please

- ganeshie8

maybe below could be an even better start :
for each prime factor \(p\) of the denominator term, \(m!n!\), we have :
\[\left[ \dfrac{\color{red}{m}+\color{blue}{n}}{p^k}\right]\ge \left[\dfrac{\color{red}{m}}{p^k}\right]+\left[\dfrac{\color{green}{n}}{p^k}\right]\]

- ganeshie8

fine with that ?
i have just used the given hint, nothing fancy..

- Loser66

Go ahead, I just don't see the link yet but pretty sure it will pop out next.

- Loser66

I got the equation, next?

- Loser66

the exponent of prime p on (m+n)!

- ganeshie8

For each prime factor \(p\) of the denominator term, \(m!n!\), we have :
\[\left[ \dfrac{\color{red}{m}+\color{blue}{n}}{p^k}\right]\ge \left[\dfrac{\color{red}{m}}{p^k}\right]+\left[\dfrac{\color{green}{n}}{p^k}\right]\]
It follows :
\[\sum\limits_{k\ge 1}\left[ \dfrac{\color{red}{m}+\color{blue}{n}}{p^k}\right]\ge \sum\limits_{k\ge 1}\left[\dfrac{\color{red}{m}}{p^k}\right]+\sum\limits_{k\ge 1}\left[\dfrac{\color{green}{n}}{p^k}\right]\]

- ganeshie8

what does left hand side expression, \(\sum\limits_{k\ge 1} \left[ \dfrac{\color{red}{m}+\color{blue}{n}}{p^k}\right]\), represent ?

- Loser66

The total exponent of p on (m+n)! where p is a prime factor of (m+n)!

- ganeshie8

good, what about the right hand expression, \(\sum\limits_{k\ge 1}\left[\dfrac{\color{red}{m}}{p^k}\right]+\sum\limits_{k\ge 1}\left[\dfrac{\color{green}{n}}{p^k}\right]\)
what does that represent ?

- Loser66

oh, the same, for the first one it is exponent of p on m! , second is on n!

- ganeshie8

right, when you add both exponents, you get the exponent of the denominator, \(m!n!\), yes ?

- ganeshie8

so, the right hand side represents the exponent of \(p\) in the prime factorization of \(m!n!\)

- Loser66

And since they are exponent , hence the right hand side becomes p^m p^n

- Loser66

Got you. Thank you so much.

- ganeshie8

what do you mean by :
`hence the right hand side becomes p^m p^n `

- Loser66

oh, just too exciting when understanding it. hehehe... I know it is not the correct notation,

- Loser66

the first sum is \(p^{r}\) which is a prime factor of m!
the second sum is \(p^{s}\) which is a prime factor of n!
hence \(p^{r+s}\) is a prime factor of m! n!
right?

- Loser66

And this prime is < the same prime factor of (m+n)! from the left hand side
That shows m!n! is a factor of (m+n)! , right?

- ganeshie8

Looks perfect!

- Loser66

Thanks again.

- ganeshie8

np

Looking for something else?

Not the answer you are looking for? Search for more explanations.