Thread: Permutations quetion , slight doubt

1. Permutations quetion , slight doubt

Hi

THe question is
THe number of ways in whcih 4 distinct balls can be put in 4boxes labelled a,b,c,d so that exactly one box remains empty:

So what I have done till now is as follows:
1. Case 1: Box "a" remains empty. So we have 4balls which need to go in 3boxes so that every box should have atleast 1ball.

So, we select 3balls from 4 to fill in one ball in each box. (4c3 * 3! ) and the remaining ball can go in any of the b,c,d boxes.

So , total cases where Box "a" is remaining empty are 4C3 * 3! * 3 = 72

BY similarity , there will be four cases in total. So the answer is 4 * 4C3 * 3! * 3 = 288 .

But the correct answer is 144. That means I am doubling up some number which I am unable to figure out.

2. When you add the fourth ball to one of the three boxes you've added ball 1 to ball 2, for example, which is the same result as adding ball 2 to the combination when the box contained ball 1. Therefore all the combinations have been counted twice, so you need to halve the number.

Someone will no doubt correct me if I'm wrong.

3. Originally Posted by champrock
The question is
The number of ways in which 4 distinct balls can be put in 4boxes labeled a,b,c,d so that exactly one box remains empty:
ANSWER: Four times the number of surjections from a set of four to a set of three.
$\displaystyle Surj(4,3)=36$.

4. wat is a "Surjection" this seems a really scientific way to do it.

Searched on net but could not find its application as u have used in the above case.

5. Originally Posted by champrock
what is a "Surjection" this seems a really scientific way to do it. Searched on net but could not find its application as u have used in the above case.
I find it hard to understand what you mean by “Searched on net but could not find its application”.
I found this nice page on one try.
A surjection is simply an onto function.
If you are serious about counting problems the you need to know about mappings.