Having trouble with a question in textbook on permutations: “How many ways can 5 items be arranged out of 9, if two items can’t be next to each other.”
A question like this is easy when you are ordering items and not leaving any out, like if it was 5 items out of 5 items the answer would be $_5P_5 -~ _{(2\times 4)}P_4$.
I was trying to work it out by thinking of all the possible ways of having 5 items but two not together like:
- neither item $A$ or item $B$: $_7P_5$ (discard both, leaving 7)
- just item $A$: $_8P_5$ (discarding $B$)
- just item $B$: $_8P_5$
But from there I’m stumped because I don’t know how to calculate the scenario where both items are in the arrangement of 5 but aren’t next to each other.
Can anyone help out?
Best Answer
There are $5!$ ways of arranging items in a line.
From these arrangements, we must subtract those in which two particular items are adjacent. Place those two items in a box. That gives us four objects to arrange, the box and the other three objects. The objects can be arranged in a row in $4!$ ways. The two objects in the box can be arranged in $2!$ ways. Hence, the number of inadmissible arrangements is $4!2!$.
Therefore, the number of admissible arrangements is $5! - 4!2!$.
Your approach is sound. Your counts for the case neither item $A$ nor item $B$ is correct. However, your count for only item $A$ is incorrect.
If only item $A$ is used, then item $B$ is not used, so we must select four of the other $9 - 2 = 7$ objects in addition to item $A$. The five selected objects can be arranged in $5!$ ways. Hence, the number of arrangements containing only item $A$ is actually $$\binom{1}{1}\binom{1}{0}\binom{7}{4}5!$$ By symmetry, the same number of arrangements contain only item $B$.
The two cases in which exactly one item is present can be handled simultaneously. Choose one of $A$ and $B$, four of the remaining seven objects, and arrange the selected objects in $5!$ ways, which gives $$\binom{2}{1}\binom{7}{4}5!$$
For the case in which both item $A$ and item $B$ are selected, we must select three of the other seven objects to be in the arrangement. Once those five objects have been selected, they can be arranged in $5! - 4!2!$ ways without placing items $A$ and $B$ next to each other. Hence, there are $$\binom{2}{2}\binom{7}{3}[5! - 4!2!]$$ ways to select five objects including $A$ and $B$ and arrange them so that $A$ and $B$ are not adjacent.
Adding the three cases gives $$\binom{2}{0}\binom{7}{5}5! + \binom{2}{1}\binom{7}{4}5! + \binom{2}{2}\binom{7}{3}[5! - 4!2!]$$ where the first term is the number of admissible arrangements in which neither $A$ nor $B$ is selected, the second term is the number of admissible arrangements in which exactly one of $A$ or $B$ is selected, and the third term is the number of admissible arrangements in which both $A$ and $B$ are selected.