Find the number of ways in which $7$ different balls can be distributed into 4 identical boxes, so that no box remains empty?

Question

How to find the number of ways in which $7$ different balls can be distributed into $4$ identical boxes so that no box remains empty?

In this question, I started by finding the number of ways of selecting any $4$ balls and putting them in the identical boxes in one way, and then the remaining balls could be placed in $3^4$ ways. Can you please help me solving this?

Answer 1

First assume that the boxes are distinct. Then the number of ways of distributing 7 distinct balls into these boxes so that none is empty is, by Principle of Inclusion Exclusion, $$4^7 - \binom{4}{1}3^7 + \binom{4}{2}2^7 - \binom{4}{3} 1^7 = 8400$$ Now the naming of the boxes can be done in $4! = 24$ ways, the required number is $\dfrac{8400}{24} = 350$.

In fact if we want to distribute $n$ distinct objects into $k$ identical boxes so that no box is empty, the number of ways is given by the Stirling number $S(n,k)$ and $$S(n,k) = \frac{1}{k!}\sum_{i=0}^{k-1} \binom{k}{i}(k-i)^n$$

Answer 2

You can go $4111, 3211\text {or }2221$, in terms of partitions of $7$... The boxes are identical so the order doesn't matter. ..

$4111$: ${7 \choose 4}=35 $

$3211$: ${7 \choose 3}{4 \choose 2}=35×6=210$

$2221$: ${7\choose 2}{5\choose 2}{3\choose 2}=21×10×3=630$

Divide $630$ by $3! $ to get 105...

Adding up $105+210+35=350$

Answer 3

Brilliant can be a helpful resource:

A Stirling number of the second kind, denoted as $S(n,r)$ or $\left\{n \atop r\right\}$ is the number of ways a set of $n$ elements can be partitioned into $r$ non-empty sets. In this case, you can use the power of the recurrence relation, which allows one to calculate any value of $S(n,r)$ from other values of $S(n,r)$.

So, here is a list of $S(n,r)$ for $n \leq 7$:

\begin{array}{c|lcr} \small{n} \ ^{\large{r}} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline 0 & 1 & & & & & & &\\ 1 & 0 & 1 & & & & & \\ 2 & 0 & 1 & 1 & & & & \\ 3 & 0 & 1 & 3& 1& & & &\\ 4 & 0 & 1 & 7 & 6& 1 & &\\ 5 & 0 & 1 & 15 & 25& 10 & 1& & \\ 6 & 0 & 1 & 31 & 90& 65 & 15 & 1& & \\ 7 & 0 & 1 & 63 & 301 & \color{red}{350} & 140 & 21& 1 & \\ \end{array}

Note that $S(7,4)=\boxed{350}$.