Números de Catalan

Los números de Catalan (Catalan numbers) son una sucesión numérica que resulta útil en varios problemas combinatorios, a menudo relacionados con objetos definidos de forma recursiva.

Esta sucesión recibió su nombre del matemático belga Catalan , que vivió en el siglo XIX. (De hecho ya la conocía Euler, que vivió un siglo antes que Catalan).

Los primeros números de Catalan $C_n$ (empezando desde cero):

$1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

Aplicación en algunos problemas combinatorios

El número de Catalan $C_n$ es la solución de

Número de secuencias de paréntesis correctas formadas por $n$ paréntesis de apertura y $n$ de cierre.
El número de árboles binarios plenos con raíz con $n + 1$ hojas (los vértices no están numerados). Un árbol binario con raíz es pleno si cada vértice tiene o bien dos hijos o bien ninguno.
El número de formas de parentizar por completo $n + 1$ factores.
El número de triangulaciones de un polígono convexo con $n + 2$ lados (es decir, el número de particiones del polígono en triángulos disjuntos usando las diagonales).
El número de formas de conectar los $2n$ puntos de una circunferencia para formar $n$ cuerdas disjuntas.
El número de árboles binarios plenos no isomorfos con $n$ nodos internos (es decir, nodos que tienen al menos un hijo).
El número de caminos monótonos en el retículo desde el punto $(0, 0)$ hasta el punto $(n, n)$ en un retículo cuadrado de tamaño $n \times n$ , que no pasan por encima de la diagonal principal (es decir, la que une $(0, 0)$ con $(n, n)$ ).
Número de permutaciones de longitud $n$ que se pueden ordenar con una pila (stack sorted) (es decir, se puede mostrar que el reordenamiento es ordenable con una pila si y solo si no existe un índice $i < j < k$ tal que $a_k < a_i < a_j$ ).
El número de particiones no cruzadas de un conjunto de $n$ elementos.
El número de formas de cubrir la escalera $1 \ldots n$ usando $n$ rectángulos (la escalera consiste en $n$ columnas, donde la $i$ -ésima columna tiene altura $i$ ).

Cálculos

Hay dos fórmulas para los números de Catalan: recursiva y analítica. Como creemos que todos los problemas mencionados arriba son equivalentes (tienen la misma solución), para la demostración de las fórmulas de abajo elegiremos la tarea en la que es más fácil hacerlo.

Fórmula recursiva

$C_0 = C_1 = 1$

$C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$

La fórmula de recurrencia se puede deducir fácilmente del problema de la secuencia de paréntesis correcta.

El paréntesis de apertura más a la izquierda $l$ corresponde a cierto paréntesis de cierre $r$ , que divide la secuencia en 2 partes que a su vez deben ser una secuencia de paréntesis correcta. Así, la fórmula también se divide en 2 partes. Si denotamos $k = {r - l - 1}$ , entonces para $r$ fijo habrá exactamente $C_k C_{n-1-k}$ tales secuencias de paréntesis. Sumando esto sobre todos los $k$ admisibles, obtenemos la relación de recurrencia sobre $C_n$ .

También se puede pensar de la siguiente manera. Por definición, $C_n$ denota el número de secuencias de paréntesis correctas. Ahora, la secuencia se puede dividir en 2 partes de longitud $k$ y ${n - k}$ , cada una de las cuales debe ser una secuencia de paréntesis correcta. Ejemplo:

$( ) ( ( ) )$ se puede dividir en $( )$ y $( ( ) )$ , pero no se puede dividir en $( ) ($ y $( ) )$ . De nuevo, sumando sobre todos los $k$ admisibles, obtenemos la relación de recurrencia sobre $C_n$ .

Implementación en C++


const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init() {
    catalan[0] = catalan[1] = 1;
    for (int i=2; i<=n; i++) {
        catalan[i] = 0;
        for (int j=0; j < i; j++) {
            catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
            if (catalan[i] >= MOD) {
                catalan[i] -= MOD;
            }
        }
    }
}

Fórmula analítica

$C_n = \frac{1}{n + 1} {\binom{2n}{n}}$

(acá $\binom{n}{k}$ denota el coeficiente binomial habitual, es decir, el número de formas de seleccionar $k$ objetos de un conjunto de $n$ objetos).

La fórmula de arriba se puede concluir fácilmente a partir del problema de los caminos monótonos en una cuadrícula cuadrada. El número total de caminos monótonos en el retículo de tamaño $n \times n$ está dado por $\binom{2n}{n}$ .

Ahora contamos el número de caminos monótonos que cruzan la diagonal principal. Consideremos tales caminos que cruzan la diagonal principal y encontremos la primera arista que queda por encima de la diagonal. Reflejamos el camino respecto de la diagonal todo el trayecto que sigue después de esta arista. El resultado es siempre un camino monótono en la cuadrícula $(n - 1) \times (n + 1)$ . Por otro lado, cualquier camino monótono en el retículo $(n - 1) \times (n + 1)$ debe intersectar la diagonal. Por lo tanto, enumeramos todos los caminos monótonos que cruzan la diagonal principal en el retículo $n \times n$ .

El número de caminos monótonos en el retículo $(n - 1) \times (n + 1)$ es $\binom{2n}{n-1}$ . Llamemos a tales caminos “caminos malos”. Como resultado, para obtener el número de caminos monótonos que no cruzan la diagonal principal, restamos los “caminos malos” de arriba, y obtenemos la fórmula:

$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n + 1} \binom{2n}{n} , {n} \geq 0$