Número catalán

Los números de Catalan son una secuencia de números naturales que aparecen en diversos problemas de conteo , a menudo relacionados con objetos definidos recursivamente . Reciben su nombre de Eugène Catalan , aunque fueron descubiertos previamente en la década de 1730 por Minggatu .

El n -ésimo número de Catalan se puede expresar directamente en términos de los coeficientes binomiales centrales mediante

$${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\text{para }}n\geq 0.}$$

Los primeros números de Catalan para n = 0, 1, 2, 3, ... son

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, ... (secuencia A000108 en el OEIS ) .

Una expresión alternativa para C _n es $${\displaystyle C_{n}={\binom {2n}{n}}-{\binom {2n}{n+1}}\quad {\text{para }}n\geq 0\,,}$$ lo cual es equivalente a la expresión dada anteriormente porque${\textstyle {\binom {2n}{n+1}}={\frac {n}{n+1}}{\binom {2n}{n}}}$Esta expresión muestra que C _n es un número entero , lo cual no resulta inmediatamente obvio a partir de la primera fórmula dada. Esta expresión constituye la base para una demostración de la corrección de la fórmula .

Otra expresión alternativa es $${\displaystyle C_{n}={\frac {1}{2n+1}}{\binom {2n+1}{n}}\,,}$$ lo cual puede interpretarse directamente en términos del lema del ciclo ; véase más abajo.

Los números de Catalan satisfacen las relaciones de recurrencia.$${\displaystyle C_{0}=1\quad {\text{y}}\quad C_{n}=\sum _{i=1}^{n}C_{i-1}C_{ni}\quad {\text{para }}n>0}$$ y $${\displaystyle C_{0}=1\quad {\text{y}}\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1}\quad {\text{para }}n>0.}$$

Asintóticamente, los números de Catalan crecen como $${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}\,,}$$ en el sentido de que el cociente del n -ésimo número de Catalan y la expresión de la derecha tiende a 1 cuando n tiende a infinito. Esto se puede demostrar utilizando el crecimiento asintótico de los coeficientes binomiales centrales , mediante la aproximación de Stirling para n !, o a través de funciones generadoras .

Los únicos números catalanes C _n que son impares son aquellos para los que n = 2 ^k − 1 ; todos los demás son pares. Los únicos números catalanes primos son C ₂ = 2 y C ₃ = 5 . ^{[ 1 ]} De manera más general, la multiplicidad con la que un primo p divide a C _n se puede determinar expresando primero n + 1 en base p . Para p = 2 , la multiplicidad es el número de bits 1, menos 1. Para p un primo impar, se cuentan todos los dígitos mayores que ⁠ p + 1 / 2 ⁠ ; también se cuentan los dígitos iguales a ⁠ p + 1 / 2 ⁠ a menos que sean finales; y se cuentan los dígitos iguales a ⁠ p − 1 / 2 ⁠ si no son finales y se cuenta el siguiente dígito. ^{[ 2 ]} Los únicos números catalanes impares conocidos que no tienen el último dígito 5 son C ₀ = 1 , C ₁ = 1 , C ₇ = 429 , C ₃₁ , C ₁₂₇ y C ₂₅₅ . Los números catalanes impares, C _n para n = 2 ^k − 1 , no tienen el último dígito 5 si n + 1 tiene una representación en base 5 que contiene solo 0, 1 y 2, excepto en el lugar menos significativo, que también podría ser un 3. ^{[ 3 ]}

Los números de Catalan tienen las representaciones integrales ^{[ 4 ] [ 5 ]}

$${\displaystyle C_{n}={\frac {1}{2\pi }}\int _{0}^{4}x^{n}{\sqrt {\frac {4-x}{x}}}\,dx\,={\frac {2}{\pi }}4^{n}\int _{-1}^{1}t^{2n}{\sqrt {1-t^{2}}}\,dt.}$$ lo cual produce inmediatamente $${\displaystyle \sum _{n=0}^{\infty }{\frac {C_{n}}{4^{n}}}=2.}$$

Esto tiene una interpretación probabilística simple. Consideremos una caminata aleatoria en la recta de los enteros, comenzando en 0. Sea −1 un estado de "trampa", de modo que si el caminante llega a −1, permanecerá allí. El caminante puede llegar al estado de trampa en los tiempos 1, 3, 5, 7,… y el número de maneras en que el caminante puede llegar al estado de trampa en el tiempo 2k + 1 es C _k . Dado que la caminata aleatoria unidimensional es recurrente, la probabilidad de que el caminante finalmente llegue a −1 es $${\displaystyle \sum _{n=0}^{\infty }{\frac {C_{n}}{2^{2n+1}}}=1.}$$

En combinatoria existen numerosos problemas de conteo cuya solución viene dada por los números de Catalan. El libro «Enumerative Combinatorics: Volume 2», _del combinatorialista Richard P. Stanley, contiene un conjunto de ejercicios que describen 66 interpretaciones diferentes de los números de Catalan. A continuación se presentan algunos ejemplos, con ilustraciones de los casos C₃ = 5 y C₄ = ₁₄ .

• C _n es el número de palabras de Dyck ^{[ 6 ]} de longitud 2 n . Una palabra de Dyck es una cadena que consta de n X y n Y, de modo que ningún segmento inicial de la cadena tiene más Y que X. Por ejemplo, las siguientes son las palabras de Dyck hasta una longitud de 6:

• Reinterpretando el símbolo X como un paréntesis de apertura e Y como un paréntesis de cierre, C _n cuenta el número de expresiones que contienen n pares de paréntesis que coinciden correctamente. Por ejemplo, para n = 3, estos son:

• C _n es el número de maneras diferentes en que n + 1 factores pueden ser completamente entre paréntesis, es decir, el número de maneras de asociar n aplicaciones de un operador binario (como en el problema de la multiplicación en cadena de matrices ). Para n = 3 , por ejemplo, tenemos las siguientes cinco formas diferentes de entre paréntesis completas de cuatro factores:

• Las aplicaciones sucesivas de un operador binario pueden representarse en términos de un árbol binario completo , etiquetando cada hoja como a , b , c , d . De ello se deduce que C _n es el número de árboles binarios completos con n + 1 hojas, o, equivalentemente, con un total de n nodos internos:

• C _n es el número de árboles ordenados (o planos) no isomorfoscon n + 1 vértices. ^{[ 7 ]} Véase codificación de árboles ordenados como árboles binarios . Por ejemplo, C _n es el número de posibles árboles de análisis sintáctico para una oración (suponiendo ramificación binaria), en el procesamiento del lenguaje natural.
• C _n es el número de caminos reticulares monótonos a lo largo de los bordes de una cuadrícula de n × n celdas cuadradas, que no pasan por encima de la diagonal. Un camino monótono es aquel que comienza en la esquina inferior izquierda, termina en la esquina superior derecha y consta enteramente de bordes que apuntan hacia la derecha o hacia arriba. Contar dichos caminos es equivalente a contar palabras de Dyck: X representa "mover a la derecha" e Y representa "mover hacia arriba".

Los siguientes diagramas muestran el caso n = 4 :

Esto se puede representar enumerando los elementos catalanes por altura de columna: ^{[ 8 ]}

• Un polígono convexo de n + 2 lados se puede dividir en triángulos uniendo sus vértices con segmentos de línea que no se cruzan (una forma de triangulación de polígonos ). El número de triángulos formados es n y el número de maneras diferentes en que esto se puede lograr es C _n . Los siguientes hexágonos ilustran el caso n = 4 :

• C _n es el número de permutaciones ordenables en pila de {1, ..., n } . Una permutación w se llama ordenable en pila si S ( w ) = (1, ..., n ) , donde S ( w ) se define recursivamente de la siguiente manera: escribir w = unv donde n es el elemento más grande en w y u y v son secuencias más cortas, y establecer S ( w ) = S ( u ) S ( v ) n , siendo S la identidad para secuencias de un elemento.
• C _n es el número de permutaciones de {1, ..., n } que evitan el patrón de permutación  123 (o, alternativamente, cualquiera de los otros patrones de longitud 3); es decir, el número de permutaciones sin ninguna subsecuencia creciente de tres términos. Para n = 3 , estas permutaciones son 132, 213, 231, 312 y 321. Para n = 4 , son 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 y 4321.
• C _n es el número de particiones no cruzadas del conjunto {1, ..., n } . Por consiguiente , C _n nunca excede el n -ésimo número de Bell . C _n es también el número de particiones no cruzadas del conjunto {1, ..., 2 n } en las que cada bloque tiene un tamaño de 2.
• C _n es el número de maneras de cubrir una forma escalonada de altura n con n rectángulos. Al cortar a través de la antidiagonal y observar solo los bordes, se obtienen árboles binarios completos. La siguiente figura ilustra el caso n = 4 :

• C _n es el número de diagramas de Young estándar cuyo diagrama es un rectángulo de 2 x n . En otras palabras, es el número de maneras en que los números 1, 2, ..., 2 n pueden ordenarse en un rectángulo de 2 x n de manera que cada fila y cada columna sean crecientes. Por lo tanto, la fórmula puede derivarse como un caso especial de la fórmula de longitud de gancho .

123 124 125 134 135 456 356 346 256 246 

• C _n es el número de secuencias de longitud n que comienzan con 1, y pueden aumentar en 0 o 1, o disminuir en cualquier número (hasta al menos 1). Para n = 4, estas son 1234, 1233, 1232, 1231, 1223, 1222, 1221, 1212, 1211, 1123, 1122, 1121, 1112, 1111. Desde un camino de Dyck, comience un contador en 0. Una X aumenta el contador en 1 y una Y lo disminuye en 1. Registre los valores solo en las X. Comparado con la representación similar de los números de Bell , solo falta 1213.

Hay varias maneras de explicar por qué la fórmula $${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}}$$ Resuelve los problemas combinatorios mencionados anteriormente. La primera demostración que se muestra a continuación utiliza una función generadora . Las demás demostraciones son ejemplos de demostraciones biyectivas ; implican contar literalmente una colección de algún tipo de objeto para llegar a la fórmula correcta.

Segunda prueba

Llamamos camino malo a aquel que comienza en ( x , y ) = (0, 0) , termina en ( n , n ) , es monótono y contiene un punto por encima de la línea y = x . Contamos el número de caminos malos estableciendo una biyección con caminos que comienzan en (0, 0) , terminan en ( n − 1, n + 1) , y son monótonos.

Para una trayectoria incorrecta dada, construya una trayectoria reflejada de la siguiente manera. Sea P el primer punto de la trayectoria incorrecta que interseca la recta y = x + 1. La trayectoria incorrecta desde (0, 0) hasta P es el inicio de la trayectoria reflejada. La parte de la trayectoria incorrecta desde P hasta ( n , n ) reflejada a través de la recta y = x + 1 es el resto de la trayectoria reflejada. Vea la ilustración para un ejemplo. La línea negra representa los puntos comunes a ambas trayectorias, la línea roja punteada es el resto de la trayectoria incorrecta y la línea roja continua es el resto de la trayectoria reflejada.

Esta es una biyección porque todo camino monótono de (0, 0) a ( n − 1, n + 1) se puede construir a partir de un camino malo, y todo camino reflejado es invertible de forma única al encontrar el único punto P , que debe existir porque todo camino de este tipo debe intersecar y = x + 1 .

El número de pasos en la trayectoria reflejada es ( n − 1) + ( n + 1) = 2 n . El número de pasos hacia arriba es n + 1 porque la trayectoria es monótona y comienza en y = 0 y termina en y = n + 1 .

El número de caminos reflejados se puede contar de la forma habitual, contando cuántos pasos ascendentes se pueden distribuir entre el total de pasos, que es${\textstyle {\binom {2n}{n+1}}}$y el número de caminos catalanes (buenos caminos) se obtiene restando el número de malos caminos del número total de caminos monótonos de la cuadrícula original,

$${\displaystyle C_{n}={\binom {2n}{n}}-{\binom {2n}{n+1}}={\binom {2n}{n}}-{\frac {n}{n+1}}{\binom {2n}{n}}={\frac {1}{n+1}}{\binom {2n}{n}}.}$$

Esta demostración puede reformularse en términos de palabras de Dyck. Partimos de una secuencia (no de Dyck) de n X y n Y e intercambiamos todas las X e Y después de la primera Y que viola la condición de Dyck.

Tercera prueba

Esta demostración biyectiva proporciona una explicación natural para el término n + 1 que aparece en el denominador de la fórmula para C _n . Una versión generalizada de esta demostración se puede encontrar en un artículo de Rukavicka (2011). ^{[ 10 ]} 

Dado un camino monótono, la superación del camino se define como el número de aristas verticales por encima de la diagonal. Por ejemplo, en la Figura 2, las aristas por encima de la diagonal están marcadas en rojo, por lo que la superación de este camino es 5.

Dado un camino monótono cuya frecuencia de excedencia no es cero, aplicamos el siguiente algoritmo para construir un nuevo camino cuya frecuencia de excedencia sea 1 menor que la del camino inicial.

• Comenzando desde la parte inferior izquierda, siga el camino hasta que pase por encima de la diagonal por primera vez.
• Sigue el camino hasta que vuelva a tocar la diagonal. Denota con X la primera arista que encuentres.
• Intercambia la parte del camino que ocurre antes de X con la parte que ocurre después de X.

En la Figura 3, el punto negro indica el punto donde el camino cruza por primera vez la diagonal. El borde negro es X , y colocamos el último punto de la red de la porción roja en la esquina superior derecha y el primer punto de la red de la porción verde en la esquina inferior izquierda, y colocamos X en consecuencia, para crear un nuevo camino, como se muestra en el segundo diagrama.

La superación ha disminuido de 3 a 2. De hecho, el algoritmo hace que la superación disminuya en 1 para cualquier ruta que le proporcionemos, porque el primer paso vertical que comienza en la diagonal (en el punto marcado con un punto negro) es el único borde vertical que cambia de estar por encima de la diagonal a estar por debajo de ella cuando aplicamos el algoritmo; todos los demás bordes verticales permanecen en el mismo lado de la diagonal.

Se observa que este proceso es reversible : dado cualquier camino P cuya superación sea menor que n , existe exactamente un camino que produce P al aplicarle el algoritmo. De hecho, la arista (negra) X , que originalmente era el primer paso horizontal que terminaba en la diagonal, se ha convertido en el último paso horizontal que comienza en la diagonal. Como alternativa, se puede invertir el algoritmo original para buscar la primera arista que pasa por debajo de la diagonal.

Esto implica que el número de caminos de excedencia n es igual al número de caminos de excedencia n − 1 , que es igual al número de caminos de excedencia n − 2 , y así sucesivamente, hasta cero. En otras palabras, hemos dividido el conjunto de todos los caminos monótonos en n + 1 clases de igual tamaño, correspondientes a las posibles excedencias entre 0 y n . Dado que hay${\textstyle {\binom {2n}{n}}}$caminos monótonos, obtenemos la fórmula deseada $${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}.}$$

La figura 4 ilustra la situación para n = 3. Cada una de las 20 posibles rutas monótonas aparece en algún lugar de la tabla. La primera columna muestra todas las rutas de excedencia tres, que se encuentran completamente por encima de la diagonal. Las columnas de la derecha muestran el resultado de sucesivas aplicaciones del algoritmo, con la excedencia disminuyendo una unidad a la vez. Hay cinco filas, es decir, C ₃ = 5 , y la última columna muestra todas las rutas que no superan la diagonal.  

Utilizando palabras de Dyck, comience con una secuencia de${\textstyle {\binom {2n}{n}}}$. Sea X _d el primer X que hace que una subsecuencia inicial sea igual, y configuremos la secuencia como ( F ) X _d ( L ) . La nueva secuencia es LXF .

La matriz de Hankel n × n cuya entrada ( i , j ) es el número de Catalan C _{i + j −2} tiene determinante 1, independientemente del valor de n . Por ejemplo, para n = 4 tenemos $${\displaystyle \det {\begin{bmatrix}1&1&2&5\\1&2&5&14\\2&5&14&42\\5&14&42&132\end{bmatrix}}=1.}$$

Además, si la indexación se "desplaza" de modo que la entrada ( i , j ) se llena con el número de Catalan C _{i + j −1,} entonces el determinante sigue siendo 1, independientemente del valor de n . Por ejemplo, para n = 4 tenemos $${\displaystyle \det {\begin{bmatrix}1&2&5&14\\2&5&14&42\\5&14&42&132\\14&42&132&429\end{bmatrix}}=1.}$$

En conjunto, estas dos condiciones definen de forma unívoca los números de Catalan.

Otra característica única de la matriz de Catalan-Hankel es que la submatriz n × n que comienza en 2 tiene determinante n + 1 .

$${\displaystyle \det {\begin{bmatrix}2\end{bmatrix}}=2}$$

$${\displaystyle \det {\begin{bmatrix}2&5\\5&14\end{bmatrix}}=3}$$

$${\displaystyle \det {\begin{bmatrix}2&5&14\\5&14&42\\14&42&132\end{bmatrix}}=4}$$

$${\displaystyle \det {\begin{bmatrix}2&5&14&42\\5&14&42&132\\14&42&132&429\\42&132&429&1430\end{bmatrix}}=5}$$

etcétera.

La secuencia catalana fue descrita en 1751 por Leonhard Euler , quien estaba interesado en el número de maneras diferentes de dividir un polígono en triángulos. La secuencia recibe su nombre de Eugène Charles Catalan , quien descubrió la conexión con las expresiones entre paréntesis durante su exploración del rompecabezas de las Torres de Hanoi . El truco de conteo por reflexión (segunda prueba) para las palabras de Dyck fue descubierto por Désiré André en 1887.

El nombre “números catalanes” se originó a partir de John Riordan . ^{[ 14 ]}

En 1988, salió a la luz que la secuencia numérica de Catalan había sido utilizada en China por el matemático mongol Mingantu hacia 1730, cuando comenzó a escribir su libro Ge Yuan Mi Lu Jie Fa [El método rápido para obtener la razón precisa de la división de un círculo] , que fue completado por su estudiante Chen Jixin en 1774 pero publicado sesenta años después. ^{[ 15 ] [ 16 ]} Peter J. Larcombe (1999) esbozó algunas de las características del trabajo de Mingantu, incluido el estímulo de Pierre Jartoux, quien trajo tres series infinitas a China a principios del siglo XVIII.

Por ejemplo, Mingantu utilizó la sucesión catalana para expresar expansiones en serie de${\displaystyle \sin(2\alpha )}$y${\displaystyle \sin(4\alpha )}$en términos de${\displaystyle \sin(\alpha )}$.

Los números catalanes pueden interpretarse como un caso especial del teorema de la papeleta de Bertrand . Específicamente,${\displaystyle C_{n}}$es el número de maneras en que un candidato A con n + 1 votos puede superar al candidato B con n votos.

La secuencia de dos parámetros de enteros no negativos${\displaystyle {\frac {(2m)!(2n)!}{(m+n)!m!n!}}}$ Es una generalización de los números de Catalan. Estos se denominan números supercatalanos , según Ira Gessel . No deben confundirse con los números de Schröder-Hipparchus , que a veces también se denominan números supercatalanos.

Para${\displaystyle m=1}$, esto es solo dos veces los números catalanes ordinarios, y para${\displaystyle m=n}$, los números tienen una descripción combinatoria sencilla. Sin embargo, otras descripciones combinatorias solo se conocen ^{[ 17 ]} para${\displaystyle m=2,3}$y${\displaystyle 4}$, ^{[ 18 ]} y es un problema abierto encontrar una interpretación combinatoria general.

Sergey Fomin y Nathan Reading han proporcionado un número de Catalan generalizado asociado a cualquier grupo de Coxeter cristalográfico finito , concretamente el número de elementos totalmente conmutativos del grupo; en términos del sistema de raíces asociado , es el número de anticadenas (o ideales de orden) en el conjunto parcialmente ordenado de raíces positivas. El número de Catalan clásico${\displaystyle C_{n}}$corresponde al sistema radicular de tipo${\displaystyle A_{n}}$La relación de recurrencia clásica se generaliza: el número de Catalan de un diagrama de Coxeter es igual a la suma de los números de Catalan de todos sus subdiagramas propios máximos. ^{[ 19 ]}

Los números de Catalan son una solución de una versión del problema de los momentos de Hausdorff . ^{[ 20 ]}

Para enteros positivos coprimos r y s , los números de Catalan racionales${\displaystyle {\frac {1}{r+s}}{\binom {r+s}{r}}}$contar el número de caminos reticulares con pasos de longitud unitaria hacia la derecha y hacia arriba desde (0,0) hasta ( r , s ) que nunca pasan por encima de la línea ry = sx . ^{[ 21 ]}

La convolución k -fold de Catalan es:

$${\displaystyle \sum _{i_{1}+\cdots +i_{k}=n \atop i_{1},\ldots ,i_{k}\geq 0}C_{i_{1}}\cdots C_{i_{k}}={\dfrac {k}{2n+k}}{\binom {2n+k}{n}}}$$

• Stanley, Richard P. (2015), Números catalanes . Cambridge University Press, ISBN 978-1-107-42774-7.
• Conway y Guy (1996) El libro de los números . Nueva York: Copernicus, págs.  96–106.
• Gardner, Martin (1988), Viajes en el tiempo y otros enigmas matemáticos , Nueva York: WH Freeman and Company, págs. 253–266 (Cap. 20) , Bibcode : 1988ttom.book.....G , ISBN  0-7167-1924-X
• Koshy, Thomas (2008), Números catalanes con aplicaciones , Oxford University Press, ISBN 978-0-19-533454-8
• Koshy, Thomas y Zhenguang Gao (2011) "Algunas propiedades de divisibilidad de los números de Catalan", Mathematical Gazette 95:96–102.
• Larcombe, PJ (1999). "El descubrimiento chino de los números catalanes en el siglo XVIII" (PDF) . Mathematical Spectrum . 32 : 5–7 .
• Stanley, Richard P. (1999), Combinatoria enumerativa. Vol. 2 , Cambridge Studies in Advanced Mathematics, vol.  62, Cambridge University Press , ISBN 978-0-521-56069-6, MR 1676282 
• Egecioglu, Omer (2009), Una evaluación de determinantes catalanes-hankel (PDF)
• Gheorghiciuc, Irina; Orelowitz, Gidon (2020), Números supercatalanos de tercera y cuarta especie , arXiv : 2008.00133

• Stanley, Richard P. (1998), Apéndice catalán a Combinatoria enumerativa, Volumen 2 (PDF)
• Weisstein, Eric W. "Número catalán" . MathWorld .
• Davis, Tom: Números catalanes . Más ejemplos.
• "Equivalencia de tres interpretaciones de los números catalanes" del Proyecto de Demostraciones de Wolfram
• Materiales de aprendizaje relacionados con triángulos numéricos de partición en Wikiversidad