2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.