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
Math Forum Home || Math Library || Quick Reference || Math Forum Search