 My Math Forum 7 balls into 5 boxes, expected number of empty boxes

 Algebra Pre-Algebra and Basic Algebra Math Forum

 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:
 Originally Posted by pinion 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. That'll give you a number that's really, really high... And where does the binomial coefficient come into this?

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 7-element 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=(∑(5-k)*Part(7,k))/(∑Part(7,k)), k=[1,5]. (It's 5-k, 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 ,

,

,

,

,

expected number of balls empty

Click on a term to search for related topics.
 Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post evinda Advanced Statistics 3 October 21st, 2013 03:10 AM woonipad Applied Math 3 June 30th, 2012 10:43 PM mathbob Algebra 1 December 7th, 2010 04:11 PM bondboy007 Probability and Statistics 1 November 4th, 2008 06:21 AM symmetry Algebra 4 June 8th, 2007 06:30 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      