Número de paseos desde $(0, 0)$ a $(2n, 0)$ que son positivos.

Question

Demuestre que el número de paseos de $(0, 0)$ a $(2n, 0)$ que son positivos es igual a $\frac{1}{2n-1}{2n-1 \choose n}$ .

(Este paseo se llama puente).

Aquí, un paso dentro de la caminata es un movimiento de una unidad a la derecha, con la posibilidad de moverse hacia arriba para $1$ y $-1$ . Creo que el paseo al ser positivo significa que se mantiene por encima del eje x y sólo lo toca en $(0,0)$ y $(2n,0)$

He estado pensando que este es el mismo número de caminos de $(1,1)$ a $(2n-1, 1)$ que no tocan el eje x, pero no estoy seguro de que esta sea la forma correcta de hacerlo.

Answer 1

Lo que necesitas son los Números Catalanes, que cuentan los paseos "no negativos" desde $(0,0)$ a $(2n,0)$ . Vienen dados por $C_n = \frac{1}{n+1} \binom{2n}{n}$

Ahora bien, como sólo queremos paseos positivos el primer movimiento tiene que ser $(1,1)$ mientras que el último tiene que ser de $(2n-1,1)$ a $(2n,0)$ . Así que el primer y el último movimiento son fijos y necesitamos encontrar el número de paseos no negativos de $(1,1)$ a $(2n-1,1)$ que es igual a los paseos no negativos de $(0,0)$ a $(2(n-1),0)$ . Ese número viene dado por:

$$C_{n-1} = \frac 1n \binom{2n-2}{n-1} = \frac{(2n-2)!}{(n-1)! \cdot n!} = \frac1{2n-1}\frac{(2n-1)!}{(n-1)!n!} = \frac{1}{2n-1}\binom{2n-1}{n}$$