Número de Catalán

Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 563
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Número de Catalán

Mensaje sin leer por Nacho »

Vamos a definir al número de Catalán como [math]

Hay muchas interpretaciones combinatoriales de este número, que son las que vamos a ver ahora:

Interpretación 1:

La cantidad de caminos monótonos (Un camino monótono es un camino que pasa por puntos enteros desde la esquina inferior izquierda hasta la esquina superior derecha, haciendo sólo movimientos hacia arriba o la derecha) entre [math] y [math] que nunca pasan por arriba de la recta [math] es [math].
catalanpath.png
Demostración de la interpretación 1:

Partimos de un tablero de [math]. Supongamos que tenemos un camino monótono. Vamos a llamar excedente a la cantidad de pasos hacia arriba que se dan superando la recta [math]. Vamos a demostrar que a través de un algoritmo siempre podemos aumentar o reducir al excedente en 1. Tomamos dos partes: para tomar la primera parte, seguimos el camino, cruzando la diagonal, hasta un paso antes de tocar nuevamente (que debe ser hacia la derecha) la diagonal; para tomar la segunda parte, tomamos desde que toca la diagonal hasta que llega al final. El algoritmo consiste en tomar la segunda parte, luego colocar el paso que separa a la primera parte de la segunda y colocar la primera parte.
El algoritmo reduce en uno el excedente ya que corre el primer paso que supera a la recta [math], ubicandolo sobre la recta, pero el resto que superaba a la recta ahora la sigue superando. Es trivial ver que el algoritmo es reversible.
Ahora es claro que la cantidad de caminos con excedente [math] es igual a la cantidad de caminos con excedente [math], que es igual a la cantidad de caminos con excedente [math], y así siguiendo hasta 0. Como hay [math] caminos totales, tenemos que la cantidad de caminos con excedente [math] es [math]. [math]

Interpretación 2:

El número de expresiones que contienen [math] pares de paréntesis que están correctamente apareados es [math].
Ej. para [math]: [math]; [math]; [math]; [math]; [math] .

Demostración de la interpretación 2:

Vamos a hacer una biyección entre esta interpretación y la interpretación 1. Abrir un paréntesis es análogo a ir a la derecha y cerrar un paréntesis es análogo a ir hacia arriba. Además, en el camino nunca podemos estar más arriba de la recta [math] ya que la posición en [math] es la cantidad de paréntesis que se cerraron hasta el momento, y si [math] entonces se cerraron más de los que se abrieron. Por lo tanto, la cantidad de expresiones correctas que se pueden armar con [math] paréntesis es igual a la cantidad de caminos monótonos que nunca pasan por arriba de [math], que es [math]. [math]

Interpretación 3:

El número de árboles planos es con [math] vértices es [math].
Catalanplanetree.png
Demostración de la interpretación 3:

Vamos a hacer una biyección con la interpretación 2. Un vértice es lo mismo que dos paréntesis (uno abriendo y otro cerrando), un vértice que está conectado a un arista y está por debajo de él está contenido adentro de los paréntesis superiores. Por lo tanto, si descontamos el vértice superior, vemos que tenemos que aparear [math] pares de paréntesis, que vimos en el problema 2 que es [math]. [math]

Interpretación 4:

El número de árboles binarios con [math] vértices internos es [math].
catalanbinarytree.png
Demostración de la interpretación 4:

Vamos a hacer una biyección con la interpretación 2. Un vértice es lo mismo que dos paréntesis (uno abriendo y otro cerrando), y un vértice tiene dos vértices unidos a él por un arista. Al vértice que está hacia la izquierda llamémoslo del tipo A y al de la derecha del tipo B. Si es del tipo A, esos paréntesis están dentro de los anteriores, pero si es del tipo B, se encuentran fuera de los anteriores. Así vemos que la cantidad de árboles binarios es lo mismo que aparear [math] pares de paréntesis, que vimos que es [math]. [math]

Una Relación de Recurrencia:

Se cumple que [math].

Demostración de que vale la recurrencia:

Supongamos que tenemos un tablero de [math]. Vamos a contar la cantidad de caminos de [math] a [math] de dos formas. Por lo ya expuesto antes, esa cantidad es precisamente [math].

Vamos a demostrar que la cantidad de caminos entre [math] y [math] y que pasan por debajo de la diagonal es [math]. Esto se debe a que el primer paso debe ser [math], y el último paso debe ser [math]. Luego, queremos contar los caminos entre [math] y [math] que no cruzan la diagonal (ya que si la cruzaran, estarían tocando la diagonal principal). Esta cantidad es [math] por lo expuesto en la interpretación 1.

Ahora, vamos a mirar cada camino entre [math] y [math]. Supongamos que [math] es el primer punto en el camino en el que se toca la diagonal. Tenemos [math] formas de ir hasta ahí. Luego, tenemos [math] formas de ir desde [math] hasta [math]. Entonces, hay [math] caminos cuyo primer punto en la diagonal es [math]. Si vamos corriendo [math] desde [math] hasta [math], obtenemos [math] caminos. Cambiando índices, esto es [math].

Pero habíamos dicho que eso era la cantidad de formas de ir de [math] a [math]. Entonces [math]. [math]
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
5  
Responder