# Permutation with repetition and condition.

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?

-
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

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.

-
+1. Nice explanation. Thanks! – Legendre Oct 6 '12 at 11:59

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$

-
+1. Thanks for the help! – Legendre Oct 6 '12 at 11:59