1

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.

satyam
  • 11

1 Answers1

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$.

Brian M. Scott
  • 616,228
  • Brian can you tell me recursion exp if I want to have consecutive character for one character only like ternary string with one repeated character (ex: bcabcca). – satyam Sep 29 '12 at 06:39
  • @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? – Brian M. Scott Sep 29 '12 at 06:43