Número de formas de llegar de un punto a otro.

Question

Calcula el número de formas de llegar a la pizza sin pisar bombas (puedes moverte hacia arriba y hacia la derecha)

Mi solución fue calcular el número de formas de llegar desde el caracol a la pizza (sin incluir las bombas) y restar a ese número el número de formas de llegar desde cualquier bomba a la pizza. A continuación, le añado el número de formas en las que se pisan dos bombas y se llega a la pizza. Por último, añado a ese número el número de formas de pisar tres bombas y llegar a la pizza. (Todo ello a partir del Principio de inclusión-exclusión ). Mi respuesta final fue: $$31293$$ ¿Estoy en lo cierto? ¿Puedes detectar algún error que haya cometido por el camino? Gracias.

(Edición: He contado esas formas mirando las permutaciones de elegir un cierto número de pasos a la derecha, $x$ de la suma de pasos a la izquierda y a la derecha $x+y$ Así que..: $$\binom{x+y}{x}=\binom{x+y}{y}$$ Ver: ¿Cómo puedo hallar el número de los caminos más cortos entre dos puntos de una retícula 2D? )

Answer 1

El simple recuento parece menos tedioso que utilizar el principio de inclusión-exclusión:

Cada rectángulo tiene un número que denota el número de formas de llegar a ese rectángulo desde la esquina inferior izquierda. Para llegar a ese número, basta con sumar los valores de los rectángulos de la izquierda y de la parte inferior. Obviamente, poniendo $0$ en lugar de las bombas antes de los cálculos se ajusta a esa regla general.