# 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. – Mauve Jan 9 '18 at 7:24
• en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind – Mauve Jan 9 '18 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. – Ross Millikan Jan 9 '18 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$