Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.