another question
-
I am having trouble solving this problem
Consider sequences that consist entirely of X’s, Y ’s and Z’s where runs of consecutive X’s, Y ’s, and
Z’s are at most length 3. How many sequences with these properties of length 8 are there?I read the solution, but I don't understand why F(n-1) and F(n-2) need to be multiplied by 2. Here is the solution-
Let the number of sequences of length n with the above properties be F(n). When n ≤ 3,
there are no restrictions for which letters can be used, so F(1) = 3
1 = 3, F(2) = 3
2 = 9, and F(3) =
3
3 = 27. From here, we construct a recursion for greater n. The last run can not be made from the
same letter as the previous run, so there are two choices for the letter of the last run. Also, the last run
can have a length of 1, 2, or 3, so we have the recursion F(n) = 2F(n − 1) + 2F(n − 2) + 2F(n − 3).
Plugging in n = 8 gives us that there are F(8) = 5676 sequences of length 8 with the aforementioned
properties. -
@Kevin-Li
We will get back to you with this... we're thinking about it!
