Number of ways to arrange 5 monkeys in a row?

We have 5 monkeys $a,b,c,d,e$ and we are interested in the number of ways to have them stand in a row without $a$ and $b$ being next to each other.

The part that I struggle with most is that I don't fully understand how to solve this when the 5 are different. It's not the same as for example coloring 5 segments either blue or red without any two neighboring segments being red.

This is how I tried to solve this but I'm certain that there's something wrong. I would really appreciate it if you could also critique my approach.

Idea:

Let $f_{k}$ be the number of ways we can have the $5$ monkeys in a row without $a$ and $b$ being next to each other. We try to do this recursively:

case 1 : the last monkey is not $a$ or $b$: then we have $f_{k-1}$ possibilities for the rest of the k-1 monkeys.

case 2 : the last monkey is either $a$ or $b$: Here the second to last has to be one of $\{c,d,e\}$. So we have $3$ possibilities for the second to last spot and $2$ possibilities for the last. A total of $2*3 = 6$ and $f_{k-2}$ for the remaining spots.

The recursive equation I get is: $f_{k} = 6 + f_{k-1} + f_{k-2}$

$f_{1} = 5$

$f_{2} = 10$

$f_{3} = 21$

$f_{4} = 37$

$f_{5} = 64$

I'm not sure about my solution.

Thanks in advance

Solution 1:

Here's how I'd approach this particular problem. I'll solve for $k$ monkeys afterwards.

You have $5!$ ways for the monkeys to be arranged in a line without restriction.

There are $8$ ways that $A$ and $B$ can be positioned next to each other; there are $4$ pairs of adjacent spaces, and either $A$ or $B$ can be on the left.

For each of these cases, there are $3! = 6$ ways to arrange the other three monkeys.

So the answer is $5! - 8 \cdot 3! = 72$ ways.

Now, just apply to $k$ monkeys using the same argument:

$$P(k) = k! - 2(k-1)(k-2)! = k! - 2(k-1)!.$$

(Hat tip to user471297 for the last simplification.)

Solution 2:

Recursive solution (the complementary counting solution is outlined in John's answer):

Let $f(k)$ be the number of ways to arrange $k$ monkeys, including $a$ and $b$ such that these two aren't next to each other.

Case 1: $a$ or $b$ is at the beginning of the line.

Counting this case directly, we first choose the leading monkey in one of $2$ ways. Then we find that the other of these two monkeys is in one of $k-2$ positions (any spot except for the one occupied by the first monkey, and the one immediately behind it). The other $k-2$ monkeys can be in any order, so we get $2 (k-2) (k-2)!$ ways.

Case 2: Neither are at the beginning of the line.

There are a total of $k-2$ choices for the monkey to lead the line; after that, we have the $k-1$ subproblem, so we find $(k-2)f(k-1)$ ways here.

Combining these, we have a total of $f(k) = (k-2)(2(k-2)! + f(k-1))$ good arrangements. Starting with $f(2) = 0$, an inductive argument should show that this matches the closed form answer.

Solution 3:

@John and @platty have both supplied good answers. Here is another approach.

$a$ is at an end of the row: Since $a$ can be at the left or right end of the row, there are two ways to place $a$. For each such choice, there are three ways to place $b$ so that $b$ is not adjacent to $a$. The remaining three monkeys can be arranged in the three remaining positions in $3!$ ways. Hence, there are $$2 \cdot 3 \cdot 3!$$ arrangements in which $a$ is at an end of the row.

$a$ is not at the end of the row: Since there are five positions including the two ends of the row, there are three choices for the position of $a$. Since $b$ cannot be adjacent to $a$, there are two ways to place $b$. The remaining three monkeys can be arranged in the three remaining positions in $3!$ ways. Hence, there are $$3 \cdot 2 \cdot 3!$$ arrangements in which $a$ is not at an end of the row.

Total: Since the two cases are mutually exclusive and exhaustive, the five monkeys can be arranged in $$2 \cdot 3 \cdot 3! + 3 \cdot 2 \cdot 3! = 72$$ ways if $a$ and $b$ are not in adjacent positions.

Solution 4:

I came up with the answer a different, non-recursive, way than some of the answers here (I understand the OP wanted a critique of their approach, but I figured that a different method could still add value). Anyway, my method:

As John said, there are $5!$ ways to arrange the monkeys without restriction. From there I treated monkeys $A$ and $B$ as one monkey and found the number of ways the four monkeys could be arranged: $4!$

Since there are two ways to arrange monkeys $A$ and $B$ together, you have $2 * 4!$ ways $A$ and $B$ could be put together. Subtracting from the original unrestricted $5!$ yields $120 - 2 * 24 = 72$.

Solution 5:

Here is a simple solution :

First arrange 5 monkeys in 5! = 120;

remove all the cases where both a and b sit together.. so to get that tie two monkeys as one item: so you have 4 monkeys now --- how many ways you can arrange 4monkeys: 4! and also A and B sit as AB and BA so finally

we have 2 * 4! ways

so: answer is 5! -2 4! so in general : k! - 2 (k-1)!

Now just go to the previous answers k! - 2 * (k-1)(k-2)! is also actually same as k! - 2* (k-1)!