My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Reply
 
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!
frendlyfranz is offline  
 
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.
pinion is offline  
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.
cknapp is offline  
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?
pinion is offline  
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.
cknapp is offline  
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.
pinion is offline  
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.
cknapp is offline  
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!
pinion is offline  
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
frendlyfranz is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
balls, boxes, empty, expected, number



Search tags for this page
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





Copyright © 2019 My Math Forum. All rights reserved.