Determinación de una relación de recurrencia (Tarea)

Question

Dejemos que ${d_n}$ es el número de cadenas de ADN de longitud n que contienen un par de nucleótidos consecutivos del mismo tipo. Hay cuatro símbolos utilizados en las cadenas de ADN: A, C, G, T . Los nucleótidos se dividen en dos tipos: purinas, A y G y pirimidinas, C y T .

La primera parte del problema consiste en determinar los primeros valores de ${d_n}$ con n \= 1, 2, 3, lo cual estoy bastante seguro de tenerlo correcto:

${d_1}$ = 0 (es imposible que una cadena de longitud 1 tenga un par de nucleótidos consecutivos)

${d_2}$ = 8 { AG, CT, GA, TC, AA, GG, CC, TT }

${d_3}$ = ${4^3}$ - 12 = 64 - 16 = 48 (conjunto de todas las cadenas de longitud 3 menos las cadenas sin 2 tipos de nucleótidos consecutivos):

{ ACA, ACG, GCA, GCG, ATA, ATG, GTA, GTG, TAT, TAC, CAT, CAC, TGT, TGC, CGT, CGC }

La segunda parte del problema me está costando un poco más, que es determinar la relación de recurrencia para ${d_n}$ .

Sé que un buen primer paso es plantear casos, pero este es un problema muy diferente a cualquier otro que haya hecho en mi clase de matemáticas discretas. Cualquier ayuda, aunque sea una pista, será muy apreciada. Si quieres que te aclare algo, por favor, házmelo saber.

Answer 1

Esta es la frase clave de su solución:

conjunto de todas las cadenas de longitud 3 menos las cadenas con 2 tipos de nucleótidos consecutivos

El único problema es que por alguna razón se resta 17 y no 16.

¿Cuántas cadenas no contienen dos tipos iguales consecutivos? Se empieza una cadena con cualquier tipo (4 posibilidades), y en cada paso se añade una de las dos letras posibles del tipo opuesto al último añadido. Para $n=3$ tienes $4*2^2=16$ .

En general, $d_n=4^n-4\cdot2^{n-1}=4^n-2^{n+1}$ . Así, la secuencia comienza con 0, 8, 48, 224, etc.

Pero esto no es una relación de recurrencia. Para ello, considere cómo construiría todas las cadenas de longitud $n$ : en primer lugar, puede tomar cualquier cadena de longitud $n-1$ que satisface la condición y añade cualquier carta a la misma ( $4\cdot d_{n-1}$ ), o tomar una cadena de longitud $n-1$ que no cumpla la condición y añadir una letra del mismo tipo que la última letra ( $2\cdot(4^{n-1}-d_{n-1})$ ). Ahora sumemos las dos para obtener la relación de recurrencia, y comprobemos que la solución de forma cerrada para ella es como la anterior.

Answer 2

Sin pérdida de generalidad, dejemos que el primer símbolo sea $A$ . Si el segundo símbolo es $A$ o $G$ el resto de la cadena puede ser arbitraria. Resultado: $2\cdot 4^{n-2}$ cuerdas.

Si el segundo símbolo es $C$ o $T$ entonces la subcadena que se obtiene al omitir el primer símbolo debe contener ya un par de nucleótidos consecutivos. Resultado: $2 \cdot x$ cadenas, donde $x$ es el número de cadenas de longitud $n-1$ que contienen un par de nucleoides consecutivos y comenzar con un símbolo fijo . Exprese esto en términos de $d_{n-1}$ .

Entonces, $d_n = 4 \cdot ( 2 \cdot 4^{n-2} + 2 \cdot x )$ si no me equivoco.