Finding permutations recursively.See constraints below

Question

Problem: Let $P(n)$ be the number of permutations of $m$ letters taken $n$ at a time with repetitions but no $3$ consecutive letters being the same. Find a recurrence relation connecting $P(n)$, $P(n-1)$, $P(n-2)$. I am not able to understand problem statement. Please explain it and give a HINT.

Answer 1

To explain the statement, it is easier to give an example. Let $m=2$, $n=3$. So we have two letters, say, $A$ and $B$. Then the $3$-letter permutations you look at are $ABA$, $AAB$, $BAA$, $BAB$, $BBA$, $ABB$.

Now a HINT.

Divide all $n$-letter permutations into two groups: with equal two first letters and with different ones. The permutation of the first kind is a $(n-2)$-letter permutation, to whose beginning a double letter different from its first letter is attached. Similarly, the permutation of the second kind is a $(n-1)$-letter permutation, to whose beginning a single letter different from its first letter is attached.

Try to write the required recurrence from here.