Hallar el número de rutas del vértice más a la izquierda al vértice más a la derecha

Question

Supongamos que se puede pasar de un v los dos vértices están conectados por una única arista común. El número de rutas que uno puede tomar desde el vértice más a la izquierda L a través de 6 aristas y 5 vértices intermedios hasta el vértice más a la derecha R es .......

Este es mi examen de práctica para la beca (nivel preuniversitario) y la única forma en que lo hice correctamente es contando pero siento que fue un poco desordenado pero se puede simplificar escribiendo con alfabetos como (u para arriba, d para abajo, s para ir derecho).

Sin embargo, podría haber otras soluciones como la combinación o permutación, probablemente. La clave de respuesta proporcionada es 12. Por favor, díganos lo que piensa y cómo resolver este problema.

Answer 1

Lo molesto son los dos triángulos de abajo y arriba. Puedes obtener la respuesta considerando los caminos que pasan y no pasan por esos triángulos. Para los que no pasan, hay $2\cdot \ 2\cdot 1\cdot1\cdot 2\cdot 1=8$ caminos.

Para los que atraviesan los triángulos, convéncete de que sólo es posible atravesar exactamente uno y no los dos. Para el triángulo inferior hay dos caminos posibles (que sólo difieren en el extremo R). Para el triángulo superior hay dos caminos posibles para llegar a él desde L y luego sólo 1 camino para llegar a R.

Así que la respuesta es 12

Answer 2

Te daré una pista. Intenta hacer estos pasos. Sé que puede parecer tedioso, pero creo que en el proceso de pasar por ella usted puede obtener una idea interesante.

Empezarás por el vértice izquierdo y te desplazarás progresivamente hacia la derecha. Escribirás un número al lado de cada vértice.

Empieza en el vértice más a la izquierda. Escribe un número 1 a su lado.

Ahora mira la segunda columna de vértices. Escribe también un 1 junto a ambos.

Ahora mira la tercera columna de vértices. Para cada vértice, mira las aristas que entran en él desde la izquierda. Para cada arista que entra, obtén el número del vértice situado a la izquierda de la arista (es decir, de la columna 2). Suma todos los números que encuentres y escribe ese número junto al vértice. Hazlo para los tres vértices de la tercera columna. Así que la tercera columna de vértices debe decir 2, 2, 1 de arriba abajo.

Sigue haciendo lo mismo que hiciste antes para cada columna de vértices, obteniendo los números de los vértices conectados a la izquierda y sumándolos. Cuando lo hayas hecho para el último vértice, deberías tener el número de caminos.

Así es como se ve mi diagrama:

            2
1  1  2  2  3  7  12
   1  2  3  2  5  
      1      

Si sigue atascado, eche un vistazo a https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

Answer 3

Intenta etiquetar los vértices y escribir la matriz de adyacencia resultante. Luego súbela a la potencia de 6 y lee la entrada en la posición (i, j), donde i y j son las etiquetas de los vértices situados más a la izquierda y más a la derecha, respectivamente. Como la matriz de adyacencia es de 14 x 14, probablemente debas utilizar un ordenador. Te recomiendo que utilices el sitio web de Wolfram alpha. Aunque no sería demasiado difícil a mano, ya que A^6 = (A^2)^2 A^2.