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

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?

• 20688 seems awfully high: It's greater than the number of ways to put 7 labelled balls in 4 labelled boxes with no restrictions. Jan 9, 2018 at 7:24
• en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Jan 9, 2018 at 7:26
• The approach of putting any four balls in different boxes and then distributing the remaining three overcounts. You could put $1,2,3,4$ in four different boxes, then put $5,6,7$ with the $1$. You could also put $2,3,4,5$ in four different boxes and put $1,6,7$ with the $5$. Your approach counts these separately, but they result in the same configuration, as do two more. Jan 9, 2018 at 17:30

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$$

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$

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}$$.