1
$\begingroup$

Ternary strings are those that contain only 3 characters at most. For ex: abcbca is ternary string over set {a,b,c}, etc. Can anyone tell what will be the recursion relation for the string that does not contain consecutive characters , for ex: abccba,bcaacb etc.

Thanks in adavance for the answer.

1 Answers 1

4

Let $a_n$ be the number of good strings of length $n$. Every good string of length $n+1$ is obtained by adding one of two characters to a string of length $n$, one of the two that don’t match its last character, so $a_{n+1}=2a_n$ for $n\ge 1$. However, $a_1=3$, so $a_n=3\cdot2^{n-1}$ for $n\ge 1$.

  • 0
    @satyam: Do you mean strings with just one instance of repetition, or strings that allow only one of the three characters to repeat but allow it to repeat more than once, like `abccbccacccbaba`?2012-09-29