el número de bucles en celosía?

Question

Caminar sobre una rejilla. El número de caminos diferentes de $(0,0)$ $(m,n)$utilizando el norte y el este de los pasos es el coeficiente binomial

$C(m+n,m)$

si necesita volver a $(0,0)$ usando el sur y el oeste de pasos, y no pasa por el pasado de los puntos. Entonces, ¿cuál es el número de bucles de caminar de $(0,0)$ $(m,n)$luego de regresar a $(0,0)$? Cualquier expresión algebraica para esto? btw:hice esta pregunta antes, pero no había de obtener una respuesta todavía. Tal vez pueda obtener una buena respuesta en el aquí.

Answer 1

El número de bucles es el número de pares de no-caminos se cruzan s.t. una primera que va desde (0,1) a (m-1,n) y la segunda va de (1,0) a (m,n-1).

No caminos se cruzan en una celosía son contados por algunos determinante de la fórmula. En este caso es sólo $\det\left(\begin{matrix}\binom{m+n-2}{m-1}&\binom{m+n-2}{m-2}\\\\\binom{m+n-2}{n-2}&\binom{m+n-2}{n-1}\end{matrix}\right)=\binom{m+n-2}{m-1}^2-\binom{m+n-2}{m-2}\binom{m+n-2}{n-2}$.

No es difícil demostrar esta fórmula directamente: un par (ruta de acceso de (0,1) a (m-1,n); ruta de acceso de (1,0) a (m,n-1)) ya sea de forma un bucle sin intersección o (si los caminos se cruzan) puede ser (canónicamente) se identifican con un par (ruta de acceso de (0,1) a (m,n-1); ruta de acceso de (0,1) a (m,n-1).

---

Upd. quantumelixir pidió una explicación más detallada. Aquí está.

1. El número de (monótona) entramado de caminos de$(a,b)$$(a',b')$$\binom{(a'-a)+(b'-b)}{a'-a}$.

2. Cualquier bucle se puede descomponer en 2 rutas: la primera, que va de $(0,1)$$(m-1,n)$, y la segunda, que va de $(1,0)$$(m,n-1)$.

3. Hay $\binom{m+n-2}{m-1}$ rutas de cada tipo.

4. Pero no todas las par le da un bucle: necesitamos contar sólo los pares que no interesect; o, de manera equivalente, se debe contar el número de $I$ de las parejas de esos caminos s.t. ellos sí se cruzan - la respuesta a la pregunta original se $\binom{m+n-2}{m-1}^2-I$.

5. Es evidente que existe una bijection entre el conjunto de intersección de los pares (path $(0,1)\to(m-1,n)$, el camino de $(1,0)\to(m,n-1)$) y el conjunto de intersección de los pares (path $(1,0)\to(m-1,n)$, el camino de $(0,1)\to(m,n-1)$) - es decir, "ir por el primer camino (de la pareja) hasta la (primera) punto de intersección, y luego ir por el segundo camino".

6. Por lo $I$ es el número de intersección de los pares (path $(1,0)\to(m-1,n)$, el camino de $(0,1)\to(m,n-1)$). Pero ese par es la intersección!

7. Por lo $I$ es sólo $\binom{m+n-2}{m-2}\binom{m+n-2}{n-2}$. Y la respuesta final es $\binom{m+n-2}{m-1}^2-\binom{m+n-2}{m-2}\binom{m+n-2}{n-2}$.