- #1
toothpaste666
- 516
- 20
Homework Statement
a) Find a rec. rel. for an, the number of sequences of length n formed by u's, v's, and w's with the subsequence vv not allowed.
b) Repeat part a) but now with the requirement that there is no subsequence uwv.
The Attempt at a Solution
a) the first letter in the sequence can be a u and then the rest of the sequence can be formed in an-1 ways, it can be a v with the rest of the sequence formed in an-1 ways or a w with the rest in an-1 ways. so an = an-1 + an-1 + an-1 = 3an-1 . But we haven't dealt with the restriction yet. we need to remove the ways where the sequence vv appears. which is choose the two v's and the rest of the sequence is formed in an-2 ways. so
an = 3an-1 - an-2
I am pretty sure this is right but the course website says the answer is an = 2an-1 + 2an-2 and I can't figure out why
b) this time we subtract off the ways that contain uwv. to find this number choose uwv and the rest of the sequence can be formed in an-3 ways so
an = 3an-1 - an-3
this one is apparently correct.