UVa 10648

From Algorithmist
Jump to navigation Jump to search

10648 - Chocolate Box[edit]

Summary[edit]

Given distinguishable boxes and chocolates to put in those boxes with equal probability, what is the probability that at least one box is empty? This set of numbers can be calculated exactly by the Stirling Number of the Second Kind.

Explanation[edit]

The Stirling Number of the Second Kind (using Knuth's notation ) counts the number of ways to partition a set of elements into non-empty sets. How does this solve our problem?

For a given , each of the occur with equal probability. calculates the number of sets, so the boxes would not be distinctive. e.g.: = , but since the boxes are distinctive, we would have have to multiply it by to get all the ordering.

Now there are two (equivalent) ways to go about:

The first is calculating - the number of ways to put distinctive chocolates into boxes - or having no empty boxes. Since the boxes are distinct, multiply it by to get the total number of ways we can have no empty boxes. The distribution is equal, and every way happens with an equal probability, thus we can divide it by the total number of ways (which is simply ) to get the probability of having no empty boxes. To get the inverse of this, we subtract that probability from 1. (The sets are totally disjoint, afterall.)

The second is calculating - the number of ways to put distinctive chocolates into boxes. This will count the number of ways there will be empty boxes, respectively. For each way, we have to account for the fact that all the boxes are distinctive, so we multiply it by , but to factor out the double counting we put on all the empty boxes (since it doesn't matter), we have to divide it by - the number of empty boxes. This means we are actually calculate . As with the first method, we can then divide it by the total number of ways (which is simply ) to get the probability.

Input[edit]

50 12
50 12
100 3
100 12
32 7
-1

Output[edit]

Case 1: 0.1476651
Case 2: 0.1476651
Case 3: 0.0000000
Case 4: 0.0019960
Case 5: 0.0500009