The Chocolate Box Problem

Date: 11/11/2002 at 05:13:47
From: Brian Mitchell
Subject: The chocolate box problem

Given twelve types of chocolates, what is the probability that a box 
of fifty (randomly selected from an infinite supply with equal 
probability) does not contain one or more of the types?

I can see that the probability of any given type being missing is 
(11/12)^50. I reason that the probability I'm trying to find is equal 
to 

1-(the number of unique groups containing all types / total number of 
unique groups)

It is the numerator that gives the trouble...

Ah, but I was wrong... The denominator gives equal difficulty :) I see 
now that the question may be posed: How many ways of adding k positive 
numbers to equal n? (And what if zero is not allowed?)

Still can't do it though.

Thanks,
Brian

Date: 11/11/2002 at 18:41:08
From: Doctor Anthony
Subject: Re: The chocolate box problem

We start by first finding an expression for T(n,m) where this 
represents the number of ways of placing n distinguishable objects at 
random into m distinguishable boxes so that no box is empty.  

So we can model our problem as placing 50 distinguishable balls at 
random into 12 boxes and find the probability that no box is empty.  
Subtracting this probability from 1 will give the probability that one 
or more boxes are empty - or one or more types of chocolate are 
missing.

Consider a problem of finding the number of arrangements of 10 letters 
that can be made from unlimited supplies of 4 letters A, B, C, and D 
such that each letter appears at least once.

We require the coefficient of x^10/10! in the expansion of

 = [x + x^2/2! + x^3/3! + ..]^4  =  [e^x - 1]^4

The -1 ensures that we MUST have an A, B, C and D somewhere in
each arrangement.

 [e^x-1]^4 = e^(4x) - 4e^(3x) + 6e^(2x) - 4e^x + 1

from which we pick out term in x^10.

 = (4x)^10/10! - 4.(3x)^10/10! + 6.(2x)^10/10! - 4.x^10/10!

 = [4^10 - 4.(3^10) + 6.(2^10) - 4].(x^10/10!)

and the term in square brackets is the coefficient of x^10/10!

So  T(10,4) = [4^10 - 4.(3^10) + 6.(2^10) - 4]  =  818520

which corresponds to the formula

           m
 T(n,m) = SUM[(-1)^k.C(m,k).(m-k)^n]   with n=10 and m=4
          k=0

In the problem with the chocolates we have n=50 and m=12 so we require

T(50,12) = 12^50 -12(11^50) +66(10^50) -220(9^50) +495(8^50)
          - 792(7^50) + 924(6^50) - 792(5^50) + 495(4^50)
          - 220(3^50) + 66(2^50) - 12(1^50)

         = 7.756621135 x 10^53

The total number of ways of distributing the 50 balls is 12^50, so 

                                7.756621135 x 10^53
  Probability no box is empty = -------------------
                                      12^50

                              = 0.852335

Probability that one or more box is empty = 1 - 0.852335

                                          = 0.147665

So the probability that some types of chocolate are missing = 0.1477

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/11/2002 at 22:08:42
From: Brian Mitchell
Subject: Thank you (The chocolate box problem)

Wow, cool!  Thanks for your speedy reply. Now I know what I'm looking 
for, I found quite a few other answers by you in the archives using 
the T(n,m) function. Is there a common name for such problems?  
Thanks, Brian.

Date: 11/12/2002 at 11:11:39
From: Doctor Anthony
Subject: Re: Thank you (The chocolate box problem)

These questions come under the general title of 'combinatorics'.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/