Loser66
  • Loser66
Let m, n be positive integers, prove that m!n! is a divisor or (m+n)! Please, help
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
mom.
  • mom.
*of
ParthKohli
  • 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
  • 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
  • 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
  • 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
  • Loser66
Hold on, that is what we have to prove.
Loser66
  • 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
  • Loser66
the last part is n!
ganeshie8
  • ganeshie8
combinatoric method that PK has shown earlier is a legitimate proof
Loser66
  • 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
  • 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
  • ganeshie8
I know that proof using floor funciton, one sec...
ganeshie8
  • ganeshie8
consider the prime factorization of \(n!\). do you remember how to get the exponent of a prime \(p\) ?
ganeshie8
  • ganeshie8
for example, what is the exponent of \(3\) in the prime factorization of \(20!\) ?
Loser66
  • Loser66
yes, it is \[\lfloor x/p\rfloor+\lfloor x/p^2\rfloor+.....\]
ganeshie8
  • ganeshie8
good, remember that, we're going to need that in the proof using floor functions
Loser66
  • Loser66
Show me, please
ganeshie8
  • 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
  • ganeshie8
fine with that ? i have just used the given hint, nothing fancy..
Loser66
  • Loser66
Go ahead, I just don't see the link yet but pretty sure it will pop out next.
Loser66
  • Loser66
I got the equation, next?
Loser66
  • Loser66
the exponent of prime p on (m+n)!
ganeshie8
  • 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
  • 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
  • Loser66
The total exponent of p on (m+n)! where p is a prime factor of (m+n)!
ganeshie8
  • 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
  • Loser66
oh, the same, for the first one it is exponent of p on m! , second is on n!
ganeshie8
  • ganeshie8
right, when you add both exponents, you get the exponent of the denominator, \(m!n!\), yes ?
ganeshie8
  • ganeshie8
so, the right hand side represents the exponent of \(p\) in the prime factorization of \(m!n!\)
Loser66
  • Loser66
And since they are exponent , hence the right hand side becomes p^m p^n
Loser66
  • Loser66
Got you. Thank you so much.
ganeshie8
  • ganeshie8
what do you mean by : `hence the right hand side becomes p^m p^n `
Loser66
  • Loser66
oh, just too exciting when understanding it. hehehe... I know it is not the correct notation,
Loser66
  • 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
  • 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
  • ganeshie8
Looks perfect!
Loser66
  • Loser66
Thanks again.
ganeshie8
  • ganeshie8
np

Looking for something else?

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