Question

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

Answer 1

*of

Answer 2

\[\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.

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

Hold on, that is what we have to prove.

Answer 7

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

Answer 8

the last part is n!

Answer 9

combinatoric method that PK has shown earlier is a legitimate proof

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

consider the prime factorization of \(n!\).

do you remember how to get the exponent of a prime \(p\) ?

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

Show me, please

Answer 18

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]\]

Answer 19

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

Answer 20

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

Answer 21

I got the equation, next?

Answer 22

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

Answer 23

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]\]

Answer 24

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

Answer 25

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

Answer 26

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 ?

Answer 27

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

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

Got you. Thank you so much.

Answer 32

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

Answer 33

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

Answer 34

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?

Answer 35

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?

Answer 36

Looks perfect!

Answer 37

Thanks again.

Answer 38

np