¿Por qué el término ${ \frac {1}{n-1}} {2n-4 \choose n-2}$ cuenta el número de triangulaciones posibles en un polígono?

Question

En la imagen que se muestra a continuación, se cuenta el número de triangulaciones diferentes en un polígono, cómo se llega a esta expresión, por qué:

$$ {2n-4 \choose n-2} $$

y por qué lo multiplicamos por $${ \frac {1}{n-1}}$$

En este libro no explican este asunto.

Tomé la expresión de conteo de aquí :

Answer 1

Toda triangulación de un $n$ -puede asociarse a un árbol binario con $(n-2)$ nodos, ya que hay $(n-2)$ triángulos en la triangulación. Fija un lado del polígono y considera el triángulo de ese lado. Puede tener uno o dos vecinos, a la izquierda o a la derecha. Los triángulos con un solo vecino son los que comparten un lado (o dos, en el caso del triángulo inicial) con el perímetro del polígono, y los triángulos sin vecinos son los que comparten dos lados con el perímetro del polígono. Por otra parte, todo árbol binario rooteado con $(n-2)$ nodos (donde un hijo derecho difiere de un hijo izquierdo) da una triangulación diferente. Además, todo árbol binario rooteado con $(n-2)$ pueden codificarse como una cadena de $(2n-4)$ paréntesis equilibrados: se asigna la codificación "()" a cada hoja, luego se asigna recursivamente la codificación "(codificación del hijo izquierdo) codificación del hijo derecho" a cada padre, hasta llegar a la raíz. Cada vez que se recorre una arista del árbol se añade un par de paréntesis. Además, cada cadena de $(2n-4)$ paréntesis equilibrado puede ser "decodificado" de forma única en un árbol binario rooteado de izquierda/derecha con $(n-2)$ nodos. La última biyección es entre la cadena de $(2n-4)$ paréntesis equilibrados y las trayectorias hacia arriba o hacia abajo en un $(n-2)\times (n-2)$ cuadrícula cuadrada: partiendo de la esquina inferior izquierda, nos movemos hacia arriba cada vez que encontramos un "(" y hacia la derecha cada vez que encontramos un ")": la condición de equilibrio es equivalente a que nunca crucemos la diagonal de la cuadrícula. Veamos ahora la segunda prueba en Wikipedia sobre los números catalanes y todo está hecho.

Answer 2

Dibujar una regularidad $n$ -gon, y elige uno de los lados. Una vez triangulado, este lado estará en uno de los triángulos. Si eliminamos este triángulo, nos quedan dos polígonos triangulados. Las triangulaciones que encontremos en ellos son arbitrarias, así que esto nos da una recurrencia.

La recurrencia resulta ser la misma que satisface los números catalanes, la que aparece en la "quinta prueba" dada aquí , por lo que el número de triangulaciones es un número catalán.