How many strings in the set X have length exactly 55?

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?

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.

Answer 1

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$.

Answer 2

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.$$

Answer 3

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.

Answer 4

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)