0
$\begingroup$

4 balls with different colors, there are 3 identical boxes. the box can be empty. of course, all balls must be used. how many ways to distribute the balls?
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 my answer is, S(4,1)+S(4,2)+S(4,3) but I don't know how to get numeric answer from here like how do I find what S(4,1) is?

$\endgroup$
1
  • 1
    $\begingroup$ S(4,1) would seem to be trivial: 1! There is only 1 way to keep all 4 balls in the same 1 group. $\endgroup$
    – Bram28
    Dec 3 '20 at 18:44
1
$\begingroup$

You can put all balls in $1$ box in $1$ way. Then you can put $1$ ball in a box and the other $3$ balls in a second box in $4$ ways, or pair the $4$ balls off in two boxes in $3$ ways. Finally you can make ${4\choose2}=6$ pairs of balls for one box and put the remaining balls in two more boxes. In all you have $1+4+3+6=14$ ways, corresponding with $S(4,1)+S(4,2)+S(4,3)=14$.

$\endgroup$
0
$\begingroup$

There are closed formulas for those Stirling numbers, or you can just consult a table, e.g. just go here: https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

But, this problem isn't so hard that you couldn't just brute this yourself:

Label the balls $1$ through $4$, and put the first ball in a group: $1$

Now we can add the second ball to that one: $12$, or not: $1,2$

To each of those possibilities, we find the different ways to add the third ball:

That is, $12$ leads to $123$, or $12,3$, and $1,2$ leads to $13,2$, or $1,23$, or $1,2,3$. So note that this also tells us that if you had $3$ different balls, then there are $5$ ways to put them in $3$ boxes, possibly empty.

Finally, we add the fourth ball. Note that n the case where we still have only one group, there are $2$ possibilities, whereas when you have two or three groups, you have $3$ possibilities each. This gives us $14$ possibilities. Here they are explicitly:

$1234$

$123,4$

$124,3$

$12,34$

$12,3,4$

$134,2$

$13,24$

$13,2,4$

$14,23$

$1,234$

$1,23,4$

$14,2,3$

$1,24,3$

$1,2,34$

$\endgroup$
2
  • $\begingroup$ @asker minor breach of protocol. sometimes the person responding will extend you the courtesy and also tackle the second question. However, the standard mathSE protocol is one question per query. This suggests that it would be more appropriate to create a 2nd query for your 2nd question. Also, just as before, mathSE reviewers will (again) be looking for you to show work as part of the query. $\endgroup$ Dec 3 '20 at 19:11
  • $\begingroup$ finally makes sense, a very clear explaination. thank you. $\endgroup$
    – asker
    Dec 3 '20 at 19:40

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.