[Math] Number of ways of placing 6 distinct balls into 3 distinct boxes with no box empty

combinatoricspermutations

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?

Best Answer

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.

Related Question