¿Cuántos caminos diferentes de arriba a abajo se escriben ALGEBRA?

Question

Empezando por la A en la parte superior y moviendo sólo una letra a la vez hacia la izquierda o hacia la derecha, ¿cuántos caminos diferentes de arriba a abajo se escriben ALGEBRA?

      A
     L L
    G G G
   E E E E
  B B B B B
 R R R R R R
A A A A A A A

Answer 1

¿Has visto alguna vez Triángulo de Pascal ? Cada elemento de la misma se hace sumando los dos números que están justo encima.

            1
           1 1
          1 2 1
         1 3 3 1
        1 4 6 4 1
      1 5 10 10 5 1
     1 6 15 20 15 6 1

Una propiedad interesante del triángulo, es que si utilizas las reglas que has indicado, el valor de cada elemento denota cuántas formas hay de llegar a esa posición desde arriba

Así que todo lo que tienes que hacer es sumar todas las entradas de la fila 7, lo que te dará cuántas formas únicas hay de ir de la fila uno a la fila 7 siguiendo tus reglas establecidas.

$$1 + 6 + 15 + 20 + 15 + 6 + 1 = 64$$

Por cierto, hay una fórmula para sumar toda una fila, porque el valor total de la fila se duplica esencialmente cada vez que se baja uno. Así que

$$\sum = 2^{rowNumber-1}$$

Si quieres saber más sobre su funcionamiento: Vídeo TED-Ed

Answer 2

La respuesta es $64$ . De hecho, para cualquier $n$ palabra de letras, la respuesta será $2^{n-1}$ .

Podemos demostrarlo por inducción:

1. El caso base para $n=1$ es trivialmente cierto con exactamente una forma.

2. Considere cualquier elemento $(i,j)$ en la pirámide. Para cualquier celda de este tipo hay dos caminos que podemos tomar, ir a la izquierda o ir a la derecha, por lo tanto si el número de caminos para llegar a $(i,j)$ es $m_{i,j}$ entonces el número total de caminos para llegar a la fila $i+1$ aumentará en $2*m$ para todos $j \in [1,i]$ . Este total será $\sum_{j=1}^{i} 2 \times m_{i,j}$ . Por inducción sabemos que esta suma es $\sum_{j=1}^{i} m_{i,j} = 2^{i-1}$ . Por lo tanto, el número total de formas de llegar a la fila $i+1$ es $2^{i}$ .

   Q.E.D.

Curiosamente, el número de formas de llegar a dos columnas en la misma fila de la pirámide no es necesariamente el mismo. Pero la suma del número de formas de llegar a todas esas columnas en una fila concreta siempre sumará una potencia de $2$ . Esto se debe al hecho de que el número de formas de llegar a $(i,j)$ es en realidad el coeficiente binomial $\binom{i}{j}$ y $\sum_{i=0}^{n} \binom{n}{i} = 2^n$

Answer 3

En pocas palabras, en cualquier punto tienes dos opciones, izquierda o derecha. Por lo tanto, el número de caminos es $2^6$ .