Cuántas palabras posibles de este tipo se pueden formar?

Question

Estamos realizando $10$ letra de las palabras usando las letras de la a $A,C,G,T$.

Cuántas palabras posibles existen de la forma $A...AC...CG...GT...T$

Aquí es donde todo el $A's$ antes de ir a la totalidad de la $C's$ y todos los de la $C's$ ir antes de que todos los $G's$ y todos los de la $G's$ ir antes de que todos los $T's$?

Sé que hay un $4^{10}$ posible de palabras compuesto de las letras $A,C,G,T$ pero no tengo idea de cómo tener en cuenta la overcounting en este bit.

Answer 1

Este problema es equivalente a la cantidad de formas de partición $10$ en cuatro partes, en la que el orden de las particiones de los asuntos. Es decir, $10 = 2 + 3 + 3 + 2$ no es lo mismo que $10 = 3 + 2 + 2 + 3$. El primer número representa el número de Una, el segundo número representa el número de C, y así sucesivamente.

Con el fin de contar el número de maneras, creo que de $10$ puntos y $3$ líneas. El $3$ líneas de dividir el $10$ puntos en cuatro partes. Por lo tanto, tengo un total de $10 + 3 = 13$ espacios para elegir, y necesito colocar 3 líneas. Por lo tanto, la respuesta va a ser ${13 \choose 3} = 286$.

Ejemplos de $10$ puntos y $3$ líneas: $$\cdot\cdot|\cdot\cdot\cdot|\cdot\cdot\cdot\cdot|\cdot$$ $$\cdot\cdot\cdot|\cdot|\cdot|\cdot\cdot\cdot\cdot\cdot$$ $$\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot|\cdot\cdot||$$ $$\cdot\cdot\cdot|\cdot\cdot\cdot|\cdot\cdot|\cdot\cdot$$

Answer 2

Este es "estrellas y barras" - usted está recogiendo los puntos de la cadena en la que 3 de las transiciones. Por lo que solo es $${10+3 \choose 3}=\frac{13!}{10!\:3!} = 286$$

---

Efectivamente estamos extendiendo los diez posiciones reales en la cadena de incluir un extra de tres posiciones para colocar los marcadores de la transición (las "barras").

$$\circ\circ\circ\circ\circ\circ \circ\circ\circ\circ\circ\circ\circ$$

Los marcadores de la transición están en un orden predeterminado, de manera que no necesita de identificación; podemos marcar después de haber seleccionado sus posiciones: $\newcommand{transit}[2]{\tiny{\frac{#1}{#2}}}$

$$\circ\circ\circ/\circ\circ \circ\circ//\circ\circ\circ$$

$$\circ\circ\circ{\transit AC}\circ\circ \circ\circ{\transit CG}{\transit GT}\circ\circ\circ$$

Luego puede rellenar los valores reales - las "estrellas" - basado en los separadores.

$$AAA{\transit AC}CCCC{\transit CG}{\transit GT}TTT$$

y eliminar las transiciones:

$$AAACCCCTTT$$

Es una forma fácil y común callejón sin salida a explorar, a buscar en todas las combinaciones y, a continuación, tratar de pensar en una manera para eliminar duplicados, pero esta es, obviamente, una mucho más simple enfoque.

Answer 3

Supongamos que el 10 letras son bolas (denotado por O). Por lo tanto se tendría $10$ bolas, es decir, O O O O O O O O O O. Ahora, usted puede poner el $3$ barras en el medio para hacer $4$ juegos de estas $10$ bolas, por ejemplo, O|O O O|O O|O O O O. Ahora, supongamos que el número de bolas antes de cada barra es la letra requerida, es decir, en el ejemplo, la palabra es ACCCGGTTTT. Así, el número de maneras de organizar las barras daría el número de la palabra requerida. El número de maneras en las barras puede ser organizado es [10 (bolas) + 4 (divisiones) - 1] elegir 10 (bolas), es decir,$\binom{10+4-1}{10} = \binom{13}{10} = \binom{13}{3}=\frac{13\cdot 12\cdot 11}{3\cdot 2\cdot 1} = 286$. Por lo tanto, hay 286 palabras posibles con las condiciones dadas.

Esta es una ilustración de cómo se formaron las Estrellas y las Barras de obras.