Number of ways to arrange 5 monkeys in a row?

Question

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

Answer 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.)

Answer 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.

Answer 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.

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

Answer 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)!

Answer 6

A way to find the result without subtracting one result from the general one:

Arrange the three other monkeys, $c, d, e$ in $3!$ or $6$ distinct ways.

There is a slot for $a$ or for $b$ in front of the first of $c, d, e$ already placed, and after each of $c, d, e$ already placed, for a total of 4 slots, each possible holding one of the two remaining letters, either $a$ or $b$. Adjacent placement of $a$ and $b$ is thus impossible

Select two of these four slots in $4 \times 3$ or $12$ ways. Put $a$ in the first slot selected and $b$ in the second.

Collapse the two empty slots as unneeded, and you're done with $6 \times 12$ or $72$ ways...

Answer 7

For your approach, you should get that placing $2$ monkeys in conformity with the conditions has zero options. So there is something odd going on there. Your base case would probably better be taken from the $2$ obvious possibilities for three monkeys.

---

Using a masking approach for variety, let us suppose that we have determined which of the locations will be occupied by $a$ and $b$. That location mask will give rise to $2$ ways of placing $a,b$ and, independently, $(k-2)!$ ways of placing the other monkeys.

Valid masks can be produced in $(2(k-2)+(k-2)(k-3))/2$ ways, separating the initial selection of the $2$ end positions from the $k{-}2$ mid positions, and then reducing the double count.

This gives the total possibilities as
$\begin{align} 2(k-2)!\cdot(2(k-2)+(k-2)(k-3))/2 &= (k-2)!(k-2)(2+k-3)\\ &=(k-2)!(k-2)(k-1)\\ &=(k-1)!(k-2) \end{align}$

For $k=5$, this gives $24\cdot 3 = 72$ options.

Answer 8

When $a$ should immediately precede $b$, then they together count as a single monkey, so you get $4!$. The other way round ($b$ then $a$), you get another $4!$. Without this condition you get $5!$. You don't want the condition, so subtract:

$$5! - 2\cdot4!$$

Answer 9

  +---+---+---+
  | X | X | X |
  +--- --- ---+     For this illustration, Monkeys **A** & **E** are the restricted monkeys
 ↑    ↑   ↑    ↑    (Maybe they have beef ¯\\_(ツ)_/¯)

Above is an illustration with the "arranging people in seats" style. Say monkeys B,C & D can sit in any order about themselves they like. They have 3!* ways(=6).

Now, monkey A has 4 possible choices(denoted by the arrows above) since he has no restrictions with them. So a total of (6x4=24) arrangements so far.

Monkey E will now be arranged into ANY THREE OF THE REMAINING ARROWS that were not chosen by monkey A, as any of these ensure they are not next to each other. This brings the final tally to (6x4x3=72) arrangements.

NOTE: This approach extends to if there are other monkeys with similar restrictions i.e. the next would have 2 choices, and the next 1, and it would be impossible for another after that to not be next to a restricted monkey.

• If anyone is confused about "3!", it simply means 3 choices for 1, then the next has 2, and the last has 1 => thus 3x2x1 = 6

I hope this helps; it's my first MathStackExchange post. I like this method & thought I should share. Thx