Distinguishable balls into distinguishable bins : what is wrong with my approach?

Question

The question is this: How many ways are there to put 5 different balls into 3 different boxes so that none of the boxes is empty?

The correct answer as per my lecturer's notes is 150, and I would like to know where I am going wrong in my approach.

Here is how I approached it (wrongly):

Separated into three tasks:

1) Picking three balls from 5 to put in the boxes

           {5 \choose 3} ways

2) Permuting those balls

            3! ways

3) Placing the other two balls can be done in two ways:

Either put both in one of the boxes

   3 ways

Or put both each in a different box

    P(3,2) ways to pick two boxes and arrange the balls in them

Task 3 has a total of

   6 +3 = 9 ways

Total using product rule is (as per my approach, which is incorrect):

   60 * (9) = 540

I have seen other approaches to getting the correct answer(including using Stirling numbers of the second kind followed by permutation, inclusion-exclusion), but would like to know what is the correct way to split this into tasks and use the product rule (without using Stirling numbers).

Answer 1

You could also modify your original approach to account for the double counting.

After your step two, your 60 is correct.

Addressing your two possibilities:

The two extra balls are in different containers: your six is correct but each answer appears four times (2 pairs of balls in cups and either member could have been part of the initial three placed), so this possibility is 60 x 6 / 4 = 90

The two extra balls are in the same container has 3 three possibilities but each one is a triple count so 60 x 3 /3 = 60.

Adding them together yields 150.

Answer 2

If you are familiar with the multinomial theorem, you know that the coefficient of $x^iy^jz^k$ in the expansion of $(x+y+z)^5$ is how many ways you can arrange the five balls into the boxes such that there are $i$ balls in box $x$, $j$ balls in box $y$ and $k$ in $z$.
Since we want to find all terms $x^iy^jz^k$ such that $i,j,k\ge 1$ we start by taking from $(x+y+z)^5$ all the terms that have only two letters or one letter, $(x+y+z)^5-(x+y)^5-(x+z)^5-(y+z)^5$. However, now you are taking an extra $x^5$, $y^5$, $z^5$ from the expansion, since each of these letters appears twice in the subtracting terms, therefore, you add them and call the resulting expression $$f(x,y,z)=(x+y+z)^5-(x+y)^5-(x+z)^5-(y+z)^5+x^5+y^5+z^5$$ You could expand this by hand or in WA to see that all the terms you do not want indeed cancel out and then sum the coefficients of the remaining terms, but to get the answer, since you only want to add the coefficients of the generating function, you can compute $f(1,1,1)=3^5-3(2^5)+3=150$ to get the answer

Answer 3

Other answers and comments have pointed to the mistake in your argument.

If you don't want to bring in Stirling numbers or inclusion/exclusion you can argue as follows:

Five balls can be split into three nonempty heaps in exactly two ways: $${\rm (a)}\quad 3+1+1\>,\qquad({\rm b})\quad 2+2+1\ .$$ In case (a) we can choose the two boxes getting one ball in $3$ ways and then the two balls going into the first, resp., the second of these boxes in $5\cdot 4$ ways. The remaining balls go into the remaining box. Makes $3\cdot5\cdot 4=60$ possibilities.

In case (b) we can choose the box receiving $1$ ball in $3$ ways, and then select this ball in $5$ ways. The remaining $4$ balls can be paired off in $3$ ways, and the two resulting pairs can then then be dropped into the remaining boxes in $2$ ways. Makes $3\cdot5\cdot 3\cdot 2=90$ possibilities.

It follows that there are $60+90=150$ possibilities in all.