How many ways can we put $n+2$ different balls into $n$ different cells?

There are $n \gt 0$ different cells and $n+2$ different balls. Each cell cannot be empty. How many ways can we put those balls into those cells?

My solution:

Let's start with putting one different ball to each cell. for the first cell there are $n+2$ options to choose a ball. .. for the $n$th cell there are $3$ options to choose a ball. total : $\frac{(n+2)!}{2!}$

Now we got $2$ balls left and my question is: Can I change the way I choose? I mean until now I choose for each cell a ball. Can I now choose for each of the balls that left a unique cell? Is this legal? If the answer is yes, then let's choose for each ball a cell ($n$ options for picking up a cell) so we get $n^2$ options to put $2$ balls in $n$ cells.

we get: $\frac{(n+2)!}{ 2!} n^2$

Is this correct?

Your answer is incorrect. Using your method, you could place a red ball in the first cell when you place one ball in each cell, then add a blue ball to the first cell when you add the two additional balls or vice versa. The outcome is the same, but you have counted it twice.

To correct your answer, use the Inclusion-Exclusion Principle. There are $n$ choices for each of the $n + 2$ balls, so there are $n^{n + 2}$ ways of placing the balls in boxes. From these, we must exclude those distributions in which fewer than $n$ boxes receive a ball. There are $\binom{n}{k}$ ways of selecting $k$ boxes to not receive a ball and $(n - k)^{n + 2}$ ways to distribute the balls to the remaining $n - k$ boxes. Hence, by the Inclusion-Exclusion Principle, there are $$\sum_{k = 0}^{n} (-1)^k\binom{n}{k}(n - k)^{n + 2}$$ ways of distributing $n + 2$ balls to $n$ boxes so that no box is left empty.

• The balls are non-identical. – Stav Alfi Jun 12 '16 at 13:19

Start by splitting up.

$n+2=3+1+1+\cdots+1$ corresponding with one cell that contains exactly $3$ balls.

There are $\binom{n+2}{3}$ possibilities to choose $3$ balls, and there are $n!$ possibilities to spread out the units (one containing $3$ balls and the others containing one ball) over $n$ cells.

$n+2=2+2+1+\cdots+1$ corresponding with two cells that contains exactly $2$ balls.

There are $\frac{1}{2}\binom{n+2}{2}\binom{n}{2}$ possibilities to choose $2$ pairs of balls, and again $n!$ possibilities to spread out the units (two containing $2$ balls and the others containing one ball) over $n$ cells.

(Note that the factor $\frac12$ repairs double counting here)

So in total there are $$\left[\binom{n+2}{3}+\frac{1}{2}\binom{n+2}{2}\binom{n}{2}\right]n!$$ possibilities.

• For $n=2$, your answer gives 1. Something's wrong. – Peter Shor Jun 12 '16 at 13:20
• @PeterShor Yes, you were right (thank you). I repaired. – drhab Jun 12 '16 at 13:26
• I did not understand why you devided in 2: $\frac{1}{2}\binom{n+2}{2}\binom{n}{2}$. Can you be more specific? – Stav Alfi Jun 12 '16 at 13:49
• Suppose that $n=2$ so there are $4$ balls: $A,B,C,D$. Then $\binom42\binom22=6$ is the cardinality of the set that has $(\{A,B\},\{C,D\})$, $(\{A,C\},\{B,D\})$, $(\{A,D\},\{C,B\})$, $(\{B,C\},\{A,D\})$, $(\{B,D\},\{A,B\})$ and $(\{C,D\},\{A,B\})$ as elements. The number of possibilities to choose $2$ pairs of balls is $\frac126=3$. E.g. the elements $(\{A,B\},\{C,D\})$ and $(\{C,D\},\{A,B\})$ both correspond with pair $\{\{A,B\},\{C,D\}\}$. So that pair is originally double counted. We start with counting ordered pairs. Then a correction because we are actually aiming at unordered pairs. – drhab Jun 12 '16 at 15:13
• Got it! Thank you very much! Your answer is excellent just like the one I accepted. Thank you agian for your time! – Stav Alfi Jun 12 '16 at 15:29

One possible way, to count the possibilities, is as follows:

There are two possibilities: 1- one cell has three balls 2- two cells have two balls each

for the first situation, $3$ balls are chosen out of $n+2$. the $3$ balls can be considered as one unique ball and would make $n$ balls with the rest of the balls. So we get

$\binom{n+2}{3}n!$

for the second situation, with the same way of thinking, we get

$\frac{\binom{n+2}{4}\binom{4}{2}n!}{2}$

Then you just need to add them up.

• Can you explain how you got to $\frac{\binom{n+2}{4}\binom{4}{2}n!}{2}$ exactly? – Stav Alfi Jun 12 '16 at 13:43
• you need two blocks of two balls. each block is like one unique ball. so, we choose 4 out of n+2 ball. then 2 out of the 4 balls to make the first block. the remaining two balls would make the second block. but, we have over counted cases. 1 2|3 4 is the same as 3 4|1 2. Due to symmetry, we can divide it by two. – Med Jun 12 '16 at 13:54

Alternatively: Proceed as you did, but consider as two separate cases those ways where one cell gets $3$ balls and those where $2$ cells get $2$ each.

There are $\frac{(n+2)!}{2!}\;n$ ways to place $n$ of the balls in the cells, one ball per cell, then to pick one cell for the remaining balls. As N.F.Taussig said, this counts outcomes more than once; in fact it counts each outcome thrice, because, of the $3$ balls in the chosen cell, any of them could have been the ball that went in there first. So we divide by $3$, getting $\frac{(n+2)!}6\;n$.

There are $\frac{(n+2)!}{2!}\;{n(n-1)}$ ways to place $n$ of the balls in the cells, one ball per cell, then to pick different cells for the $2$ remaining balls. We must now divide by $2$, twice, because for each of the $2$ picked cells, either of the $2$ balls in it could have been the ball that went in there first. Thus $\dfrac{(n+2)!n(n-1)}8$.

The total is thus $\dfrac{(n+2)!n(4+3(n-1))}{24}=\dfrac{(n+2)!n(3n+1)}{24}$.

There are either two boxes that have two balls each, or one that has three, and these are mutually exclusive options.

For the first, pick the two two-ball boxes in $\binom{n}{2}$ ways. There are $\binom{n+2}{2}$ ways to put two balls in the one with smaller index, and after that we have $\binom{n}{2}$ ways to put two different balls in the other box. Then we are left with $n-2$ balls for $n-2$ boxes, which we can distribute in $(n-2)!$ ways.

For the second, pick one special box ($n$ ways), then 3 balls ( in $\binom{n+2}{3}$ ways) and then we distribute $n-1$ balls over equally many boxes.