Consider the set X of strings over the alphabet {a,b} in which all runs of conse
ID: 3081825 • Letter: C
Question
Consider the set X of strings over the alphabet {a,b} in which all runs of consecutive a's have even length and all runs of consecutive b's have odd length. For example, the string aabaaaabaabbbaaaa us such a string, whereas the string aabbaa is not. How many strings in the set X have length exactly 55?
HINT:
S ---> aA | bB | ? S(x) = xA(x) + xB(x) + 1
A ---> aS | bD A(x) = xS(x) + xD(x)
B ---> aA | bC | ? B(x) = xA(x) + xC(x) + 1
C ---> aD | bB C(x) = xD(x) + xB(x)
D ---> aD | bD D(x) = xD(x) + xD(x)
S(x) = A(x) + B(x) + 1
A(x) = S(x) + D(x)
B(x) = A(x) + C(x) + 1
C(x) = D(x) + B(x)
D(x) = 2Dx
Explanation / Answer
Let A(n) be the number of such strings of length n that end in a and B(n) be the number of such strings of length n that end in b. We are going to form a system of difference relations for A and B. Consider strings of length n that end in a. We can form each of them uniquely by adding two a's to any such string of length 2. Moreover, if we take any string of length n ending with a, it must end with two a's, and removing the two a's will yield a string obeying the same rules, except of length n - 2. Therefore we have: A(n) = A(n - 2) + B(n - 2) Now, consider the strings of length n that end in b. We can either form them by taking a string of length n - 1 ending with a, and add a single b at the end, or we can take a string of length n - 2 ending with b, and add two b's. Similarly, we can see that every string of length n ending in b must be of that form, so we have: B(n) = A(n - 1) + B(n - 2) Thus, we have a second order linear homogeneous system of difference equations. Now, I tried to solve this in general using the usual methods, but the closed form solution is terrifyingly awful (as in, I wouldn't bother writing it on paper, let alone Y!A), so I suggest we just do some manual computation to work out A(55) + B(55). First we need to work out some initial conditions: A(1) = 0 B(1) = 1 A(2) = 1 B(2) = 0 Thus we have: A(3) = A(1) + B(1) = 1 B(3) = A(2) + B(1) = 2 A(4) = A(2) + B(2) = 1 B(4) = A(3) + B(2) = 1 A(5) = A(3) + B(3) = 3 B(5) = A(4) + B(3) = 3 A(6) = A(4) + B(4) = 2 B(6) = A(5) + B(4) = 4 Now, you could continue on like this. One thing I did notice as I was calculating these numbers was that, if you consider all the numbers in the vertical column (starting with the initial condition), you get a sequence: 0, 1, 1, 0, 1, 2, 1, 1, 3, 3, 2, 4, ... which satisfies the condition: C(n) = C(n - 3) + C(n - 4) It's pretty easy to see why this is true. If n is odd, then C(n) = A(n), C(n - 3) = B(n - 2), and C(n - 4) = A(n - 2), so the above recurrence relation becomes: A(n) = A(n - 2) + B(n - 2) as we need. Similarly, if n is even, then C(n) = B(n), C(n - 3) = A(n - 1), and C(n - 4) = B(n - 2), which yields: B(n) = A(n - 1) + B(n - 2) Thus, the recurrence relation on C captures both conditions. This new sequence C, lamentably, is no easier to solve. However, this new form can be used to expedite the computation process. We have that: A(55) = C(2 * 55 - 1) = C(109) B(55) = C(109 + 1) = C(110) The quantity you're looking for here is: A(55) + B(55) = C(109) + C(110) = C(113) If you can just compute C(113), you'll have your answer. I'd suggest getting a computer to compute the sequence up to C(113)