Sé que desde el origen hasta $(x,y)$ hay $${x+y \choose x} = {x+y \choose y}$$ Trayectorias de la red. La cuestión es encontrar el número de caminos desde el origen hasta $(2n, 2n)$ sin pasar por $(n,n)$ . Mi intento de solución es primero contar todos los caminos posibles que es igual a $${4n \choose 2n}$$ Luego restamos todos los caminos que pasan por el punto $(n,n)$ que tiene que ser igual a todos los caminos que terminan en $(n,n)$ que es $${2n \choose n}$$ Por lo tanto, el número total de caminos de $(2n, 2n)$ a $(n,n)$ es $${4n \choose 2n} - {2n \choose n}$$ Sin embargo, no sé si ese es el número total de caminos que no pasan por $(n,n)$ y terminan en $(2n,2n)$ . Si esto es cierto, ¿cómo puedo demostrar que sólo hay ${2n \choose n}$ caminos que atraviesan $(n,n)$ ?
Respuesta
¿Demasiados anuncios?
Has hecho un buen comienzo. El único problema es que $\binom{2n}n$ sólo cuenta el número de caminos desde $(0,0)$ a $(n,n)$ . Puede combinar cada uno de ellos con cualquier ruta de $(n,n)$ a $(2n,2n)$ y también hay $\binom{2n}n$ de esos, por lo que el número total de caminos que pasan por $(n,n)$ es $\binom{2n}n^2$ .
Si no estás seguro de algo así, una buena idea es probarlo concretamente para números pequeños. En el caso que nos ocupa, puedes enumerar muy fácilmente todos los caminos para $n=1$ y encontrar que $4$ de la $6$ pasar por $(1,1)$ . Si hubieras hecho esto, probablemente te habrías dado cuenta de lo que falta en tu argumento.
