Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/ 
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/