Trayectorias reticulares que evitan un punto

Question

Mi casa se encuentra en $(0,0)$ y el supermercado se encuentra en $(7,5)$ . Sólo puedo moverme hacia arriba o hacia la derecha. ¿Cuántas rutas diferentes hay? Obviamente, ${12}\choose{7}$ $=$ ${12}\choose{5}$ $=$ $792$ . ¿Cuántos caminos hay si quiero evitar la intersección muy transitada situada en $(3,3)$ ?

Tengo tres ideas, todas ellas conducen a respuestas diferentes:

1) Mi primera idea fue etiquetar la cuadrícula y escribir el número en cada intersección que representa cuántos caminos cruzan ese punto. Esto equivalía a escribir el triángulo de pascales en diagonal inclinada, hasta que llegué a $(3,3)$ donde tuve que escribir un $0$ Pero luego procedí como era de esperar, el número de la intersección era igual al de abajo sumado al de la izquierda. En $(7,5)$ Acabé consiguiendo $490$ .

Después de esto, quería una forma combinatoria para confirmar mi respuesta, así que lo intenté:

2)contando todos los caminos desde $(0,0)$ a $(3,3)$ y restando los de $792$ . Así que aquí restaría ${6}\choose{3}$ $=20$ .

3)contando todos los caminos desde $(3,3)$ a $(7,5)$ y restando los de $792$ . Así que aquí restaría ${6}\choose{4}$ $=15$ .

Así que mi pregunta es: ¿qué método de pensamiento es el correcto y por qué los otros dos no conducen a la respuesta correcta (qué cuentan de más o de menos)? Sospecho que mi primer intento fue correcto, y la respuesta es $490$ ...pero no veo la forma algorítmica de verlo...

EDIT: Hice una corrección en mi cuadrícula. Escribí un $34$ en lugar de un $36$ para la intersección en $(7,2)$ . ¡Uy!

Answer 1

Tienes que mirar el complemento, que son todos los caminos desde $(0,0)$ a $(7,5)$ que pasan por $(3,3)$ .

Como ha señalado, el número de caminos de $(0,0)$ a $(3,3)$ es ${6\choose3} = 20$ y el número de caminos desde $(3,3)$ a $(7,5)$ es ${6\choose4} = 15$ . Por lo tanto, el número de caminos de $(0,0)$ a $(7,5)$ que pasan por $(3,3)$ son todas las combinaciones de los caminos anteriores, lo que significa que $20\cdot15=300$ caminos.

$792-300=492$ y así $492$ es la respuesta final.

Answer 2

Su idea de restar el número de caminos que pasan por $(3,3)$ de $792$ fue una buena idea, pero no la llevaste a cabo del todo bien. El número de caminos que pasan por $(3,3)$ no es $\binom{6}{3}$ ni $\binom{6}{4}$ pero $\binom{6}{3}\binom{6}{4}$ . Esto se debe a que cada camino desde $(0,0)$ a $(7,5)$ a través de $(3,3)$ consiste en dos "minitrampas", una de $(0,0)$ a $(3,3)$ y uno de $(3,3)$ a $(7,5)$ . Hay $\binom{6}{3}$ maneras de elegir el primer camino y $\binom{6}{4}$ maneras de elegir la segunda, lo que resulta en $\binom{6}{3}\binom{6}{4}$ maneras de elegir el camino completo, y $792-\binom{6}{3}\binom{6}{4}$ caminos evitando $(3,3)$ .