M Balls in N Boxes

Date: 01/24/2002 at 10:07:31
From: Tanya
Subject: Probability

Suppose we put m balls into n boxes. What is the expected number of 
empty boxes?

Date: 01/24/2002 at 19:15:11
From: Doctor Anthony
Subject: Re: Probability

To avoid overcomplicated expressions with n and m I will consider 
placing 10 numbered balls at random into 6 boxes.

The number of ways we could place 10 numbered balls into 6 boxes with 
no restrictions is given by 6^10

We now select 1 box to leave empty (this can be done in C(6,1) = 6 
ways) and then distribute the 10 balls into 5 boxes such that no box 
is empty.

This can be done in T(10,5) ways where 
         
           5
T(10,5) = SUM[(-1)^k.C(5,k).(5-k)^10]   
          k=0


 = C(5,0) x 5^10 - C(5,1) x 4^10 + C(5,2) x 3^10 - C(5,3) x 2^10

   + C(5,4) x 1^10

 = 5^10 - 5 x 4^10 + 10 x 3^10 - 10 x 2^10 + 5 

 = 5103000

Next we remove 2 boxes (this can be done in C(6,2) = 15 ways) and 
distribute the balls into the other 4 boxes.

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

and similarly

T(10,3) = 3^10 - 3.(2^10) + 3    =  55980

T(10,2) = 2^10 - 2               = 1022

T(10,1) = 1^10                   = 1

The expected number of empty boxes is

  [1/6^10].[1 x 6 x 5103000 + 2 x 15 x 818520 + 3 x 20 x 55980
             + 4 x 15 x 1022 + 5 x 6 x 1]

  = [1/6^10].[58593750]

  =  0.96903

So we could expect just about one box to be empty after distributing 
the 10 balls into 6 boxes.  A general formula for m balls and n boxes 
would be very complicated, so it is best to treat any problem by the 
method described above.  

If you wish to see the derivation of the formula for T(10,5) and other 
such terms you should write in again.

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