In how many ways $n$ distinct objects can be distributed to $k$ identical bins if bins may be left empty?

Question

In how many ways $n$ distinct objects can be distributed to $k$ identical bins if bins may be left empty?

---

$$\sum_{r_{1}+...+r_{k}=n}^{ }\frac{1}{k!}\binom{n}{r_1}\binom{n-r_1}{r_2}\cdot\cdot\cdot\binom{n-...-r_{k-1}}{r_k}$$$$\frac{1}{k!}\sum_{r_{1}+...+r_{k}=n}^{ }\frac{n!}{r_{1}!r_{2}!\cdot\cdot\cdot r_{k}!}$$$$\frac{k^{n}}{k!}$$

I noticed that the answer is given by $$\sum_{r=0}^{k}{ n \brace k-r}$$

Where ${ n \brace k}$ denotes Stirling numbers of the second kind.

But my first answer is not true. can someone explain the reason?

Answer 1

Let $i$ be the number of bins that are not empty. Then the Stirling number $S(n, i)$ is equal to the number of ways to distribute the $n$ objects into the $i$ bins, such that none are empty. Now, all that is left is to sum over all possible values of $i$. See the following for a concrete example: distribution of distinct objects into identical boxes .

Answer 2

You ask for the reason that your first attempt was incorrect. To see why, let us look for outcomes which are counted too many times or not enough times. To find such an outcome, let us in particular look at the extreme cases.

The outcome where all objects end up in the same bin occurs in your summation a total of $k$ times. Once when $r_1=n,r_2=r_3=\dots=r_k=0$, again when $r_2=k,r_1=r_3=r_4=\dots=0$ and so on. The multinomial coefficient that results, (i.e. the product of binomial coefficients), was just equal to $1$ as there is only one way to have all balls put in the first bin and zero balls in all other bins, equivalently $\binom{n}{n}\binom{0}{0}\binom{0}{0}\cdots \binom{0}{0}=1$ and $\binom{n}{0}\binom{n}{0}\cdots\binom{n}{n}\binom{0}{0}\cdots = 1$ and so on.

So... if we were to look at how much this one case contributed to your overall sum, we see that there were $k$ occurrences of $\frac{1}{k!}$ which were added, so this one outcome contributed $\dfrac{k}{k!}$ or $\dfrac{1}{(k-1)!}$ to the sum. But... we wanted it to have contributed $1$ time to the overall sum, so something must have gone wrong.

What has gone wrong is that your dividing by $k!$ was too much. Only scenarios where all sizes of bins were different were counted $k!$ times. Meanwhile, scenarios where certain values of $r_i$ were equal were counted fewer times. If we wanted to correct this, we would need to pay attention to how many ways we could have assigned $r_1,r_2,\dots,r_k$ to the bins themselves. Alternatively, we could have put a restriction on the summation so that we instead summed over the cases where $r_1\leq r_2\leq r_3\leq \dots\leq r_k$. In either event however, we are no longer able to use the multinomial theorem.

---

The approach with stirling numbers of the second kind is correct. It is worth mentioning as well that the problem's answer has its own name, the Bell Numbers and does indeed have the identity that you found that $B_n = \sum\limits_{k=0}^n{n\brace k}$. For more common "balls-in-bins" type questions, you should read further about Stanley's Twelvefold Way.

---

As a final comment, it is always a good idea to look at extreme cases for any counting problem. For instance, seeing if the answer you come up with worked correctly for $0$ or $1$ bin, or if it worked for $0$ or $1$ ball, or like here looking at what happened when all balls went in the same bin, etc... These extreme cases are often quite easy to count by hand and hopefully easy to calculate in your formula (since arithmetic involving $0$'s and $1$'s often simplify quickly). In doing so, you are more likely to catch mistakes (though there are still times when even more careful analysis is needed).

Answer 3

There are some "traps" to avoid in the process to get an answer to your question,
so allow me to proceed by elementary steps.

Suppose you have $n$ labeled balls $\left\{ {1,2, \cdots ,n} \right\}$ and $m$ boxes in a row (we do not say yet if distinguishable or not) with capacity $$ \left[ {c_1 ,c_2 , \cdots ,c_m } \right]\quad \left| \matrix{ \;0 \le c_j \hfill \cr \;c_1 + c_2 + \cdots + c_m = c \hfill \cr} \right. $$ summing to $c$, where some of the capacities might be null

To totally fill those boxes, with distinct balls and distinguishing the order in which they are placed, we have:
$$n\left( {n - 1} \right) \cdots \left( {n - \left( {c_{\,1} - 1} \right)} \right) = n^{\,\underline {\,c_{\,1} \,} } $$ choices for the first,
$$\left( {n - c_{\,1} } \right)\left( {n - c_{\,1} - 1} \right) \cdots \left( {n - \left( {c_{\,1} + c_{\,2} - 1} \right)} \right) = \left( {n - c_{\,1} } \right)^{\,\underline {\,c_{\,2} \,} }$$ for the second, and so forth, and thus $$ \bbox[lightyellow] { \eqalign{ & n^{\,\underline {\,c_{\,1} \,} } \left( {n - c_{\,1} } \right)^{\,\underline {\,c_{\,2} \,} } \cdots \left( {n - \left( {c_{\,1} + \cdots + c_{\,m - 1} } \right)} \right)^{\,\underline {\,c_{\,m} \,} } = \cr & = n^{\,\underline {\,c\,} } = \left( \matrix{ n \cr c \cr} \right)c! \cr} }$$ in total. Clearly we cannot wholly fill the boxes if $n < c$.
That corresponds to choose a subset of $c$ balls out of $n$, permute it, separate and lay into the boxes.
From now on we can leave out the factor $\binom{n}{c}$ and assume $n=c$.

a) Now if the boxes are distinct and not limited in capacity, the balls are distinct, and their placing inside a box is distinct, then the above multiplied by the number of weak/strong compositions of $n$ into $m$ parts, i.e. $$ \bbox[lightyellow] { \eqalign{ & N_{LL} (n,m) = \left( \matrix{ n + m - 1 \cr n \cr} \right)n! = m^{\,\overline {\,n\,} } \cr & L_{LL} (n,m) = \left( \matrix{ n - 1 \cr n - m \cr} \right)n! \cr & N_{LL} (n,m) = \sum\limits_k {\left( \matrix{ m \cr k \cr} \right)L_{LL} (n,k)} \cr} } \tag{a}$$ give the number of ways to fill the boxes with ($N$) or without ($L$) empty boxes, with $n$ balls.

We are speaking of partitioning the $n$ distinct balls into a list of $m$ lists $$ \left[ {\underbrace {\left[ {\matrix{ 2 \cr 5 \cr } } \right], \left[ 1 \right],\left[ \emptyset \right],\left[ {\matrix{ 4 \cr 6 \cr 3 \cr } } \right], \cdots ,\left[ {\matrix{ \vdots \cr \vdots \cr } } \right]}_{m\,{\rm lists}}} \right] $$

b) If instead the placing of the balls in each box is undistinct, i.e. if upon placing a batch of balls inside a box they are re-ordered by label, then we are speaking of a list of sets $$ \left[ {\underbrace {\left\{ {\matrix{ 5 \cr 2 \cr } } \right\}, \left\{ 1 \right\},\left\{ \emptyset \right\}, \left\{ {\matrix{ 6 \cr 4 \cr 3 \cr } } \right\}, \cdots ,\left\{ {\matrix{ \vdots \cr \vdots \cr } } \right\}} _{m\,{\rm sets}}} \right] $$ Therefore in the filling process, upon picking each batch $c_k$ we shall de-permute it, that is $$ \eqalign{ & {{n^{\,\underline {\,c_{\,1} \,} } } \over {\,c_{\,1} !}} {{\left( {n - c_{\,1} } \right)^{\,\underline {\,c_{\,2} \,} } } \over {c_{\,2} !}} \cdots {{\left( {n - \left( {c_{\,1} + \cdots + c_{\,m - 1} } \right)} \right)^{\,\underline {\,c_{\,m} \,} } } \over {\,c_{\,m} \,!}} = \cr & = {{n^{\,\underline {\,n\,} } } \over {\,c_{\,1} !c_{\,2} !\, \cdots c_{\,m} \,!}} = \left( \matrix{ n \cr c_{\,1} ,c_{\,2} ,\, \cdots ,c_{\,m} \cr} \right) \cr} $$ and sum over the compositions on $n$ into $m$ parts to get $$ \bbox[lightyellow] { \eqalign{ & L_{LS} (n,m) = \sum\limits_{\left\{ {\matrix{ {1\, \le \,c_{\,k} \,\left( { \le \,n} \right)} \cr {c_{\,1} + \,c_{\,2} + \cdots \, + c_{\,m} \, = \,n} \cr } } \right.} {\;\left( \matrix{ n \cr c_{\,1} ,\,c_{\,2} , \cdots \,,c_{\,m} \, \cr} \right)} \cr & N_{LS} (n,m) = \sum\limits_{\left\{ {\matrix{ {0\, \le \,c_{\,k} \,\left( { \le \,n} \right)} \cr {c_{\,1} + \,c_{\,2} + \cdots \, + c_{\,m} \, = \,n} \cr } } \right.} {\;\left( \matrix{ n \cr c_{\,1} ,\,c_{\,2} , \cdots \,,c_{\,m} \, \cr} \right)} = n^{\,m} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} {\left( \matrix{ m \cr j \cr} \right)\sum\limits_{\left\{ {\matrix{ {1\, \le \,c_{\,k} \,\left( { \le \,n} \right)} \cr {c_{\,1} + \,c_{\,2} + \cdots \, + c_{\,j} \, = \,n} \cr } } \right.} {\;\left( \matrix{ n \cr c_{\,1} ,\,c_{\,2} , \cdots \,,c_{\,j} \, \cr} \right)} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} {\left( \matrix{ m \cr j \cr} \right)L_{LS} (n,m)} \cr} } \tag{b}$$ That is the same if we sequentially launch distinct or undistinct balls into distinct boxes, because the balls landing in a box will be ordered according to the launching sequence.

c) If in the above the boxes are undistinct , then for those non-empty, which are all distinct by content, we will get a partition into set of sets which is $1/(m!)$ of the above and which by definition is counted by the Stirling N. 2nd kind.
The empty boxes will be grouped at the beginning, so $$ \left\{ {\underbrace {\left\{ \emptyset \right\}, \cdots ,\left\{ \emptyset \right\}, \left\{ 1 \right\},\left\{ {\matrix{ 5 \cr 2 \cr } } \right\}, \left\{ {\matrix{ 6 \cr 4 \cr 3 \cr } } \right\}, \cdots }_{m\,{\rm sets}}} \right\} $$ and $$ \bbox[lightyellow] { \eqalign{ & L_{SS} (n,m) = \left\{ \matrix{ n \cr m \cr} \right\} = {1 \over {m!}}\sum\limits_{\left\{ {\matrix{ {1\, \le \,c_{\,k} \,\left( { \le \,n} \right)} \cr {c_{\,1} + \,c_{\,2} + \cdots \, + c_{\,m} \, = \,n} \cr } } \right.} {\;\left( \matrix{ n \cr c_{\,1} ,\,c_{\,2} , \cdots \,,c_{\,m} \, \cr} \right)} \cr & N_{SS} (n,m) = \sum\limits_{j = 0}^m {L_{SS} (n,j)} = \sum\limits_{j = 0}^m {\left\{ \matrix{ n \cr j \cr} \right\}} \cr} } \tag{c}$$

d) Finally, if the boxes are un-distinct, the balls are distinct, and their placing inside a box is distinct we have a set of lists $$ \left\{ {\underbrace {\left[ \emptyset \right], \cdots ,\left[ \emptyset \right], \left[ 1 \right],\left[ {\matrix{ 2 \cr 5 \cr } } \right], \left[ {\matrix{ 4 \cr 6 \cr 3 \cr } } \right], \cdots } _{m\,{\rm lists}}} \right\} $$ and the number of non-empty boxes will be $1/(m!)$ of that in a), i.e. $$ \bbox[lightyellow] { \eqalign{ & L_{SL} (n,m) = \left( \matrix{ n - 1 \cr n - m \cr} \right){{n!} \over {m!}} = {\rm Lah}\;{\rm N}{\rm .} \cr & N_{SL} (n,m) = \sum\limits_{j = 0}^m {L_{SL} (n,j)} = \sum\limits_{j = 0}^m {\left( \matrix{ n - 1 \cr n - j \cr} \right) {{n!} \over {j!}}} \cr} } \tag{d}$$

In conclusion, the answer to your question will be d) or c) depending on whether you are considering or not the order of the balls inside each box, otherwise said if you "pour" or "launch" the balls into the boxes.

Answer 4

Empty bins are already indistinguishable, so $k!$ is too much.

Your formula $k^n / k!$ looks initially plausible— it is the number of functions from $n$ objects to $k$ bins, divided by the number of permutations $k!$ so as to make the bins indistinguishable.

The factor of $k!$ is intended to prevent double-counting solutions that are just rearrangements of indistinguishable bins, so that an assignment like $a|b|c$ is equivalent to $b|a|c$.

Unfortunately, there's a problem with this counting method. The problem comes from rearranging the labels on indistinguishable bins that are empty. The $k^n$ formula already counts empty bins as indistinguishable from one another. When you divide everything by a factor $k!$, you are dividing by too much, assuming that you need to make $k$ things indistinguishable, when you only need to make the remaining $\ell$ occupied boxes in each case indistinguishable.

---

An example could help. When $n=3$ and $k=3$, we have that

$$\frac{k^n}{k!} = \frac{3^3}{3!} = \frac{9}{2} = 4.5$$ $$\left\{ {3 \atop 3}\right\} = 5$$

The five actual solutions (ways of assigning three objects to three indistinguishable bins) are $$abc | \cdot |\cdot\\ bc | a | \cdot\\ac|b|\cdot \\ ab|c|\cdot \\ a | b| c$$

To contrast with your formula, I'll show you how to get back to $k^n=3^3=27$ original options (when the objects and bins are both distinguishable). If you multiply each option by $\frac{n!}{e!}$, where $e$ is the number of empty bins, you reintroduce the original asymmetry where the bins were distinguishable:

$$\begin{align*}3!/2! \qquad & abc | \cdot |\cdot\\ 3!/1! \qquad & bc | a | \cdot\\ 3!/1! \qquad & ac|b|\cdot \\ 3!/1! \qquad & ab|c|\cdot \\ 3!/0! \qquad & a | b| c\\\hline 27 \qquad& \end{align*}$$

For example, in the second row, the factor $3!/1!$ reminds us that we are collapsing $3!/1!=6$ solutions into one: a|bc|, a||bc, |a|bc, bc|a|, bc||a, |bc|a.