How many strings in the set X have length exactly 55? 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?
I have came up with the following information below:
S ---> aA | bB | (lambda sign) S(x) = xA(x) + xB(x) + 1
A ---> aS | bD A(x) = xS(x) + xD(x)
B ---> aA | bC | (lambda sign) 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
This the information that me a friend had worked on but we cannot seem to get the total, can someone help?
The quantity i came up with is:
A(55) + B(55) = C(109) + C(110) = C(113)
If i can just compute C(113), i'll have my answer. Can someone help me with getting the answer, i do not know how to compute for the answer using a computer. I normally would use the software Maple, but i do not have access to this software.
 A: This sequence is Sloane's A062200, which lists the recurrence: $$a(n)=2a(n-2)+a(n-3)-a(n-4),$$ which can be derived as follows.
We can construct all sequences on length $n \geq 4$ by one of the following operations:


*

*Take one of the $a(n-2)$ sequences of length $n-2$, and append $aa$ at the end.

*Take one of the $a(n-2)$ sequences of length $n-2$, and append $bb$ at the end.

*Take one of the $a(n-3)$ sequences of length $n-3$, and append $aab$ at the end.


There is a catch, however.  If we append $bb$ at the end of a sequence that ends with $a$, then we have a sequence with an even number of $b$'s.  The only way a sequence can end with an $a$ is by the first construction (when it would end with $aabb$).  Hence we have overcounted by exactly $a(n-4)$.  So we obtain the above recurrence.
We take the initial values $a(0)=a(1)=a(2)=1$ and $a(3)=3$, which can be readily computed.
For $n=55$, the recurrence gives the number as $2174457329$.
A: Welcome to Math.se.  You can use TeX here to make symbols such as lambda: type $\lambda$  to get $\lambda$.
I don't quite understand your calculations - you haven't defined any of your terms.  But it's not hard to come up with a recurrence relation for this problem.  Let $a(n)$ be the number of strings where all runs of consecutive $a$'s are even in length, and all runs of consecutive $b$'s are odd in length, and end in $a$; and define $b(n)$ to be those strings defined similarly ending in $b$.  Then you get the recurrence relations  $$a(n) = a(n-2) + b(n-2)$$ $$b(n) = a(n-1) + b(n-2)$$
for $n > 2$. The first since given any string meeting the conditions ending in $a$ with $n-2$ letters, you can append two $a$'s to it to get another such string with $n$ letters ending in $a$.  Do you see where the second comes from?
With this information it's not hard to write code to calculate $a(n)$, $b(n)$.  I calculate $$a(55) + b(55) = 2174457329.$$
A: I would love to be able to actually comment on this question, but lurking doesn't exactly get you any rep (15 required for commenting), so here goes.
This looks to be a context-free grammar, would I be correct? CST.sx seems to be your best bet for a good answer, but I'm going to suggest that you use a python recursive backtrack algorithm to determine exactly how many strings there are.
A: Here is a quick and easy python program for your problem:
list1=[1,1,1,3] #the first four starting numbers

for a in range(55-len(list1)+1): #we have to subtract the starting numbers
    list1.append(-list1[-4]+list1[-3]+2*list1[-2])

print list1[-1] #lists the result (last entry)

