Encontrar el número de caminos monótonos entre dos puntos, sin restricción o mientras se visita un punto intermedio específico

Question

Un camino monótono desde el punto $A$ hasta el punto $B$ es un camino que solo incluye "arriba" y "derecha".

Si el punto $A$ es $(0,0)$ y el punto $B$ es $(7,9)$, entonces un camino posible es UUUUUUUUURRRRRRR (arriba $9$ veces, derecha $7$ veces). Otro camino podría ser URUUUUUUUURRRRRR.

Mi pregunta es, para la primera parte: ¿cuántos caminos de este tipo hay desde $A$ hasta $B$?

La forma en que intenté resolver esta pregunta fue ver todas las combinaciones posibles para encajar $7$ R's en $16$ espacios diferentes. La razón por la que hay $16$ espacios diferentes es que necesito un total de $7$ derechos y $9$ arribas para llegar de $(7,9)$ a $(0,0)$. Por lo tanto, esto debería ser un problema de combinación de cuántas formas puedo organizar $7$ derechos y $9$ arribas en un espacio de $16$. Al encontrar el número de combinaciones, simplemente puedo encontrar el número de formas de organizar las R's en $16$ espacios diferentes e ignorar el número de formas de organizar las U's. Intenté resolver esto con casos de prueba más pequeños y la respuesta parece ser $\binom{16}{7}$. ¿Alguien puede verificar esto?

La segunda parte del problema que intentaba resolver era encontrar cuántos caminos van desde $(0,0)$ hasta $(3,2)$ hasta $(7,9)$. Para resolver la segunda parte, ignoré el número de caminos que van desde $(0,0)$ hasta $(3,2)$ y me enfoqué en el número de caminos que van desde $(3,2)$ hasta $(7,9)$. Usé el mismo método en la primera parte y obtuve $\binom{11}{4}$. ¿Alguien puede verificar esto?

Answer 1

Su respuesta a la primera parte es correcta. Tenga en cuenta que no está "ignorando" las $U$, aunque - más bien, lo que está haciendo es elegir $7$ espacios para las $R$, de un total de $16$. Y, bueno, los espacios restantes deben ser llenados con $U$ como resultado.

Para la segunda parte, no es correcto. Su respuesta parece estar asumiendo que, si un camino va de $(0,0) \to (7,9)$, seguramente debe detenerse en $(3,2)$, lo cual no es cierto. (Piense, por ejemplo, en un camino que va todo el camino hacia arriba y todo el camino hacia la derecha.) O tal vez está pensando "sólo hay un camino $(0,0) \to (3,2)$", lo cual tampoco es correcto, y puede demostrarlo.

La lógica correcta es encontrar el número de caminos $(0,0) \to (3,2)$ y $(3,2) \to (7,9)$ individualmente, y multiplicar esos números. (Después de todo, cualquier camino $(0,0) \to (3,2) \to (7,9)$ debe pasar por $(3,2)$, así que podemos elegir el camino general eligiendo un camino válido para la primera mitad, y otro camino válido para la segunda mitad.)