¿Cuántas cadenas en el conjunto X tienen una longitud exactamente 55?

Question

Consideremos el conjunto X de las cadenas sobre el alfabeto {a,b} en que todas las carreras de consecutivos a tener, incluso, de longitud y de todas las carreras de consecutivos b longitud impar. Por ejemplo, la cadena aabaaaabaabbbaaaa nos cadena, mientras que la cadena de aabbaa no lo es. Cuántas cadenas en el conjunto X tiene longitud exactamente 55?

He venido con la siguiente información a continuación:

S ---> aA | bB | (signo lambda) S(x) = xA(x) + xB(x) + 1

A ---> aS | bD(x) = xS(x) + xD(x)

B ---> aA | bC | (signo lambda) 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

Una(x) = S(x) + D(x)

B(x) = A(x) + C(x) + 1

C(x) = D(x) + B(x)

D(x) = 2Dx

Esta la información que me de un amigo que había trabajado en el, pero nos puede parecer, para obtener el total, alguien puede ayudarme?

La cantidad que se me ocurrió es:

(55) + B(55) = C(109) + C(110) = C(113)

Si puedo calcular C(113), voy a tener mi respuesta. Alguien me puede ayudar con la obtención de la respuesta, no sé cómo calcular la respuesta de utilizar un ordenador. Yo normalmente uso el software Maple, pero no tengo acceso a este software.

Answer 1

Esta secuencia es Sloane del A062200, que muestra la recurrencia: $$a(n)=2a(n-2)+a(n-3)-a(n-4),$$, que se puede derivar de la siguiente manera.

Podemos construir todas las secuencias de longitud $n \geq 4$ por una de las siguientes operaciones:

• Tome una de las $a(n-2)$ secuencias de longitud $n-2$, y anexar $aa$ al final.
• Tome una de las $a(n-2)$ secuencias de longitud $n-2$, y anexar $bb$ al final.
• Tome una de las $a(n-3)$ secuencias de longitud $n-3$, y anexar $aab$ al final.

Hay un problema, sin embargo. Si añadimos $bb$ al final de una secuencia que termina con $a$, luego tenemos una secuencia con un número de $b$'s. La única manera de que una secuencia puede terminar con un $a$ es por la primera construcción (cuando iba a terminar con $aabb$). Por lo tanto, tenemos overcounted por exactamente $a(n-4)$. Así obtenemos la por encima de la recurrencia.

Tomamos los valores iniciales $a(0)=a(1)=a(2)=1$$a(3)=3$, que puede ser fácilmente calculada.

Para $n=55$, la recurrencia da el número de $2174457329$.

Answer 2

Bienvenido a las Matemáticas.se. Usted puede usar TeX aquí para hacer símbolos tales como lambda: tipo $\lambda$ conseguir $\lambda$.

No entiendo muy bien sus cálculos - no se ha definido ninguna de sus términos. Pero no es difícil encontrar una relación de recurrencia para este problema. Deje $a(n)$ el número de cadenas donde todas las carreras de las consecutivas $a$'s incluso en longitud, y todas las carreras de las consecutivas $b$'s son impares en longitud, y al final en $a$; y definir $b(n)$ a las cadenas definidas de manera similar que termina en $b$. Luego de obtener las relaciones de recurrencia $$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 $$ with $n-2$ letters, you can append two $$'s to it to get another such string with $n$ letters ending in $$. Do you see where the second comes from?

With this information it's not hard to write code to calculate $(n)$, $b(n)$. I calculate $$a(55) + b(55) = 2174457329.$$

Answer 3

Me encantaría ser capaz de comentar sobre esta cuestión, pero al acecho no es exactamente de conseguir que cualquier rep (15 requerida para la presentación de comentarios), así que aquí va.

Esto parece ser una gramática independiente del contexto, ¿estaría en lo correcto? CST.sx parece ser su mejor apuesta para una buena respuesta, pero voy a sugerir que el uso de un python recursiva backtrack algoritmo para determinar exactamente cuántas cadenas hay.