2
$\begingroup$

7 balls with different colors, there are 4 identical boxes. the box can be empty. how many ways to distribute the balls?

what kind of counting problem is this? how do we count it?

$\endgroup$
3
  • $\begingroup$ Do you have to use every ball? Also do you have any thoughts/ work on the problem? $\endgroup$ Mar 26 '17 at 6:15
  • $\begingroup$ of course you have to use every ball. If you don't use the all the balls, you basically put 7 different balls into 5 boxes. $\endgroup$
    – Di Wang
    Mar 26 '17 at 6:19
  • $\begingroup$ I only have the answer: S(7,4)+ S(7,3)+ S(7,2)+S(7,1), S stands for stirling number. $\endgroup$
    – Di Wang
    Mar 26 '17 at 6:21
1
$\begingroup$

We have $7$ objects (let each be elements of a set) and we want to partition these objects into $4$ subsets. We can have $1$ nonempty subset (and the other $3$ consequently empty), $2$ nonempty subsets (and the rest empty), $3$ nonempty subsets (and the rest empty), or $4$ nonempty subsets. We can't have $0$ nonempty subsets because that would mean we have no balls in all of the boxes.

The striling number of the second kind $S(n,k)$ counts the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. So the answer is as you claim,

$$S(7,1)+S(7,2)+S(7,3)+S(7,4)$$

$\endgroup$
1
$\begingroup$

From set A (the m balls) to set B (the n boxes), the number of onto functions is $n!S(m,n)$. If the boxes are identical, the order does not matter anymore. Therefore, there are $n!S(m,n)/n! = S(m,n) $ ways to distribute the 7 balls.

We can use, 4 boxes, 3 boxes, 2 boxes or 1 box.

$S(7,4)+S(7,3)+S(7,2)+S(7,1)$

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