I have the following homework:
Assume we have $7$ apples, $4$ oranges, and $1$ banana. The apples and oranges are identical separately. Please count the number of all permutations for each of the following cases:
(a) put these fruits in a row;
(b) put these fruits in a circle; (orientation matters, i.e., clockwise and counter-clock are different.)
(c) put these fruits in a row where the banana cannot be adjacent to any oranges.
For part a, I think the answer is
$$\frac{12!}{7!4!}=3960$$
For part b, I think the answer is
$$\frac{(12-1)!}{7!4!}=330$$
However, for part c, I don't even know how to approach this. I started by thinking about the situation the banana need to be adjacent to the oranges, after that, I will subtract it from the answer in part a which is the possible permutations. However, I don't know how to do that. Could anyone please help?
Best Answer
Your first two answers are correct.
For the third question, your strategy is sound.
Suppose a banana has an orange to its immediate left. Then the orange-banana pair must begin in one of the first $11$ positions. That leaves seven apples and three oranges to distribute to the remaining $10$ positions, which can be done in $\binom{10}{3}$ ways. Hence, there are $$11\binom{10}{3}$$ arrangements in which a banana has an orange to its immediate left.
By symmetry, there are $$11\binom{10}{3}$$ arrangements in which a banana has an orange to its immediate right.
However, if we subtract these amounts from the total, we will have subtracted each arrangement in which a banana is adjacent to two oranges twice, once when we subtracted arrangements in which there was a banana to its immediate left and once when we subtracted arrangements in which there was a banana to its immediate right. We only want to subtract such arrangements once, so we must add them to the total.
If a banana is adjacent to two oranges, then the orange-banana-orange block must begin in one of the first $10$ positions. That leaves us with seven apples and two oranges to distribute to the remaining nine positions, which can be done in $\binom{9}{2}$ ways. Hence, there are $$10\binom{9}{2}$$ such arrangements.
By the Inclusion-Exclusion Principle, the number of arrangements of seven indistinguishable apples, four indistinguishable oranges, and a banana in a row in which the banana is not adjacent to an orange is $$\binom{12}{7, 4, 1} - 2 \cdot 11\binom{10}{3} + 10\binom{9}{2}$$ where the multinomial coefficient $$\binom{12}{7, 4, 1} = \frac{12!}{7!4!1!}$$