Doubt in distributing $n$ different objects in $r$ different bins

47 Views Asked by At

My attempt - $n$ distinct objects in $r$ distinct bins

One way would be $n^r$ ways.

I have doubt in other method which I did in following way.

Say I choose $k_i~\forall i=1 \text{ to } r$ objects and place them in "$i^{th}$" bin.

Also $k_1+k_2+ \ldots + k_r=n$

Total number of ways of doing this = $\sum_{k_r=0}^n ...\sum_{k_2=0}^n\sum_{k_1=0}^n \binom{n}{k_1}\binom{n-k_1}{k_2}\binom{n-k_1-k_2}{k_3} ....\binom{n-k_1-k_2..-k_{r-1}}{k_r}$ (Please note that $\binom{n}{k} = nCk$)

The above expression by combinatorics seem fine to me. But I am not able to proceed from here.

1

There are 1 best solutions below

0
On

If we are placing $n$ distinct objects in $r$ distinct bins, then we have $r$ choices for where we place each of the $n$ objects, so there are $r^n$ possible distributions of the objects.

If we place $k_i$ objects in bin $i$, where $1 \leq i \leq r$, then $$k_1 + k_2 + k_3 + \ldots + k_r = n$$ The total number of ways we can distribute the $n$ objects in the $r$ bins is $$\sum_{k_1 + k_2 + k_3 + \ldots + k_r = n} \binom{n}{k_1}\binom{n - k_1}{k_2}\binom{n - k_1 - k_2}{k_3} \ldots \binom{n - k_1 - k_2 - \ldots - k_{r - 1}}{k_r}$$ where we sum over all $r$-tuples $(k_1, k_2, k_3, \ldots, k_r)$ of nonnegative integers with sum $n$. The term $$\binom{n}{k_1}\binom{n - k_1}{k_2}\binom{n - k_1 - k_2}{k_3} \ldots \binom{n - k_1 - k_2 - \ldots - k_{r - 1}}{k_r}$$ can be expressed as the multinomial coefficient $$\binom{n}{k_1, k_2, k_3, \ldots, k_r} = \frac{n!}{k_1!k_2!k_3!\ldots k_r!}$$ which arises in the Multinomial Theorem, a generalization of the Binomial Theorem. It states that $$(x_1 + x_2 + x_3 + \ldots + x_r)^n = \sum_{k_1 + k_2 + k_3 + \ldots + k_r = n} \binom{n}{k_1, k_2, k_3, \ldots, k_r}\prod_{j = 1}^{r}x_j^{k_j}$$ If we set $x_j = 1$ for $1 \leq j \leq r$, we obtain $$r^n = \sum_{k_1 + k_2 + k_3 + \ldots + k_r = n} \binom{n}{k_1, k_2, k_3, \ldots, k_r}$$ which is the number of ways of distributing $n$ distinct objects to $r$ distinct bins.