1. ## recurrence relations

Find a recurrence relation for the number of ternary strings (0 s, 1 s and 2 s) of length n that contain none of the strings 101, 202, 102, or 201. What are the initial conditions? Use the recurrence to compute the number of such sequences of length 5.

2. To figure out the initial conditions, simply write out the ternary strings for n=1 and n=2:

n=1

0
1
2

n=2

00
01
02
10
11
12
20
21
22

That should be sufficient for some initial conditions. I guess you could also do it for n=0, but there are 0 of length 0.

From here, I would suggest writing out for maybe n=3 and n=4. Beyond that, you may want a computer to spit out such things. Then you could look for a pattern and find the recurrence. That's just a brute force sort of idea.

For now, it's all I've got. We may need to think about this more mathematically, that is, what is the equation for the number of unrestricted ternary strings? Then, what is the mathematical restriction we wish to impose?

3. thank you for your help. I will greatly appreciate it.But I think the real problem starts form 3 itself. So, can you help me in finding the recurrence relation.