La recurrencia de la $(n+2)\text{Cat}_{n+1}=(4n+2)\text{Cat}_n$ para los no-cruce de matchings

Question

El número de no-cruce de matchings de los lados de $2n$-gon (es decir, el número de maneras de conectar a los lados de a pares por los no-caminos se cruzan) es $n$'th catalán número, $\text{Cat}_n$.

Cómo probar la combinatoria que $(n+2)\text{Cat}_{n+1}=(4n+2)\text{Cat}_n$ para esta interpretación de la lengua catalana números?

---

Por ejemplo, prueba de ello la recurrencia de las triangulaciones de $(n+2)$-gon se describe en Wikipedia: después de la elección de un lado de la $(n+3)$-gon y contratación corresp. triángulo obtenemos una $(n+2)$-gon, con una marcada y) orientado al borde - quiero algo como esto.

En principio, las triangulaciones y no cruce elecciones están conectados por una cadena de bijections (por ejemplo, matchings $\leftrightarrow$ equilibrada entre paréntesis $\leftrightarrow$ árboles binarios $\leftrightarrow$ triangulaciones) y uno puede intentar el traslado de la descripción en el párrafo anterior a través de esta cadena. Pero de esta manera rápidamente se hace muy complicado (para mí, al menos).

Answer 1

(Será ligeramente más conveniente utilizar el lenguaje de la no-cruce de matchings de puntos en una línea aka equilibrada entre paréntesis.)

Vamos a llamar a () (es decir, un par de elementos adyacentes que están vinculados en el matching) de una hoja. Cada no-cruce de coincidencia tiene al menos una hoja. Para obtener la relación de recurrencia Vamos a contar el número de no-cruce de matchings de $2(n+1)$ elementos con un marcado la hoja.

Ejemplo ($n=2$, las hojas son de color rojo). $((\color{red}{()}))$, $\color{red}{()}\color{red}{()}\color{red}{()}$, $(\color{red}{()}\color{red}{()})$, $(\color{red}{()})\color{red}{()}$, $\color{red}{()}(\color{red}{()})$,

Por un lado, hay $(2n+1)Cat_n$ tal 'decorado' matchings (acaba de tirar el marcado de la hoja). Por otro lado, para conseguir una decoración de coincidencia sólo tenemos que elegir una hoja en uno de $Cat_{n+1}$ elecciones.

Lema. En promedio un nc-coincidencia de las $2(n+1)$ elementos de ha $(n+2)/2$ hojas.

(Así que una vez Lema es probada tenemos $(2n+1)Cat_n=\frac{(n+2)}2Cat_{n+1}$, qed.)

Para demostrar el Lema definir una involución en nc-matchings por la regla de $\overline{(\alpha)\beta}=(\overline\beta)\overline\alpha$. Así, por ejemplo, $\overline{((()))}=()()()$, $\overline{()(())}=(()())$ (y viceversa), $\overline{(())()}=(())()$. Ahora observe que si $\sigma$ $k$ hojas, $\overline\sigma$ $n+2-k$ deja, así que hemos terminado.