3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

How many ways can five items be arranged in a row if two particular items may not be adjacent?

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!$.

How many ways can five of nine items be arranged if two items can't be next to each other.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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