
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
February 17th, 2008, 11:14 AM  #1 
Newbie Joined: Feb 2008 Posts: 3 Thanks: 0  7 balls into 5 boxes, expected number of empty boxes
Suppose we put 7 balls randomly into 5 boxes. What is the expected number of empty boxes? I can't seem to wrap my head around this one no matter how I try to connect it to Combination/Multinomial/BellNumber/StirlingNumber. http://www.mymathforum.com/viewtopic.php?t=955 was the only thread I could find that closely resembled my problem, just in his problem, he was only counting all the exhaustive groupings of N objects, which was found through using Bell Numbers. In mine, I have to somehow keep track of the number of empty boxes in these exhaustive groupings of the 7 balls. If anyone has any insight on this, it would be greatly appreciated! 
February 17th, 2008, 12:17 PM  #2 
Member Joined: Jan 2008 Posts: 32 Thanks: 0 
try ignoring boxes. ignore 1 box and partition, multiply this answer by C(5,1). ignore 2 boxes and partition, multiply this answer by C(5,2). ignore 3 boxes and partition, multiply this answer by C(5,3). ignore 4 boxes and partition (oh, oh, i know this one  it's 5!). then, add the answers. 
February 17th, 2008, 12:36 PM  #3  
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Quote:
Expected number of empty boxes is between 1 and 5... Instead, do what he says with the ignoring... Multiply by the number of boxes you ignored, and divide that sum by the total number of ways to partition the box.  
February 17th, 2008, 12:50 PM  #4 
Member Joined: Jan 2008 Posts: 32 Thanks: 0 
i misused 'partition' didn't i. i was thinking if you ignore 1 box and find all the combinations of 7 balls into 4 boxes (without leaving empty boxes..this is what i forgot to mention), then multiply that by C(5,1) = 5 (the empty box gets to be each of the 5 boxes), that would be the number of different ways to put 7 balls into 5 boxes with one empty box. repeat for 2 empty, 3 empty 4 empty, and add all the answers. *edit* can all five be empty? add 1 more? 
February 17th, 2008, 02:00 PM  #5 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 
Yeah, partition is the number of ways to split n things into k parts Anyway, since we're figuring out how many are empty, rather than which are empty, we can pretend the 5 boxes are all the same, so we are partitioning a 7element set into 5 parts, or into 4 parts, or into 3 parts, etc: there are ∑Part(7,k), k=[1,5]. Since we need to multiply by the number of empty boxes in each case E=(∑(5k)*Part(7,k))/(∑Part(7,k)), k=[1,5]. (It's 5k, because 5 boxes means 0 empty) You should be able to figure this out (granted, it'll take some computation). The partitions of a set are related to Bell's number (which is the sum of all partitions of a set). If you need any more explanation, let me know.[/url] Edit: if all 5 are empty, there are 0 balls, so they can't all be empty. 
February 18th, 2008, 05:57 AM  #6 
Member Joined: Jan 2008 Posts: 32 Thanks: 0 
yea, i'm sayin my way does what he's trying to do, assuming i correctly understand what he is trying to do, which is  given all the possible combinations of 7 balls into 5 boxes how many empty boxes are there. i think of the question like this  picture every combination laid out beside each other (so the first five boxes would be the first combination, the second five boxes would be the second combination, etc) and what we want to do is look at all these combination and count all the empty boxes. if that's not the correct understanding of the question then the method i suggested is rather wrong, but other than that i think it's correct. 
February 18th, 2008, 07:58 AM  #7 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 
He was asking for the expected number of empty boxes, given any arbitrary configuration. I think this is what's throwing you off. E is the sum of the number of ways to get a certain event, times the "value" of that event, all over the total possiblities In this case, the value is the number of empty boxes. So E(epmty box)=∑ (#of ways to get n empty boxes)*n)/(Ways to put 7 balls into at most 5 boxes) You could assume each box is independent, and count that way (read: you aren't doing it wrong), but it makes for a lot more counting. Since all you need to count is the total number of empty boxes, you can assume each box is the same, proceed from there. You'll get the same answer. Granted, it's harder to count partitions than combinations, but you're doing a little bit of hard counting, vs a lot of easy counting. However, I just realized, if the balls are not identical, you'll have to count it differently. 
February 18th, 2008, 11:20 AM  #8 
Member Joined: Jan 2008 Posts: 32 Thanks: 0 
ooooh ok i gotcha, so it's like the mean or average number of empty boxes, given all possible combinations of 7 balls into 5 boxes. so i could take what i would get as an answer and divide that by the total number of possible combinations of 7 balls into 5 boxes and get the same answer as your way? i think this might come in handy proving/disproving a Clique algorithm i've been working on...i'm excited! 
February 19th, 2008, 09:40 AM  #9 
Newbie Joined: Feb 2008 Posts: 3 Thanks: 0 
thanks cknapp, it definitely took me a whole page to write out the whole problem, but definitely thanks for the kick start. It's frustrating when you hit a brick wall. I ended up using the stirling equation for the part() function you were using, and it seems to make sense to me looking at my final answer, so all I can do is hope I did it right. The original wording doesn't make it too clear about distinct balls or whatever, but I think the stirling equation actually keeps that in mind. Anyhow, my final answer came out to be around 1.33 expected amount of empty boxes, though the answer in the back of the book was 1.05, the prof said it was only an approximation, so I could probably try to look into approximation methods, but I can't be arsed 

Tags 
balls, boxes, empty, expected, number 
Search tags for this page 
suppose that 10 balls are put into 5 boxes,Combination of 7balls identical and 4boxes,empty box with partition in mathematics,10 balls are put into 5 boxes solution,ten balls are put into ten boxes independently.find the expected no. of empty boxes,expected number of balls empty
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Exercise with boxes and balls.  evinda  Advanced Statistics  3  October 21st, 2013 03:10 AM 
How do you calculate how many boxes are required?  woonipad  Applied Math  3  June 30th, 2012 10:43 PM 
Storage of Boxes in an (odd shaped) room  mathbob  Algebra  1  December 7th, 2010 04:11 PM 
Boxes and Balls  Statistics Problem  bondboy007  Probability and Statistics  1  November 4th, 2008 06:21 AM 
Boxes of Candy  symmetry  Algebra  4  June 8th, 2007 06:30 PM 