# Placing n balls in r boxes(with a maximum of one ball per box)

489 views

How many ways are there to:

1. Put n distinguishable balls in r distinguishable boxes?
2. Put n indistinguishable balls in r distinguishable boxes?
3. Put n distinguishable balls in r indistinguishable boxes?
4. Put n indistinguishable balls in r indistinguishable boxes?

Where, $r \geq n$

retagged

1. r^n

2. (r+n-1)Cn

3.its quite tricky,the fact that balls are distinguisable makes problem difficulty.

problem is that {{b1,b2,b5},{b3,b4},{b6}} is one arrangement of these balls.so here the relative order of balls need to be                   preserved. i.e a bijection of <3,2,2> doesnt work

here there are 3 baskets (partitions ) and 6 balls(elements) now the job is partitioning a set of size n into r partitions.  but                 here the partions will be mutually exclusive and exhaustive but maybe empty.

so a trick to use is sum rule,where you calculate the number of ways of partitioning n balls in  r non empty partions,then (r-1)         non empty partions,(r-2),....2,1.

so total ways=s(n,r)+s(n,r-1)+.......s(n,1)

4.a simple bijective mapting of sample space to <> 0001000101000...000010.   where 0 represents balls and  two 1's represnts a box. only job is to calculate diffrent number of such numbers where there are n zeros and (r-1) ones  given by ((n+r-1)Cr)/r! .

its simply extension of 2nd questions,assume 3 boxes which are distigusibale so a arrangemnt <3,2,4> represnts box 1 has 3 balls,box 2 has 2 balss and box 3 has 4 balls.now <4,2,3> represents another arrangment since boxes are distingusibale but   if there are indistinguabale then both above sequneces represnets same arrangement,so <4,2,3><4,3,2><2,3,4><2,4,3><3,2,4><3,4,2> maps to {4,2,3} thus there is divide by 6(3! or r!(general)) .

0

@Viv696.

For the 3rd question. My understanding is like this. Its similar to question 1 except the boxes are indistinguishable. Now, assuming boxes are distinguishable, there are rn ways. But once you place the balls in boxes, the boxes are indistinguishable. So, divide by r!

Basically, label the boxes as {1,2,3......,r}. Now, they can be arranged in r! ways. But they have said boxes are indistinguishable, SO we divide by r!.

I dont know what do you mean by order of balls.

I too don't have answer key for this problem but here is my take at this,
Assuming one ball per box allowed
(1). $r * (r-1)*(r-2)*...*(r-n+1)$, because every ball is unique as is every box and we assume one ball per box, so we have r choices for the first ball, r-1 for the second ball and so on, at the same time we also need to count all permutations of placement of these balls.

(2). $\binom{r}{n}$, because in this case, which boxes are selected for placing the balls matter but which ball is kept in which box does not.

(3). 1, since $r \geq n$ and it does not matter in which box we put a ball.

(4). 1, since both balls and boxes are indistinguishable.

reshown

## Related questions

1
219 views
The number of ways six distinct balls be distributed into 3 distinct urns. If each urn contain at least one ball are ____
The number of ways in which $2n$ white and $2n$ black balls can be arranged such that no consecutive $n$ white balls are together, is ${}^{2n+1}C_2 + {}^{4n}C_{2n}$ ${}^{2n+1}C_2 - {}^{2n+1}C_1. {}^{3n}C_{n} (-1)^n + {}^{4n}C_{2n}$ ${}^{2n+1}C_2+ (-1)^n. {}^{2n+1}C_1 . {}^{3n}C_n + {}^{4n}C_{2n}$ ${}^{2n+1}C_2+ (-1)^n. {}^{3n}C_n . {}^{2n+1}C_1$