Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer
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 6: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 6:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.