Matemáticas detrás del número de caminos en el problema de array

El problema es contar todos los caminos posibles desde la parte superior izquierda hasta la parte inferior derecha de una array m*n con las restricciones de que desde cada celda puede moverse solo hacia la derecha o hacia abajo.

En primer lugar, lea varias soluciones posibles para el problema planteado aquí

Ahora, para la última solución, la fórmula de combinación para calcular el número de caminos es ^{m + n – 2} C _{m – 1} . Discutamos las matemáticas detrás de esa fórmula.

Supongamos que tenemos una array m*n y, de acuerdo con la pregunta, solo podemos movernos hacia la derecha o hacia abajo.

Aquí m = 5 y n = 3 , comenzamos desde (0, 0) (es decir, comenzamos) y vamos hasta el final, es decir , (4, 2) podemos considerar cualquier ruta, digamos que elegimos
(0, 0) -> ( 0, 1) -> (0, 2) -> (1, 2) -> (2, 2) -> (3, 2) -> (4, 2)
Por lo tanto, nos movemos 2 pasos a la derecha y 4 pasos hacia abajo . Incluso si tomamos cualquier otro camino, se requerirá el mismo número de pasos hacia la derecha y hacia abajo.

Ahora recuerda la combinación en matemáticas. Es solo que en lugar de letras tenemos caminos. Aquí tenemos que cubrir n-1 + m-1 de longitud celular hasta destino.
Recuerde también que estamos moviendo m-1 pasos hacia abajo y n-1 hacia la derecha. ¡ Por lo tanto, el número de caminos será esencialmente (m + n – 2)! / (n – 1)! * (m – 1)! que no es más que ^{m + n – 2} C _{n – 1} o ^{m + n – 2} C _{m – 1} .