Número de rutas en un tablero con una punción

Question

Una foto de la placa y mi solución

Tengo esta $8 \times 6$ junta, pero hay una restricción con él - tenemos un agujero con la esquina inferior izquierda en $(3, 2)$ y arriba a la derecha en $(6, 4)$. Necesito contar el número de maneras posibles de obtener a partir de la esquina superior izquierda a la esquina inferior derecha de la junta.

Puesto que hay dos maneras de ir alrededor del agujero, he contado con ellos y se suman a ellos. Es mi solución correcta o ¿me olvido de algo?

Gracias de antemano!

Answer 1

La costumbre truco aquí es marcar las líneas diagonales de las células, tales que todos los caminos pasan a través de exactamente una de esas células.

S.......1
.......2.
......3..
....  ...
...4.....
..5......
.6......E

Ahora el resultado es una suma de productos de binomios:

• $\binom80\binom60=1$ ruta pasa a través de la celda 1.
• $\binom81\binom61=48$ rutas de ir a través de la celda 2.
• $\binom82\binom62=420$ rutas de ir a través de la célula 3.
• $\binom73\binom72=735$ rutas de ir a través de la célula 4.
• $\binom72\binom71=147$ rutas de ir a través de la célula 5.
• $\binom71\binom70=7$ rutas de ir a través de la célula 6.

Por lo tanto, hay 1358 rutas en total.

Answer 2

Aquí hay una variante, que evalúa el número de celosía de las rutas de acceso de forma iterativa, sumando el número de rutas válidas con menor longitud.

                   

Llegamos a la conclusión de que en concordancia con la respuesta de @ParclyTaxel: El número de rutas válidas es $$\color{blue}{1358}$$

Answer 3

Si la junta directiva no contienen un agujero, cualquier camino implicaría ocho mueve a la derecha y seis a la baja se mueve. El camino está totalmente determinado por la elección de que seis de los catorce movimientos son hacia abajo. Por lo tanto, sin el agujero, no sería $$\binom{14}{6}$$ rutas posibles.

A partir de estos, se debe excluir de los caminos por los que pasan a través de los dos vértices que faltan. Con su sistema de etiquetado, estos vértices son a $(4, 3)$$(5, 3)$.

Las rutas que pasan por el vértice $(4, 3)$: El vértice $(4, 3)$ es de cuatro unidades a la derecha y tres unidades hacia abajo desde la esquina superior izquierda, de manera que no debería ser $\binom{7}{3}$ formas de llegar al vértice de la esquina izquierda. El vértice $(4, 3)$ es también de cuatro unidades a la izquierda y tres unidades hacia arriba desde la parte inferior de la esquina derecha, de manera que no debería ser $\binom{7}{3}$ formas de llegar a la esquina inferior derecha de $(4, 3)$. Por lo tanto, el número de rutas que pasan por el vértice $(4, 3)$ sería $$\binom{7}{3}\binom{7}{3}$$

Las rutas que pasan por el vértice $(5, 3)$: El vértice $(5, 3)$ es de cinco unidades a la derecha y tres unidades de la esquina superior izquierda, de manera que no debería ser $\binom{8}{3}$ formas de llegar al vértice de la esquina superior izquierda. El vértice $(5, 3)$ es de tres unidades a la izquierda y tres unidades hacia arriba desde la parte inferior de la esquina derecha, de manera que no debería ser $\binom{6}{3}$ formas de llegar a la esquina inferior derecha de $(5, 3)$. Por lo tanto, el número de rutas que pasan por el vértice $(5, 3)$ sería $$\binom{8}{3}\binom{5}{3}$$

Sin embargo, si sólo tenemos que restar el número de rutas que pasan a través de estos vértices del total, le han restado las rutas que pasan a través de ambos de estos vértices dos veces. Sólo queremos restar los caminos de una vez, por lo que debemos añadir la espalda.

Las rutas que pasan a través de los vértices $(4, 3)$$(5, 3)$: Hay $\binom{7}{3}$ formas de llegar a $(4, 3)$ a partir de la esquina superior izquierda, un camino para llegar a $(5, 3)$$(4, 3)$, e $\binom{6}{3}$ formas de llegar a la esquina inferior derecha de $(5, 3)$.

Por lo tanto, por la Inclusión-Exclusión Principio, el número permisible de los caminos es $$\binom{14}{6} - \binom{7}{3}\binom{7}{3} - \binom{8}{3}\binom{6}{3} + \binom{7}{3}\binom{6}{3}$$