The question says that there are r identical balls to be placed in n boxes s.t. $r\geq n$ .How many ways are there such that each box contains atleast one object?The solution is $n+r-n-1\choose n-1$.

Here ,they have considered the distribution of $(r-n)$ objects(assuming all boxes having filled with 1 ball each) and then got the formula. The doubt I have is that

why don't we also take the step of distributing those at least one balls into each boxes also into consideration.

Why does this step does not matter? Please help..

  • $\begingroup$ If we were to take the step of distributig those at least one ball into each boxes also, you will have empty boxes which contradicts what the question wants!! $\endgroup$ – Satish Ramanathan Sep 4 '14 at 13:18
  • $\begingroup$ @satishramanathan why can't it be like $1$st ball has $n$ possibilities ,$2$nd has $n-1$ possibilities $\ldots\ldots$last ball has 1 possibility. $\endgroup$ – spectraa Sep 4 '14 at 13:24

$r$ identical balls in $n$ distinct boxes, $r\ge n$, with at least one ball in each box is equivalent to

$$[(r-n) \text{identical balls in }n\text{ distinct boxes}]\cdot[n\text{ identical balls in }n\text{ distinct boxes}].$$

The problem separates into two regions where the total number of balls in each region is fixed, AND we are only concerned with rearrangements within each region. The latter holds because the balls are identical - any swap between the two regions (swaps of course maintaining the constraint of total ball number in each region) will not generate a new solution.

The "$n$ identical balls in $n$ boxes" region is a question of permutations of the $n$ balls. This is $\dfrac{n!}{n!}=1$ - not just $n!$. Because all the balls are identical, all the rearrangements are also identical.

$R$ identical balls in $N$ distinct boxes is given by $C(R+N-1,N-1)$ - considering $N-1$ "separators" + $R$ balls, the problem is reduced to counting permutations e.g. $4$ boxes $5$ balls ~ number of permutations of $XXXxxxxx$ where the $X$ delimit the boxes.

The solution is then $C(r-n+n-1,n-1)$, as stated.

  • $\begingroup$ thanks for the beautiful explanation. $\endgroup$ – spectraa Sep 4 '14 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.