Números de Catalan

Los números de Catalan  son una secuencia de enteros positivos que puede ser muy útil en problemas de conteo en combinatoria. El $n$-ésimo Catalan se puede expresar así usando coeficientes binomiales:

También tienen la fórmula de recurrencia

que también se puede expresar como

Los primeros $5$ números de Catalan son

Aplicaciones

Los números de Catalan se pueden usar para representar una gran variedad de cosas.

Por ejemplo, $C_n$ es igual al número de expresiones de paréntesis válidas de longitud $2n$. Tomemos, por instancia, $C_3=5$:

• ()()()
• (())()
• ()(())
• ((()))
• (()())

También es igual al número de árboles binarios plenos con $n+1$ hojas. La siguiente imagen muestra los $5$ árboles binarios con $4$ hojas:

$C_n$ es también el número de caminos monótonos en el retículo a lo largo de las aristas de una grilla $n \times n$ que no pasan por encima de la diagonal. Los caminos empiezan en la esquina inferior izquierda y terminan en la esquina superior derecha.

Por ejemplo, hay $C_4=14$ caminos en una grilla $4 \times 4$:

Los siguientes dos ejemplos son un poco más de nicho, pero siguen siendo interesantes de pensar.

Consideremos un polígono convexo con $n+2$ lados dividido en $n$ triángulos conectando vértices con rectas que no se intersectan. El número de formas distintas de dividir el polígono de esta manera es igual a $C_n$.

Aquí está el caso particular para $n=3$ en el que tenemos $C_3=5$:

$C_n$ también es igual al número de cadenas montañosas  de longitud $2n$ consistentes en $n$ trazos hacia arriba y $n$ trazos hacia abajo.

Derivaciones

Usando la interpretación de “cadenas montañosas”, podemos derivar dos demostraciones biyectivas agradables de las fórmulas de Catalan.

Reflexión

Consideremos conteo complementario: entonces necesitamos caracterizar los caminos que bajan por debajo del nivel del suelo, es decir, los caminos que tocan la recta $y = -1$. Resulta que para cada camino así que termina en $(2n, 0)$, podemos biyectarlo a un camino que termina en $(2n, -2)$ reflejando una porción del camino, de esta forma:

Para ser precisos, la biyección se define así:

• Para ir de azul a rojo, reflejamos el camino azul respecto del primer punto que toca $y = -1$. Como asumimos que el camino azul toca $y = -1$ al menos una vez, este punto está garantizado que existe.
• Para ir de rojo a azul, también reflejamos el camino rojo respecto del primer punto que toca $y = -1$. Este punto está garantizado que existe porque el camino empieza en $y = 0$ y termina en $y = -2$, lo que significa que debe cruzar $y = -1$ en algún punto.

Por lo tanto, el número de caminos azules es igual al número de caminos rojos, y el número de caminos rojos es fácil de contar:

Así, el número de cadenas montañosas es el número total de caminos menos el número de caminos azules:

Observar que podemos generalizar esta biyección: para contar los caminos que cruzan $y = -k$, podemos en cambio contar el número de caminos que terminan en $(2n, -2k)$.

Excedencia

Esta explicación ofrece más intuición sobre por qué aparece $\frac{1}{n + 1}$ en la expresión final.

Primero, definamos la excedencia (exceedance) de un camino como el número total de trazos hacia arriba que da por encima de $y = 0$.

Un camino con excedencia 5.

El resultado central es que para todo $i$ de $0$ a $n$, el número de caminos con excedencia $i$ es igual. Por lo tanto, el número de cadenas montañosas, es decir, el número de caminos con excedencia $n$, es precisamente $\frac{1}{n + 1}$ del número total de caminos.

Para demostrar esta igualdad, definiremos una biyección entre caminos con excedencia $i$ y caminos con excedencia $i + 1$ para $0 \leq i \lt n$. Consideremos el siguiente mapeo: para un camino con excedencia $i$, tomamos el último trazo hacia abajo que va de $y = 0$ a $y = -1$ y lo movemos al final del camino.

Esta transformación efectivamente incrementa la excedencia en 1, pero por desgracia no es biyectiva. Una forma fácil de verlo es el hecho de que el camino resultante siempre termina en un trazo hacia abajo, lo que claramente no cubre todos los caminos posibles de excedencia $i + 1$.

Por suerte, hay un arreglo fácil: después de aplicar nuestro mapeo actual, ¡intercambiamos la segunda mitad (es decir, la parte originalmente después de la flecha roja) del camino con la primera!

Podemos mostrar que este mapeo es invertible verificando que transforma la flecha roja del último trazo hacia abajo de $y = 0$ a $y = -1$, en el primer trazo hacia abajo de $y = 1$ a $y = 0$. Por lo tanto, hemos establecido una biyección entre caminos con excedencia $i$ y caminos con excedencia $i + 1$, como queríamos.

Solo por diversión, aquí hay una imagen de Wikipedia que demuestra cómo este algoritmo disminuye la excedencia de varios caminos:

Bracket Sequences I

Explicación

El problema es una aplicación directa de los números de Catalan. La respuesta para $N$ es el número de Catalan $N/2$.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <iostream>
 
using namespace std;
 
const int MOD = 1e9 + 7;
const int MAXN = 1e6;
 
long long fac[MAXN + 1];
long long inv[MAXN + 1];
 
// BeginCodeSnip{Combinatorics Functions (from the module)}
long long exp(long long x, long long n, long long m) {
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}
 
void factorial(long long p) {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % p; }
}
 
void inverses(long long p) {
	inv[MAXN] = exp(fac[MAXN], p - 2, p);
	for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % p; }
}
 
long long choose(long long n, long long r, long long p) {
	return fac[n] * inv[r] % p * inv[n - r] % p;
}
// EndCodeSnip
 
int main() {
	long long n;
	cin >> n;
 
	if (n % 2) {
		cout << 0 << endl;
		return 0;
	}
 
	factorial(MOD);
	inverses(MOD);
 
	cout << exp(n / 2 + 1, MOD - 2, MOD) * choose(n, n / 2, MOD) % MOD << endl;
}

MAXN = 10**6
MOD = 10**9 + 7
 
fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)
 
 
# BeginCodeSnip{Combinatorics Functions (from the module)}
def exp(x: int, n: int, m: int) -> int:
	x %= m
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * x % m
		x = x * x % m
		n //= 2
	return res
 
 
def factorial():
	fac[0] = 1
	for i in range(1, MAXN + 1):
		fac[i] = fac[i - 1] * i % MOD
 
 
def inverses():
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD)
	for i in range(MAXN, 0, -1):
		inv[i - 1] = inv[i] * i % MOD
 
 
def choose(n: int, r: int) -> int:
	if n < r:
		return 0
	return fac[n] * inv[r] % MOD * inv[n - r] % MOD
 
 
# EndCodeSnip
 
n = int(input())
 
if n % 2 != 0:
	print(0)
else:
	factorial()
	inverses()
	result = exp(n // 2 + 1, MOD - 2, MOD) * choose(n, n // 2) % MOD
	print(result)

Problemas