# Why is my counting wrong? Counting the number of distinct permutations such that no two adjacent letters are the same

There are three islands labelled $$A$$, $$B$$, and $$C$$. A grasshopper is on island $$A$$ and hops to one of the two other islands every minute. In how many different ways can the grasshopper end up at island $$C$$ after seven minutes?

Proposed solution: Consider the incomplete sequence $$A$$ _ _ _ _ _ _ $$C$$. We consider the equivalent problem of finding the total permutations possible of the above sequence when inserting the letters $$A$$, $$B$$, or $$C$$ into one of the slots such that the following is obeyed:

• Adjacent slots do not contain the same letter

In the first four slots, each slot has $$2$$ possibilities for a letter. Regarding the antepenultimate slot, there are two cases:

1. containing $$A$$ or $$B$$ implies the penultimate slot must contain $$B$$ or $$A$$ respectively. That is, the choice of letter is fixed.
2. containing $$C$$ implies the penultimate slot must contain $$A$$ or $$B$$. That is, there are $$2$$ choices of letter.

Adding the two cases and subtracting off what I think we are overcounting: $$2^6 - 2^4$$ is my answer. However, by explicit counting I arrive at $$43$$.

I want a combinatorial answer so why is my counting wrong?

• Do you want an explanation of why you are wrong, or do you want a correct argument? Commented Oct 8, 2022 at 7:23
• I would say: $2^6$ choices of letters for the first 6 slots, subtract those where you now end with CC, which is $2^5$, except that you subtracted those which end $CCC$, which were never there in the first place ..., so you end up with $2^6-2^5+2^4-2^3+2^2-2+1=43$ possibilities.
– mcd
Commented Oct 8, 2022 at 7:25
• @mcd how can you end with $CC$? Commented Oct 8, 2022 at 7:28
• One of those C's is the last one that is always there: e.g. one of the $2^6$ choices is A_B_A_B_A_B_C_C.
– mcd
Commented Oct 8, 2022 at 7:35
• Can you explain where you thought the $- 2^4$ came from?
– mcd
Commented Oct 8, 2022 at 7:38

Notation: letter 1 is A, letter 8 is C. We need to choose six letters to fill slots 2 to 7. There are $$2^6$$ ways of doing this with no A in slot 2 and no adjacent letters identical in slots 2 to 7. The problem is that there might be a C in slot 7, so CC at the end. We don't want to count these, so need to subtract all the sequences we initially counted which have a C in slot 7. But this is same problem as before, with six rather than seven jumps. So if $$N(7)$$ is the answer you want, $$N(7) = 2^6 - N(6)$$, and repeating this argument gives $$N(7) = 2^6 -2^5 + 2^4-2^3+2^2-2+1$$.
• Glad you like it @ajotatxe . What is nice is that you'd intuitively expect $\frac{2}{3}$ of the $2^6$ to have A or B, rather than C, in slot 7 - and $2^n - 2^{n-1} + ...$ does indeed tend to $\frac{2}{3} 2^n$ as $n$ gets larger. The slight discrepancy is caused by the slightly higher chance that A will appear in odd-numbered slots, because A is in slot 1, so can't be in slot 2. If the first letter was B, the result would be the same, of course, but with first letter C you get only 42 of the 64 initial arrangements working, as C is slightly more likely to appear in slot 7.
• I had not been considering the $CCC$ and such sequences! Agh, such a mistake. Wonderful explanation, thank you. Commented Oct 8, 2022 at 12:07