1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 20688 seems awfully high: It's greater than the number of ways to put 7 labelled balls in 4 labelled boxes with no restrictions. $\endgroup$ – Mauve Jan 9 '18 at 7:24
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind $\endgroup$ – Mauve Jan 9 '18 at 7:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 9 '18 at 17:30
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.