Number of ways of placing 6 distinct balls into 3 distinct boxes with no box empty?

Question

I am currently looking at the following question:

Find the number of possible distributions of 6 distinguishable balls in 3 distinct boxes, in such a way that each box contains at least one ball?

The following method was my attempt to solve this problem:

1. First, choose 1 ball to go in each box so that no box is empty. This can be done in $P(6,3) = 120$ ways.
2. With a ball in every box, we know need to allocate the 3 remaining balls between the 3 boxes. By the multiplication principle, there are $3 \times 3 \times 3 = 27$ ways to do this.
3. Thus, by the multiplication principle, the number of ways of allocating the balls is $120 \times 27 = 3240$

However, I have the solutions to this problem and know that the correct answer is 540.

Can anyone tell me why my method gave the wrong answer?

Answer 1

You overcounted. Label the balls $1$ through $6$ and let the boxes be $B_1,B_2,B_3$. Now suppose that

• In the first step you assign ball $1$ to $B_1$, ball $2$ to $B_2$ and ball $3$ to $B_3$.
• In the second step you assign all remaining balls to $B_1$.

The end result would be the same if you had instead

• In the first step assigned ball $x$ to $B_1$, ball $2$ to $B_2$ and ball $3$ to $B_3$, where $x\in\{4,5,6\}$
• In the second step assigned all remaining balls to $B_1$.

In this particular instance, the same end scenario $(B_1$ with balls $\{1,4,5,6\}$, $B_2$ with ball $2$ and $B_3$ with ball $3)$ was counted four times.

---

If you are interested in the answer to this problem, notice that it is equivalent to finding all surjective functions $f: \{1,2,3,4,5,6\}\longrightarrow\{1,2,3\}$. This is answered in the infamous twelvefold way, and the answer is

$$3!\cdot\left\{\begin{array}{c}6\\3\end{array}\right\},$$

where $\left\{\begin{array}{c}n\\k\end{array}\right\}$ is a Stirling number of the second kind, which counts the number of ways to partition a set of $n$ labelled objects into $k$ nonempty unlabelled subsets.