Supongamos que estás en $(0,0)$ tienes que ir a $(10,10)$ sin cruzar la línea de donde y = x.
Sólo puede mover hacia arriba o rightwards.
Me he dado cuenta de que es solo pedir la $10th$ catalán número. Pero, ¿cómo puedo demostrarlo?
Respuesta
¿Demasiados anuncios?
Identificar cada ruta con una secuencia ordenada de $10$ $H's$ (los movimientos horizontales) y $10$ $V's$ (movimientos verticales). Por lo tanto, el número de caminos de unirse a $(0,0)$ $(10,10)$(está permitido tocar la línea de $y=x+1$) es $\displaystyle P_{20}^{10,10}=\binom{20}{10}.$
Para obtener el número de rutas que no toca la línea de $y=x+1$ obtendremos el número de rutas de tocarlo. Deje $c$ ser un camino de unirse a $(0,0)$ y $(10,10)$ que toca la línea $y=x+1.$, existe un entero $i$ de manera tal que en el primer $i$ $c$ sostiene que $\mbox{number of}\: V= \mbox{number of}\: H+1.$ Supongamos que $i$ es el entero más pequeño que la satisfacción de esta propiedad. Así que podemos escribir la $i=2j+1,$ donde $j=\mbox{number of}\: H.$ $c$asociará el camino de $c'$ definido por:
$c'$ $c$ compartir la primera $2j+1$ pasos,
El siguiente $2(10-j)-1$ $c'$ se obtienen a partir de los en $c$ cambiando de cada $H$ $c$ uno $V$ y cada una de las $V$ uno $H.$
Desde la última $2(10-j)-1$ $c$ han $10-j$ $H's$ y $9-j$ $V's,$ el paso de $c'$ contiene $9$ $H's$ y $11$ $V's.$ es decir, $c'$ es un paht unirse a $(0,0)$ s $(9,11).$ es obvio que para cada ruta $c$ corresponden sólo una $c'.$
Por el contrario, cada camino de $c'$ unirse a $(0,0)$ $(9,11)$ debe tocar la línea de $y=x+1.$ En una manera similar, podemos asociar a $c'$ sólo una ruta, que une $(0,0)$ $(10,10)$ y toques $y=x+1.$
Así, el número de caminos de unirse a $(0,0)$ $(10,10)$ sin tocar la línea de $y=x+1$ es $$\displaystyle \binom{20}{10}- \binom{20}{9}=\frac{1}{11}\binom{20}{10}.$$
