0

The number of ways of distributing $n$ identical items among $r$ people such that each one of them receives at least one is $\binom{n-1}{r-1}$. Can you please give a simple proof to explain how is this theorem derived ? Thanks .

Aditi
  • 1,349
  • Also see https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) – Ross Millikan Nov 13 '17 at 16:38
  • Line up the $n$ items in a row; they are all identical. We have to somehow partition these $n$ elements among $r$ people so that each person gets at least one thing. Let the first of these n items belong to the 1st person; he possibly gets a few more; the second person starts getting balls from a certain place; after that the third person starts getting balls from a subsequent place. Thus, the question is about choosing these $(r-1)$ starting balls for these $(r-1) $ people, out of the $(n-1)$ balls barring the first ball. – Aritro Pathak Nov 13 '17 at 16:39
  • @RossMillikan thanks for the link , but isn’t that concept used when each person gets one , more or even none? Here each person should get atleast one right ? So how do we do it ? – Aditi Nov 13 '17 at 16:50
  • The link does it both ways. If you allow people to not get any, you add one to how many each gets, so you distribute $n+r$ items instead of $n$ with each person getting at least one. Then you take one item away from each person. That makes the ways with zero permitted $n+r-1 \choose r-1$ – Ross Millikan Nov 13 '17 at 18:56

1 Answers1

1

Let no of things with person$_1$ be $=x_1+1$

Let no of things with person$_2$ be $=x_2+1$ $$\vdots$$ Let no of things with person$_r$ be $=x_r+1$

We know that total no of objects are $n$, $$x_1+1+x_2+1+x_3+1+x_4+1\cdots +x_r+1=n$$ $$x_1+x_2+x_3+\cdots +x_r=n-r$$ So we want no of integral solutions to this, Formula for it is given by,$$=\binom{n-1}{r-1}$$ Hence....

neonpokharkar
  • 1,834