Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $4$ different types of balls, and $5$ bins. The bins are labeled $A,B,C,D,E$. Each bin only holds one ball. We are to put the balls into each bin such that every type of balls is put into at least one bin.

Repetition is allowed, and you have an infinite supply of each type of balls. Condition: the balls in $A$ and $B$ must be of different type. How many different ways are there to do this?

Attempt

After filling $A$ and $B$, there are only $2$ types of balls left but $3$ bins. So the last bin can hold any type of ball. There are $4$ ways to fill $A$, $3$ to fill $B$, $2$ to fill $C$ and $1$ way to fill $D$. Finally, there are $4$ ways to fill $E$, the last bin.

So, in total, there are $4(3)(2)(1)(4) = 96$ ways to do this.

Questions

  1. Is my reasoning correct?

  2. Is there a more systematic way to tackle similar questions about permutations with repetition and conditions? Or is my way the most systematic?

share|improve this question
    
The balls are distinguishable? –  leonbloy Oct 4 '12 at 18:45
    
@leonbloy - Balls of the same type are indistinguishable from each other if that is what you are asking. –  Legendre Oct 4 '12 at 19:00
add comment

2 Answers

up vote 2 down vote accepted

1: It's indeed wrong, i'll answer your second question at once.

A more general way to solve this kind of problem, is by first not minding the condition: What is the number of permutations if the balls in $A$ and $B$ do not have to be of a different type?

There is only one type that will occur twice. That gives a factor $4$. The two bins that have the same type can be chosen on $\binom{5}{2}=10$ ways. There are $3$ types left for the other $3$ bins, the permutation can be done on $3!=6$ ways. Thus, not minding the condition, the number of ways is $4\cdot10\cdot6=240$.

Now we substract the number of ways where $A$ and $B$ have the same type.

There are $4$ types, that gives a factor $4$. The $3$ other bins can be given balls on $3!=6$ ways.

Thus, the final answer is $240-4*6=216$.

This is a long solution, but it is the general way to solve such problems: Count all possible permutations and substract those that do not satisfy the condition.

share|improve this answer
    
+1. Nice explanation. Thanks! –  Legendre Oct 6 '12 at 11:59
add comment

Assuming the balls are not distinguishable:

Your approach does not look right to me. I don't understand why you assume you have 5 possible values for the last bin (and 2-1 for the previous bins).

My approach: If we have 5 bins and 4 types of balls, then one and only one type will be assigned to two bins. For this, there are ${5 \choose 2} -1 =9 $ pairs of bins (the pair AB is prohibited) and $4$ types of balls to choose from. Afterwards, we have 4-1=3 balls of different types to place in the free bins: that gives $3!$ possible ways.

Hence, there are $9 \times 4 \times 3 ! = 216$ ways

Another approach:

There are $4 \times 3 = 12$ ways of filling the bins AB. Now, we have two possibilities: the repeated ball is one of that pair, or not. In the first case, we have $2 \times 3$ alternatives (which A or B? which remaining bin?) and then we are left with two balls to put in two bins: $2$ ways. In the second case we must select one ball from the remaining balls, and put it in one of the 3 free bins ($2 \times 3$ alternatives). So the total number is $4 \times 3 \times ( 2 \times 3 \times 2 + 2 \times 3) = 216$

share|improve this answer
    
+1. Thanks for the help! –  Legendre Oct 6 '12 at 11:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.