Un problema relacionado con el número catalán

Question

Demuestre que el número de formas de apilar monedas con n monedas en la fila inferior se denota con el número catalán $$D_n = \frac{(_{2n}C_n)}{n+1}$$ . He intentado de la manera descrita en la imagen de abajo

Answer 1

Añade una fila de $n+1$ monedas debajo de la fila inferior de $n$ monedas. Llama al centro de la nueva moneda más a la izquierda $P$ y el centro de la nueva moneda más a la derecha $Q$ . Los centros de todas las monedas forman un entramado triangular. Observamos ciertas trayectorias del entramado a partir de $P$ a $Q$ . En concreto, sólo permitimos movimientos de un paso hacia arriba y hacia la derecha o de un paso hacia abajo y hacia la derecha. Además, si es posible moverse hacia arriba y hacia la derecha, exigimos que se haga este movimiento. No es difícil ver que cada pila de monedas con una fila inferior original de $n$ corresponde bajo estas reglas a un único camino de red desde $P$ a $Q$ .

Cada uno de estos caminos es esencialmente un Camino de Dyck de $P$ a $Q$ . Como cada paso lo lleva una unidad a la derecha, debe tener exactamente $2n$ pasos. No es difícil comprobar que cada camino de Dyck de $P$ a $Q$ corresponde a una pila de monedas con un $n$ -base original de la moneda. Por último, es conocido que hay $C_n=\frac1{n+1}\binom{2n}n$ Caminos de Dyck de longitud $2n$ . Así, $D_n=C_n$ .

Ejemplo: El camino de Dyck que se muestra a continuación, con $n=4$ corresponde a la pila que se muestra a su derecha:

         *   *                    O O  
        / \ / \                  O O O O
       *   *   *   *  
      /         \ / \  
     *   *   *   *   *  
     P               Q