Balls into Urns - 2

Probability Level 2

How many ways are there to place $5$ differently colored balls into $5$ identical urns if the urns can be empty?

All $5$ balls have to be used.
An urn could contain multiple balls.

The answer is 52.

1 solution

Andy Hayes
May 10, 2016

Relevant wiki: Distinct Objects into Identical Bins

The problem can be modeled as "distinct objects into any number of identical bins." The answer will be the Bell number , $B_5$ .

This number can be found with: $B_5=\sum_{k=1}^{5}{S(5,k)}$ Where $S(5,k)$ is the number of distributions of 5 distinct objects into k identical non-empty bins.

$S(5,1)=1$ , $S(5,2)=15$ , $S(5,3)=25$ , $S(5,4)=10$ , and $S(5,5)=1$

(These values can be found using the recurrence relation identity for Stirling numbers of the second kind )

Thus, $B_5=1+15+25+10+1=\boxed{52}$

"The Bell numbers count the number of ways n distinct objects can be distributed into up to n identical NON -EMPTY BINS". But here the question says that the bins can be empty. Should the Bell number be used here? Pls correct me if I am wrong.

rajdeep das - 4 years, 9 months ago

Yes, Bell numbers model the number of ways $n$ distinct objects can be distributed into up to $n$ identical non-empty bins.

The key phrase is "up to." This means that the number of urns could be 1, 2, 3, 4, or 5. In this problem, urns can be empty, so there can be 4, 3, 2, 1, or 0 empty urns (this corresponds to to having 1, 2, 3, 4, or 5 non-empty urns, respectively).

I recommend changing the wording of this problem to use the "up to 5 urns" language. It will clear up the language discrepancy between this problem and the content it is based on.

Andy Hayes - 4 years, 9 months ago

Ok I got it. (+1) :)

rajdeep das - 4 years, 9 months ago

@Andy Hayes

rajdeep das - 4 years, 9 months ago

Balls into Urns - 2

The answer is 52.

1 solution

0 pending reports