Reference no: EM131573777
Question: Counting Strings: Consider the set of all strings of a's, b's, and c's.
a. Make a list of all of these strings of lengths zero, one, two, and three that do not contain the pattern aa.
b. For each integer n ≥ 0, let sn = the number of strings of a's, b's, and c's of length n that do not contain the pattern aa. Find s0, s1, s2, and s3.
c. Find a recurrence relation for s0, s1, s2,....
d. Use the results of parts (b) and (c) to find the number of strings of a's, b's, and c's of length four that do not contain the pattern aa.