Pregunta: ¿cuántas rutas hay de $A$ $B$a lo largo de la cuadrícula en el diagrama de abajo? Sólo puede mover hacia arriba o hacia la derecha hasta llegar a $B$.
Empecé haciendo un listado de algunos de los caminos que se me a $B$. Empecé a hacer una lista...\begin{align*} & \text{UUURRUURRUURRR}\\ & \text{UUURRRUURUURRR}\\ & \text{UURRUUURRURRRU}\\\vdots\end{align*} Pronto, me di cuenta de que esto era un simple recuento de problema. Así que me puse a$$\binom{14}{7}=\text{Some large number greater than 2000}$$ Pero la respuesta fue exactamente $2000$. ¿De dónde me salen mal?
Respuestas
¿Demasiados anuncios?
user90997
Puntos
1
A de ajuste en el % de origen $(0,0) $, debemos necesariamente pasamos por ya sea el % de punto $C=(3,2)\, $o el punto $D=(2,3)\, \, $. Del mismo modo, debemos también necesariamente pasamos por tanto el % de punto $E=(5,4) \,\,$o el punto $F=(4,5) \,\,$.
Las vías que cruce $C $ y $E $ son $\binom{5}{3} \binom{4}{2} \binom{5}{3} =600 \, \,\, \,$, mientras que ésos travesía $C $ y $F $ $\binom{5}{3} \binom{4}{1} \binom{5}{3} =400\, \, \,$ son. Por lo tanto, un total de $1000$ rutas pasan por $C $. Debido a la simetría del problema es igual el número de caminos pasando por $D $. Así que tenemos un total de $2000$ rutas.
$\hspace{2cm}$
Consulte el diagrama anterior.
Denotar $\vec{XY}_Z$ a medida que el número de maneras de moverse de un punto a a $X$ a punto de $Y$ que se mueve a través opcional punto de $Z$. Queremos encontrar a $\vec{AB}$.
En primer lugar se considera el número de rutas a través de $C$, es decir,$\vec{AB}_C$. El problema puede ser simplificado mediante la superposición de varios $2\times 3$ hexominoes (mostrado en rojo) en el original y red extendida.
$\vec{AB}_C$ puede ser calculada como un producto de varios subtrazos como sigue (* indica multiplicar): $$\vec{AB}_C=\vec{AC}*\left[\vec{CE}* \vec{EB}+\vec{CF}*\vec{FB}\right]$$
Tenga en cuenta que
$\vec{CE}+\vec{CF}=\vec{CG}$ (por simetría, y también porque el $G$ está a un paso de $E,F$) y
$\vec{FB}=\vec{EB}=\vec{GH}$ (mudanza de cuadros verdes a cuadros azules en celosía de extensión).
Por lo tanto $$\vec{AB}_C=\vec{AC}*[(\vec{CE}+\vec{CF})*\vec{GH}]=\vec{AC}*\vec{CG}*\vec{GH}=\binom 52^3$$
Por simetría a lo largo de la diagonal $AB$, es obvio que $\vec{AB}_D=\vec{AB}_C$. Una similar, pero ortogonal conjunto de hexominoes puede ser dibujado para $\vec{AB}_D$.
Por lo tanto el número total de rutas de $A$ $B$es dado como
$$\vec{AB}=\vec{AB}_C+\vec{AB}_D=\color{red}{2\binom 52^3=2000}$$
Caso General
Para una configuración similar de $3$ celosías de cada dimensión $n\times n$ y la superposición de una casilla a lo largo de un común diagonal, el número de rutas de acceso de los más bajos de la izquierda seleccione la más alta situada más a la derecha del punto está dada por $$2\binom {2n-1}{n-1} ^3$$
También puede ser demostrado que para una configuración similar de $m$ attices cada dimensión de $n\times n$ y la superposición de una casilla a lo largo de un común diagonal, el número de rutas de acceso de los más bajos de la izquierda seleccione la más alta situada más a la derecha del punto está dada por $$2\binom {2n-1}{n-1} ^m$$
David Basarab
Puntos
25852
EDIT: tengo algunos de los números de debajo y soy demasiado perezoso para solucionarlos, pero el principio general se aplica todavía.
Me gustaría hacerlo a la antigua usanza y acaba de calcular el número de rutas de acceso a cada punto (añadiendo el número de maneras en que los puntos de "occidente" y "el sur" de cada nodo) hasta que llegué a B. he hecho aproximadamente la mitad de arriba.
