How many ways to put $10$ distinguishable balls in $5$ identical boxes so that no box has more than $3$ balls?

Question

As the title says, I was asked to count the number of ways one can put $10$ different balls inside $5$ identical boxes so that no box has more than $3$ balls. I am really confused by the restriction and I can't even compute the number without the restriction (It confuses me that the boxes can't be distinguished but the balls are). Any explanation is more than welcome.

Answer 1

I am unaware of any analytical approach to the problem.

The best that I can do is break down the distributions into cases, and enumerate each case. In the discussion below, I will let $n_k$ denote the enumeration for Case $k$, for $k \in \{1,2,3,4,5\}$.

So, the final tally will be

$$N = n_1 + n_2 + n_3 + n_4 + n_5.$$

The balls are distinguishable, and the boxes are not distinguishable. In the discussion below, I will examine various distributions.

---

$\underline{\text{Case 1}}$

Distribution is $3-3-3-1-0.$

Superficially, the enumeration is:

$$\binom{10}{3}\times \binom{7}{3} \times \binom{4}{3} \times \binom{1}{1} = \frac{(10)!}{(3!)^3}. \tag1 $$

However, consider the situation where

• Ball-10, Ball-9, Ball-8 comprise Group-1.

• Ball-7, Ball-6, Ball-5 comprise Group-2.

• Ball-4, Ball-3, Ball-2 comprise Group-3.

In (1) above, this particular grouping will be counted $(3!)$ times, rather than only being counted once. This is because there are $(3!)$ ways that the creations of Group-1, Group-2, and Group-3 might have been ordered.

Further, this over-counting by a factor of $(3!)$ will apply regardless of which (distinguishable) balls are used to create Group-1, Group-2, and Group-3.

So, you have that

$$n_1 = \frac{(10)!}{(3!)^3} \times \frac{1}{3!} = 2800.$$

It is important to note that the over-counting adjustment factor was required specifically because some of the groups were the same size.

---

$\underline{\text{Case 2}}$

Distribution is $3-3-2-2-0.$

Again, superficially, the enumeration is:

$$\binom{10}{3}\times \binom{7}{3} \times \binom{4}{2} \times \binom{2}{2} = \frac{(10)!}{(3!)^2 \times (2!)^2}. \tag2 $$

In (2) above, you have two over-counting factors to consider. The two groups of $3$ could have been arranged in $(2!)$ ways, and the two groups of $2$ could have been arranged in $(2!)$ ways.

So, you have that

$$n_2 = \frac{(10)!}{(3!)^2 \times (2!)^2} \times \frac{1}{(2!)^2} = 6300.$$

---

$\underline{\text{Case 3}}$

Distribution is $3-3-2-1-1.$

Again, superficially, the enumeration is:

$$\binom{10}{3}\times \binom{7}{3} \times \binom{4}{2} \times \binom{2}{1} \times \binom{1}{1} = \frac{(10)!}{(3!)^2 \times (2!)}. $$

Similar to the previous section, you have two groups of $3$ and two groups of $1$.

So, you have that

$$n_3 = \frac{(10)!}{(3!)^2 \times (2!)} \times \frac{1}{(2!)^2} = 12600.$$

---

$\underline{\text{Case 4}}$

Distribution is $3-2-2-2-1.$

Again, superficially, the enumeration is:

$$\binom{10}{3}\times \binom{7}{2} \times \binom{5}{2} \times \binom{3}{2} \times \binom{1}{1} = \frac{(10)!}{(3!) \times (2!)^3}. $$

You have three groups of $2$.

So, you have that

$$n_4 = \frac{(10)!}{(3!) \times (2!)^3} \times \frac{1}{(3!)} = 12600.$$

---

$\underline{\text{Case 5}}$

Distribution is $2-2-2-2-2.$

Again, superficially, the enumeration is:

$$\binom{10}{2}\times \binom{8}{2} \times \binom{6}{2} \times \binom{4}{2} \times \binom{2}{2} = \frac{(10)!}{(2!)^5}. $$

You have five groups of $2$.

So, you have that

$$n_5 = \frac{(10)!}{(2!)^5} \times \frac{1}{(5!)} = 945.$$

---

$\underline{\text{Final Enumeration}}$

$$N = n_1 + n_2 + n_3 + n_4 + n_5$$

$$= 2800 + 6300 + 12600 + 12600 + 945 = 35245.$$

Answer 2

A comparison with distinct balls in distinct boxes$\;$ vs$\;$ identical boxes yields a simple transformation (although $5$ cases can't be avoided here)

For the pattern $3-3-3-1-0,\;$ for distinct balls to distinct boxes, we have the product of two factorials,

[Fill Pattern]$\times$[permute Pattern]$\;= \large\frac{10!}{3!3!3!1!0!}\cdot\frac{5!}{3!1!1!}$

The simple transformation for identical boxes is to change the numerator of the second term to $1$,
thus $\quad\large\frac{10}{3!3!3!1!0!}\cdot\frac{1}{3!1!1!}$

So we simply apply this transform to each allowable pattern, viz.

$3-3-3-1-0:\;\;\large\frac{10!}{3!3!3!1!0!}\cdot\frac{1}{3!1!1!}$

$3-3-2-2-0:\;\frac{10!}{3!3~2!2!0!}\cdot\frac1{2!2!1!}$

$3-3-2-1-1:\;\frac{10!}{3!3!2!1!1!}\cdot\frac{1}{2!1!2!}$

$3-2-2-2-1:\;\frac{10!}{3!2!2!2!1!}\cdot\frac1{1!3!1!}$

$2-2-2-2-2:\;\frac{10}{2!2!2!2!2!}\cdot\frac1{5!}$

Computing and adding up, the answer is $\boxed{35245}$