Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
2  
Whoever gave me comment permissions, you are an angel. –  Sean Allred Nov 26 '12 at 17:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.