Author |
Topic: Little help needed, combinatorics quesion. (Read 468 times) |
|
Henry_Korol
Newbie
Gender: 
Posts: 3
|
 |
Little help needed, combinatorics quesion.
« on: Feb 21st, 2006, 2:55pm » |
 Quote  Modify
|
Hello everyone, I'm currently preparing to my exam in discrete maths. I came across the following quesion:
In how many ways can you put 50 different balls in to 3 boxes, such that none of them will be empty.
The basic solution goes by the principle of exclusion and inclusion, from the number of all ways to put different balls into 3 boxes ( 3^50 ) i substract the size of the set that has eather one box empty ( 3*2^50 - 3) so the answer is: 3^50 - 3*2^5 + 3, which is correct ( checked with the answers ).
But I thought about a different way to approach this question: first we put one ball in each box making sure none of them is empty, then we put the rest of the balls as we like:
the number of ways to choose 3 balls to put to the box is ( 50 choose 3 ) now I multiply this by 3! which is the number of orders I can settle these 3 balls in a row.
Now I sum this to the number of ways to settle the rest 47 balls in 3 boxes which is 3^47, so the second answer would be: (50 choose 3)*3! + 3^47, which is incorrect. I've spend a couple of good hours trying to figure out what is wrong in this approach, but it seems logical to me. Is there something I'm not thinking about?
Thanks in advance.
|
| « Last Edit: Feb 21st, 2006, 3:03pm by Henry_Korol » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Little help needed, combinatorics quesion.
« Reply #1 on: Feb 21st, 2006, 3:28pm » |
Quote Modify
|
It's too tired for my brain to work properly. But a similar question has been asked before, if you can find that thread it might help.
Or maybe I'll remember this tomorrow and give a more usefull answer:p
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Little help needed, combinatorics quesion.
« Reply #2 on: Feb 21st, 2006, 4:33pm » |
Quote Modify
|
Two problems.
First, by the way you are counting, it would C(50,3) * 3! * 3^47, not + 3^47. For each way of choosing 3 balls, and putting one each in a box, there are 3^47 ways of distributing the other 47 balls, so you need to multiply, not add.
Second, and more importantly, you are counting many cases multiple times. For example, suppose there were only 5 balls. You could choose balls 1, 2, 3 to place in boxes A, B, C respectively, as your initial 3 choices. Then you have 9 possible ways of distributing balls 4 and 5. One case will have 4 in A and 5 in B. Later, you count the situation where 3, 4, and 5 are your first 3 balls, with 4 in A, 5 in B, and 3 in C. One of the 9 distributions of the remaining two balls 1 and 2 is 1 in A, 2 in B. So you have counted this case twice now: 1,4 in A; 2,5 in B; 3 in C.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Henry_Korol
Newbie
Gender:
Posts: 3
|
|
Re: Little help needed, combinatorics quesion.
« Reply #3 on: Feb 22nd, 2006, 4:03am » |
Quote Modify
|
Thanks for the fast reply Icarus. I think I got it, though is there any way to count how many additional times I count the case, and divide by that? ie, is there any way to improve this approach, or inclusion/exclusion is the best way to go?
Thanks again.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Little help needed, combinatorics quesion.
« Reply #4 on: Feb 22nd, 2006, 4:46am » |
Quote Modify
|
Here's the thread about the general case, m balls, n bags(boxes) and each bag needs at least k balls in it.
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_eas y;action=display;num=1136663270
I'm not sure how much help it'll be though  Despite it being in the easy section we managed to confuse ourselves.
|
| « Last Edit: Feb 22nd, 2006, 4:59am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Little help needed, combinatorics quesion.
« Reply #5 on: Feb 22nd, 2006, 10:47am » |
Quote Modify
|
Quote:| In how many ways can you put 50 different balls in to 3 boxes, such that none of them will be empty. |
|
Check out Stirling Numbers.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Little help needed, combinatorics quesion.
« Reply #6 on: Feb 22nd, 2006, 5:46pm » |
Quote Modify
|
Think of the balls as being numbered from 1 to 50, and the boxes are arranged in a line such that the first box has ball number 1, the lowest numbered ball in the second box is N, the lowest numbered ball in the third box is M, and N<M. N can therefore be anything from 2 to 49, and M anything from N+1 to 50.
Given an N and M, balls number 1 to N-1 will be in the first box. The M-N-1 balls numbered N+1 through M-1 are in either the first or 2nd box in any of 2^(M-N-1) possible ways. The remaining (50-M) balls with numbers greater than M may be in any box: 3^(50-M) possibilities. Therefore, there are 2^(M-N-1) * 3^(50-M) combinations for a given N and M.
To get the total, do a double sum over the possible values of N and M:
sum(N=2 to 49) sum(M=N+1 to 50) 2^(M-N-1) * 3^(50-M)
Since the boxes can be in any order, multiply that by 3! to get the total. Evaluating that sum is not tough if you use the formula for sum of a geometric series:
sum(k=A to B) c^k = (c^(B+1) - c^A) / (c - 1)
Doing that gives 3^50 - 3*2^50 +3 (there is a typo in the solution given in the original post). I'd say the first method is easier, but this is one way of doing it without subtracting exceptions.
|
|
IP Logged |
|
|
|
Henry_Korol
Newbie
Gender:
Posts: 3
|
|
Re: Little help needed, combinatorics quesion.
« Reply #7 on: Feb 24th, 2006, 5:12am » |
Quote Modify
|
Thanks for the awesome replies guys, and very interesting approach SWF. Have done the exam today, woohooo 
Thanks to everyone.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print