3
$\begingroup$

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.

1 Answers 1

9

Hint: You have $n$ choices for the first symbol. After that, you always have $n-1$ choices.

  • 0
    @Claudio Floreani: Yes, that's right. I wanted to leave you something to do!2011-12-04