wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Little help needed, combinatorics quesion.
        
(Message started by: Henry_Korol on Feb 21^st, 2006, 2:55pm)

Title: Little help needed, combinatorics quesion.
Post by Henry_Korol on Feb 21^st, 2006, 2:55pm

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.

Title: Re: Little help needed, combinatorics quesion.
Post by towr on Feb 21^st, 2006, 3:28pm

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

Title: Re: Little help needed, combinatorics quesion.
Post by Icarus on Feb 21^st, 2006, 4:33pm

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.

Title: Re: Little help needed, combinatorics quesion.
Post by Henry_Korol on Feb 22^nd, 2006, 4:03am

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.

Title: Re: Little help needed, combinatorics quesion.
Post by towr on Feb 22^nd, 2006, 4:46am

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_easy;action=display;num=1136663270

I'm not sure how much help it'll be though :P Despite it being in the easy section we managed to confuse ourselves.

Title: Re: Little help needed, combinatorics quesion.
Post by THUDandBLUNDER on Feb 22^nd, 2006, 10:47am

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.

Title: Re: Little help needed, combinatorics quesion.
Post by SWF on Feb 22^nd, 2006, 5:46pm

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.

Title: Re: Little help needed, combinatorics quesion.
Post by Henry_Korol on Feb 24^th, 2006, 5:12am

Thanks for the awesome replies guys, and very interesting approach SWF. Have done the exam today, woohooo :D

Thanks to everyone.