Números catalanes

Los números catalanes son una secuencia numérica que se presenta en muchos problemas de combinatoria .

La secuencia lleva el nombre del matemático belga Eugene Charles Catalan , aunque también era conocida por Leonhard Euler .

Los números catalanes para formar la sucesión: $C_{n}$ $n=0,1,2,\puntos$

1 , 1 , 2 , 5 , 14 , 42 , 132 , 429 , 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … (secuencia A000108 en OEIS )

Definiciones

El enésimo número catalán se puede definir de varias formas equivalentes, como [1] : $C_{n}$

El número de mosaicos de un convexo ( n +2)-gon en triángulos por diagonales que no se cruzan .
El número de formas de conectar 2 n puntos en un círculo con n cuerdas que no se cortan .
El número de secuencias correctas de corchetes de longitud 2 n , es decir, tales secuencias de n corchetes izquierdos y n derechos, en los que el número de corchetes de apertura es igual al número de corchetes de cierre, y en cualquiera de sus prefijos no hay menos corchetes de apertura. que cerrar corchetes.
- Por ejemplo, para n = 3 hay 5 secuencias de este tipo: ((())), ()(()), ()()(), (())(), (()()) eso es $C_{3}=5$

El número de tuplas de n números naturales como para . $(x_{1},x_{2},\ldots,x_{n})$ $x_1=1$ $x_{i}\leqslant x_{i-1}+1$ $2 \leqslant i \leqslant n$
El número de árboles binarios ordenados no isomorfos con una raíz y n + 1 hojas.
El número de formas posibles de linealizar el producto cartesiano de 2 conjuntos lineales ordenados: de 2 y de n elementos.
Número de rutas de Dick desde el punto (0,0) hasta el punto (n, n). [2]

Propiedades

Los números catalanes satisfacen la relación recursiva : $C_{0}=1\cuádruple$ y para _ ${\displaystyle \quad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i))$ $n\geqslant 1$

Esta relación se obtiene fácilmente del hecho de que cualquier secuencia de paréntesis regular que no esté vacía puede representarse únicamente como w = ( w 1 ) w 2 , donde w 1 , w 2 son secuencias de paréntesis regulares.

Hay otra relación de recurrencia:

C_{0}=1\cuádruple

y .

\quad C_{n}={\binom {2n}{n}}-\sum_{k=0}^{n-1}C_{k}{\binom {2n-2k-1}{ nk}}

Otra fórmula recursiva :

C_{0}=1\cuádruple

y . Si ponemos , obtenemos una recursividad conveniente para los cálculos , .

\left(n+1\right){{C}_{n}}={{4}^{n}}-{\frac {1}{2}}\sum \limits _{k= 0}^{n-1}{{{4}^{nk}}{{C}_{k}}}

{\displaystyle c_{n}={\frac{C_{n}}{4^{n))))

c_{0}=1

c_{n}={\frac {1}{n+1}}-{\frac {1}{2\left(n+1\right)))\sum \limits _{k=0} ^{n-1}{c_{k}}

De aquí se sigue: .

\sum \limits _{k=0}^{\infty }{{\frac {C_{k}}{4^{k}}}=}\sum \limits _{k=0}^{ \infty {c_{k}}=2

También hay una relación de recurrencia más simple: $C_{0}=1\cuádruple$ y . $\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}$

La función generadora de los números catalanes es: $\sum _{n=0}^{\infty}C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.$

Los números catalanes se pueden expresar en términos de coeficientes binomiales : $C_{n}={\frac {1}{n+1}}{2n \elegir n}={\frac {1}{2n+1}}{2n+1 \elegir n}={\ binoma {2n}{n}}-{\binoma {2n}{n-1}}.$

En otras palabras, el número catalán es igual a la diferencia entre el coeficiente binomial central y el triángulo de Pascal adyacente a él en la misma línea .

C_{n}

asintóticamente $C_{n}\sim {\frac {4^{n}}{n^{{3/2}}{\sqrt {\pi }}}}.$

Véase también

Notas

↑ A. Spivak. Números catalanes. — MTsNMO.
↑ Diagramas jóvenes, caminos en una red y el método de reflejos M. A. Bershtein (ITF llamado así por Landau, IPPI llamado así por Kharkevich, NMU), G. A. Merzon (MTsNMO). 2014 (artículo con bibliografía)

Enlaces

S. K. Lando. Conferencias sobre combinatoria . —MTsNMO , 1994.
A. Shen. Secciones 2.6 y 2.7 // Programación: Teoremas y Problemas . — M.: MTsNMO , 2017.
Stanley, Richard P. (2013), anexo en catalán a Combinatoria Enumerativa, Volumen 2 , < http://www-math.mit.edu/~rstan/ec/catadd.pdf >
Weisstein, Eric W. Catalan Number (inglés) en el sitio web Wolfram MathWorld .