# Over an alphabet of $n$ symbols, how many are the strings of length $k$ without consecutive symbols repeated?

From combinatorics, it's known that over an alphabet of $n$ symbols there are $n^k$ different strings of length $k$, of which $\frac{n!}{(n-k)!}$ (assuming $k \le n$) are those without any repeated symbols.

But how to find how many strings of length $k$ without consecutive symbols repeated?

For example if the alphabet is {A, B, C }, acceptable strings are ABAB and BACA, whereas ABBA or AAAA are not.

-
Hint: You have $n$ choices for the first symbol. After that, you always have $n-1$ choices.
...which means there are $n*(n-1)^{(k-1)}$ possible strings of length $k$ without consecutive symbols repeated over an alphabet of $n$ symbols. –  Claudio Floreani Dec 4 '11 at 20:21