distributing different balls into different boxes

Question

I have this question:

1. Find in how many ways we can distribute $10$ similar balls to $4$ different boxes such that in no box there are exactly $3$ balls.
2. Find in how many ways we can distribute $10$ different balls to $4$ different boxes such that no box has exactly $3$ balls

For the first part, I did the inclusion-exclusion principle. I used $|U− (A_1 \cup A2 \cup A_3)| = S_0-S_1+S_2-S_3$.

Firstly, $U = D(4,10) = {13 \choose 10}$, $S_1 = 4 \cdot {9 \choose7}$ because we put $3$ balls in one box, $S2= {4 \choose 2} \cdot {5 \choose 4}$ because now we have $6$ balls in $2$ boxes, $S_3 = {4 \choose 3} \cdot {1 \choose 1}$. We get that $S_0- S_1+S_2-S_3=166$.

For the second part of the question, which is the part I couldn't get through, I thought about the inclusion-exclusion principle same as before, but this time $U = 4^{10}$, $S_1 = 4 \cdot {10 \choose 3} \cdot 3^7$ because we need to put $3$ balls in the first box so we have ${10 \choose 3}$ options and then there are $7$ different balls left for $3$ different boxes so we go $3^7$, and there are $4$ more options as well.

I wanted to know if my way of thinking is right? and if I should keep the second question as I started it. Just felt wrong and lost too much guessing in it ..

Thanks to any helpers!

Answer 1

In how many ways can we distribute $10$ indistinguishable balls to $4$ different boxes such that no box receives exactly three balls?

Your strategy is correct. However, $$\binom{13}{10} - \binom{4}{1}\binom{9}{7} + \binom{4}{2}\binom{5}{4} - \binom{4}{3}\binom{1}{1} = 286 - 144 + 30 - 4 = 168$$

In how many ways can we distribute $10$ different balls to $4$ different boxes such that no box has exactly three balls?

What you have done so far is correct.

There are four ways to distribute each of the $10$ balls, so there are $4^{10}$ ways to distribute the balls without restriction.

From these, we must subtract those cases in which one or more of the boxes receives exactly three balls.

A box receives exactly three balls: There are four ways to select the box which receives exactly three balls, $\binom{10}{3}$ ways to select which three balls that box receives, and $3^7$ ways to distribute the remaining seven balls to the remaining three boxes. Thus, there are $$\binom{4}{1}\binom{10}{3}3^7$$ such distributions.

Two boxes each receive exactly two balls: There are $\binom{4}{2}$ ways to select which two boxes receive exactly three balls, $\binom{10}{3}$ ways to select which three balls are placed in the leftmost of those boxes, $\binom{7}{3}$ ways to select which three of the remaining seven balls are placed in the other box which is selected to receive exactly three balls, and $2^4$ ways to distribute the remaining four balls to the remaining two boxes. Hence, there are

$$\binom{4}{2}\binom{10}{3}\binom{7}{3}2^4$$

such distributions.

Three boxes each receive exactly three balls: There are $\binom{4}{3}$ ways to select which three boxes receive exactly three balls, $\binom{10}{3}$ ways to select which three balls are placed in the leftmost of those boxes, $\binom{7}{3}$ ways to select three of the remaining seven balls is placed in the middle of those boxes, $\binom{4}{3}$ ways to select which three of the remaining four balls is placed in the rightmost of those boxes, and one way to place the remaining ball in the remaining box. Hence, there are

$$\binom{4}{3}\binom{10}{3}\binom{7}{3}\binom{4}{3}1^1$$

such distributions.

By the Inclusion-Exclusion Principle, the number of ways ten distinct balls can be distributed to four distinct boxes so that no box receives exactly three balls is

$$4^{10} - \binom{4}{1}\binom{10}{3}3^7 + \binom{4}{2}\binom{10}{3}\binom{7}{3}2^4 - \binom{4}{3}\binom{10}{3}\binom{7}{3}\binom{4}{3}1^1$$