Help me understand the proof (PnC)

[agile zinc]

Here

[covert nexus]

1. Do not ping the Moderators, unless someone is breaking the rules.
2. Do not ping the Helper Moderators, unless there is a conflict between helpers.
3. Do not ping other members randomly for help.
4. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
5. Wait patiently for a helper to come along.
6. If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:

+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[agile zinc]

Theorem: The total number of ways of dividing n identical items among r persons, each one of whom, can receive $0,1,2,$ or more itmes ($ \textless n$) is ${n+r-1}\choose{r-1}$

Proof:
Consider "r" brackets corresponding to "r" persons. In each bracket, taka an expression given by $x^0 + x^2+x^3+....+x^n$.Here, the various powers of $x$ viz; 0,1,2,....n correspond to the number of items each person can have in the distribution.
Since the total number of items is n. So, the required number of ways is the coefficient of $xn$ in the product
$$(x^0 + x^2+x^3+....+x^n)(x^0 + x^2+x^3+....+x^n).....(x^0 + x^2+x^3+....+x^n)$$ (total "r" brackets)

thus, the required number of ways;
=$$\text{Coefficient of} x^n (x^0 + x^2+x^3+....+x^n)^r$$
=$$\text{Coefficient of} x^n \text{in} \left(\frac{1-x^{n+1}}{1-x}\right)^r$$
=$$\text{Coefficient of} x^n \text{in} (1-x^{n+1})^r(1-x)^-r$$
=$$\text{Coefficient of} x^n \text{in} (1-x)^-r$$
=$$\frac{(r+1)(r+2)...(r+n-1)}{1\cdot2\cdot3.....r}$$
=$${n+r-1}\choose{r-1}$$

[drifting drum]

Satyam

[chilly oriole]

This is a... very dumb proof.

Actually, you probably shouldn't try to reproduce a proof you don't understand. Maybe take a picture of it instead.

[agile zinc]

I would call it a "dumb proof" if i've known a "genius proof".

[agile zinc]

Nah, This proof is mentioned in book.

[chilly oriole]

...so then take a picture of it.

[chilly oriole]

Okay, that's... not better.

Okay, so.

Think about it like this.

[agile zinc]

yes...

[chilly oriole]

So do you, like, understand polynomial expansion?

[agile zinc]

I'm familiar with expansion of binomials and multinomials.

[chilly oriole]

Okay, the thing to understand is that it's basically just distribution.

$(x^0 + x^1 + x^2 + x^3 + ... + x^n)(x^0 + x^1 + ... + x^n)(x^0 + x^1 + ... + x^n)... = x^0(x^0 + x^1 + ... + x^n)(x^0 + x^1 + ... + x^n)... + x^1(x^0 + x^1 + ... + x^n)... + ... + x^n(x^0 + x^1 + ... + x^n)...$

[drifting drum]

Techie Literate

[agile zinc]

so, did you just multiply the each brackets? or more specifically you just open the brackets?

[chilly oriole]

Maybe this will be clearer.

$(x^0 + x^1 + ... + x^n)^r = x^0 (x^0 + x^1 + ... + x^n)^{r - 1} + x^1(x^0 + x^1 + ... + x^n)^{r - 1} + ... + x^n(x^0 + x^1 + ... + x^n)^{r - 1}$

[drifting drum]

Techie Literate

[agile zinc]

ok...what's next?

[chilly oriole]

Okay, so.

The first thing to establish is that the coefficient of x^n is in fact the number we're after.

So let's think about where these coefficients and powers of x come from.

[agile zinc]

yes

[chilly oriole]

Where in this polynomial do we get x^0?

[agile zinc]

last term.

[chilly oriole]

What do you mean, "last term"?

[agile zinc]

Polynomial is of form $a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}.....a_0x^{0}$ , since you asked "where in the polynomial do we get $x^0$" , it's last term, maybe i interpreted your question differently..

[drifting drum]

Satyam

[chilly oriole]

How do we get an x^0 term?

[agile zinc]

p(0), where p(x) is any polynomial?

[chilly oriole]

Okay, it's midnight here, so I can't help you anymore unfortunately.

[agile zinc]

okay.

[young leaf]

Search up "generating functions".

[austere verge]

@agile zinc there is a better intuitive proof

If you want ping me

[chilly oriole]

This seems more like a proof designed to introduce students to the concept of a generating function by using one to prove a result they already know, and even in that light it's not great, but as a proof of this result it's completely unmotivated. I have a better one, it's called stars and bars.

[austere verge]

I think I have the same one I call it coins and sticks 🤷‍♂️

[agile zinc]

@austere verge Sure, maybe i know that proof as well,

[agile zinc]

Can you share it here?

[agile zinc]

How does it help?

[austere verge]

@agile zinc imagine you have n coins

say you want to divide them in 2 parts

[agile zinc]

ok..

[austere verge]

you can add a 1 stick anywhere so left side would be 1 part and right would be other

if you put the stick on edge then one of the parts can become zero

[agile zinc]

oh yeah.

[austere verge]

so if want to divide in r parts what do you do?

[agile zinc]

Maybe, we can put the stick in ${n+1}\choose{1}$ ways?

[drifting drum]

Satyam

[austere verge]

lets take a simple example

you want to divide in 3parts

you can add 2 sticks

right part middle part and left part

[agile zinc]

yeah..

[austere verge]

so what if you want to divide in r parts

[agile zinc]

For "r" parts, we take (r-1) sticks?

[austere verge]

yes

nice

so now we have n alike coins and r-1 alike sticks how many ways can we arrange them?

[agile zinc]

$\frac{n!}{n!}\cdot(r-1)!$ maybe?

[drifting drum]

Satyam

[austere verge]

well no

whats total number of items

[agile zinc]

wait, mb it's $\frac{(n+r-1)!}{n!(r-1)!}$

[austere verge]

close but sticks should be alike as well otherwise we will overcount cases

[agile zinc]

yeah

[austere verge]

youd have to divde with (r-1)! as well

[drifting drum]

Satyam

[austere verge]

exactlu

which simplifies to C(n+r-1 , r-1)

[agile zinc]

But how does this proof explains the original theorem?

[agile zinc]

This..

[austere verge]

I said i had a better proof not related

[austere verge]

.

[agile zinc]

theorem "

[austere verge]

well you have n alike objects to divide in r ways

in case of 2 right side one divison and left side one divison

in case of 3 you have 2 sticks so three parts

and they can have zero if stick is at edge

[agile zinc]

we've to distribute n identical items among r persons, each can recieve any number of items.

[austere verge]

yeah thats what we did

[agile zinc]

Got it..

[austere verge]

we needed n objects divided into r parts

[agile zinc]

Yeah, i understood now, thanks bhai.

[austere verge]

sure?

[agile zinc]

yeah, it's really good and easy to understand proof, idk what was mentioned in the "RD sharma" -_-

[austere verge]

yeah those books

only usew for questions

[agile zinc]

Thanks man a lot

[austere verge]

np

[agile zinc]

close it?

[austere verge]

you can do +close

[agile zinc]

+close

[tender burrow]

Please thank your Helpers before closing!

Please thank the helpers who assisted you by clicking the buttons below. You can thank each helper only once. Once you're done, click "Close Post" to close this thread.

[austere verge]

if its all clear

[tender burrow]

Thank you for your feedback! NoobExploded has been awarded 1 . They now have 4 . They have 1 daily left for today.