Contar el número de caminos de $(0,0)$ a $(2n,n)$ que no pasar por encima de $y=x$

Question

Contar el número de caminos de $(0,0)$ a $(2n,n)$ que no pasar por encima de $y=x$

Al principio pensé en el problema ampliando el gráfico a $(0,0)$ a $(2n,2n)$ y trasteando con la suma y la resta de múltiplos de la fórmula del número catalán, pero creo que esto es demasiado rudimentario y al hacerlo estoy dejando fuera muchos caminos que se mueven por el $x=n$ a $x=2n$ y $y=0$ a $y=n$ sección cuadrada del gráfico que no tiene restricciones (porque la diagonal se corta en $(n,n)$ ). Por supuesto, sólo se puede ir hacia la derecha y hacia arriba.

Gracias.

Answer 1

El Teorema del voto dice

En una elección en la que el candidato A recibe $p$ votos y el candidato B $q$ votos con $p$ > $q$ la probabilidad de que A esté estrictamente por delante de B a lo largo del recuento es $\dfrac{p-q}{p+q}$

Así que si hubieras preguntado "Cuenta el número de caminos desde $(0,0)$ a $(2n,n)$ que nunca toque $y=x$ "entonces la respuesta habría sido $$\dfrac{n}{3n} {3n \choose n}$$ que puede simplificarse ligeramente.

Pero usted quiere "no pasar nunca por encima $y=x$ " y esto equivale a contar los caminos desde $(-1,0)$ a $(2n,n)$ que nunca se tocan $y=x+1$ o, lo que es lo mismo, las trayectorias de $(0,0)$ a $(2n+1,n)$ que nunca se tocan $y=x$ .

Como esto puede ser una tarea para casa, tal vez deberías probar un poco para terminar esto.

Answer 2

La forma más sencilla de hacerlo parece ser la partición basada en el lugar donde se cruzan los caminos de $x=n$ a $x=n+1$ y luego grapar los dos cálculos: primero, cuántos caminos de $(0,0)$ a $(n, k)$ ( $k \leq n$ ) nunca superan la diagonal (esto debería ser factible mediante versiones de las maquinaciones habituales que te llevan a los números catalanes), y luego cuántos caminos hay desde $(n+1, k)$ a $(2n, n)$ (que es, por supuesto, el mismo que el número de caminos de $(0, 0)$ a $(n-1, n-k)$ y se evalúa fácilmente).