Número de maneras de ortografía Abracadabra en esta red

Question

Este es embarrasingly, el primer problema en forma de notas en introductorio combinatoria por Polya y Tarjan. (Solucionado, pero no he mirado).

Enunciado del problema: Hallar el número de maneras de ortografía "abracadabra" siempre va de una letra a la adyacente.

$$A$$ $$B \quad B$$ $$R \quad R \quad R $$ $$A\quad A \quad A \quad A $$ $$C\quad C\quad C\quad C\quad C$$ $$A\quad A \quad A \quad A \quad A\quad A$$ $$D\quad D\quad D\quad D\quad D$$ $$A\quad A \quad A \quad A $$ $$B \quad B \quad B $$ $$R \quad R$$ $$A$$

Tengo una muy improbable respuesta de $2^{25}$, así que he intentado un caso más sencillo de entender.

Comenzando en el extremo más septentrional hay dos rutas. En cada uno de los dos B en la segunda fila hay $2$ rutas, de modo que uptil este punto

$$A$$ $$B \quad B$$ $$R \quad R \quad R $$

no debería ser $2^3$ formas de obtener las tres letras de la palabra "ABR", pero en el manual de contar el número de maneras en que se encuentra a sólo 4 (LL, LR, RR, RL donde R=derecha/L=a izquierda). Lo que está mal con mi enfoque? Más precisamente, donde he overcounted?

Edit: he entendido mi problema. He utilizado el producto en lugar de la regla de la suma regla. Creo que voy a dejar de prestar atención a estas "reglas" como están obstaculizando la solución de mi problema de todos modos. (He pedido a una pregunta anterior sobre el tema)

Answer 1

Este es esencialmente el mismo que el de este problema. Empezar por la reescritura de la matriz como un cuadrado, con la parte superior ahora en la parte inferior izquierda, y la parte inferior en la parte superior derecha: $$\begin{array}{cccccc} A & D & A & B & R & A\\ C & A & D & A & B & R\\ A & C & A & D & A & B\\ R & A & C & A & D & A\\ B & R & A & C & A & D\\ A & B & R & A & C & A \end{array}$$ Usted desea obtener de la parte inferior izquierda a la superior derecha, utilizando sólo se mueve a derecha o de arriba. Una simple cosa es que se nota que hay un solo camino para llegar a la parte inferior izquierda, y en cualquier momento, el número de maneras para llegar a un punto es la suma de la cantidad de formas para llegar al punto directamente debajo y el número de maneras para llegar al punto directamente a la izquierda. Esto nos da: $$\begin{array}{cccccc} 1 & 6 & 21 & 56 & 126 & 252\\ 1 & 5 & 15 & 35 & 70 & 126\\ 1 & 4 & 10 & 20 & 35 & 56\\ 1 & 3 & 6 & 10 & 15 & 21\\ 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 1 & 1 & 1 & 1 & 1 \end{array}$$ dando a $252$ maneras.

Alternativamente, en el extremo, usted debe hacer cinco mueve a la derecha y cinco se mueve hacia arriba. Su única decisiones a tomar es cuando se hacen los movimientos. Tiene seis lugares (antes de que todos los movimientos a la derecha, entre dos movimientos a la derecha, y después de todo se mueve a la derecha), y que tiene que elegir, permitiendo repeticiones y sin preocuparse de la orden. Es decir, que desea contar las combinaciones con las repeticiones, la selección de seis de los siete possibililties. La manera de hacer de $r$ opciones de $n$ posibilidades, permitiendo repeticiones y donde no importa el orden, es $\binom{n+r-1}{r}$, por lo que en este caso tenemos $$\binom{6+5-1}{5} = \binom{10}{5} = \frac{10!}{5!5!} = 252.$$

Answer 2

bueno, yo creo que usted tiene que utilizar el principio fundamental de contar hasta el final, dando 2^9, y luego restar 8, ya que en los lados, ya que si usted elige un camino que va a la una de la Una en el borde de la fila 6, usted no tiene una opción de ruta de acceso. Mismo si tienes que elegir uno de los D en el borde de la fila 7. Esto le da a las 8 rutas que uno escoge, no se permite el cambio. Por ejemplo, si tomamos un camino que nos llevó a Una en el borde de la fila 6, entonces no habría elección. Mismo para el resto de las letras en las filas 7,8,9. Después de que se toma cuidado de, usted tiene que dividir por 2, ya que en la forma en que se utilizó el principio fundamental de contar, de ABRACADABRA es el mismo que ARBADACARBA, por lo que se divide por dos para obtener el número EXACTO de formas. Esto es (2^9-8)/2. Esto se traduce en la respuesta correcta, 252