TL;DR: ¿Cómo es $2\binom{9+12-1}{9-1}$ el número de caminos de $(3,0)$ $(12,12)$tocar o cruzar por encima de la diagonal $y=x$?
Versión completa:
Soy una estudiante universitaria, asistente de docencia, tutoría de matemáticas discretas de este año, pero tengo que admitir, yo estoy luchando para encontrar una explicación para una expresión de uno de mis alumnos ha venido para arriba con una tarea problema (sin ningún razonamiento lógico)... espero que me puedan ayudar a ver la combinatoria argumento!
El ejercicio en cuestión es:
Cuántos monótona de caminos [es decir, los movimientos permitidos de$(x,y)$$(x+1,y)$$(x,y+1)$] hay de $(3,0)$ $(12,12)$que no toque la diagonal (excepto para el movimiento final?)
Los estudiantes saben que el número de monótona de las rutas de $(0,0)$ $(n,n)$que no la cruz de arriba (pero pueden tocar) de la diagonal está dada por el catalán número $C_n$.
La solución más obvia es la siguiente:
La introducción de un auxiliar de la subdiagonal $1$ unidad de longitud por debajo de vueltas a la pregunta "¿cuántas muchos monótona de las rutas están ahí desde el $(1,0)$ $(12,11)$que se les permite tocar la diagonal y se pasa a través de $(3,0)$?"
De $(1,0)$ solo podemos llegar a $(2,0)$, desde donde se puede llegar a $(3,0)$ o $(2,1)$.
Hay $C_{11}$ monótona de las rutas de a $(12,11)$ a partir de $(1,0)$, e $C_{10}$ a partir de $(2,1)$, así que la respuesta es $C_{11}-C_{10}$.
Otro enfoque válido vi en una presentación:
El número de monótona de las rutas de$(3,0)$$(12,11)$$\binom{20}{11}$, el número de malos caminos (que toque / de la cruz por encima de la diagonal) es $\binom{20}{12}$, así que la respuesta es $\binom{20}{11}-\binom{20}{12}$.
No hay explicación dada por el estudiante, pero me di cuenta de que esta expresión fue más probablemente derivado de André reflexión del método, es decir, el número de monotónica de los caminos es $\binom{9+11}{11}$, y si tenemos que sustituir todas las $\to$ se mueve por $\uparrow$ se mueve y viceversa desde el punto de un camino que va mal, terminamos en $(11,12)$ en lugar de eso, lo que nos da un bijection de los malos caminos a todos los monótona de las rutas de $(3,0)$ a $(11,12)$, de los cuales hay $\binom{8+12}{12}$. (Justo lo suficiente, me hubiera gustado que el estudiante escriba su razonamiento, pero al menos algunos razonamiento válido no era demasiado duro para venir para arriba con.)
Ahora el tercer enfoque es el que yo no puedo envolver mi cabeza alrededor, pero no conduce a la respuesta correcta:
La expresión de todos los monótona de las rutas de$(3,0)$$(12,12)$$\binom{9+12}{9}$, el número de malos caminos es $2\binom{9+12-1}{9-1}$, así que la respuesta es $\binom{21}{9}-2\binom{20}8$.
Ningún razonamiento lógico en todo, así que ahora estoy tratando de averiguar cómo el estudiante llegó a esta conclusión. Estoy totalmente de ver donde $\binom{9+12}{9}$ viene, y al menos uno de los dos ocurrencias de $\binom{9+12-1}{9-1}$ podría ser interpretado como el número de monótona de las rutas de$(3,0)$$(11,12)$, de los cuales todos son malos caminos, pero me parece que no puede averiguar cómo el resto de los malos caminos corresponden a la expresión $\binom{9+12-1}{9-1}$.
