Calcular cuántos caminos hay para llegar a un punto en un sistema de coordenadas cartesianas

Question

Posible duplicado:
Contar el número de movimientos en una cuadrícula

Tengo un ejercicio en mi clase de Ciencias de la Computación, para averiguar cuántos caminos hay de $(0,0)$ a $(x,y)$ en un sistema de coordenadas cartesianas, mientras que los únicos movimientos legales son move up y move right .

¿Existe un método sencillo para calcular el número de rutas disponibles?

Answer 1

Sí, lo hay. Debes ir a la derecha $x$ tiempos y más $y$ veces, y puede hacer que estos $x+y$ se mueve en cualquier orden. Escriba R para un movimiento hacia la derecha y U para un movimiento hacia arriba: quiere el número de cadenas de $x$ R's y $y$ U's. Hay $\binom{x+y}x$ maneras de elegir qué $x$ lugares obtienen las R, y eso determina completamente la cadena, así que la respuesta es $\binom{x+y}x$ .

Answer 2

Suponiendo que $x\ge 0$ y $y\ge 0$ harás $x+y$ movimientos en total y entre ellos están $y$ se mueve hacia arriba. Eso debería ser $x+y\choose y$ .