Número catalán

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Secuencia de entero Recursivo

El C₅ = 42 particiones no cruzadas de un conjunto de 5 elementos (abajo, el otro 10 de las 52 particiones)

En matemáticas combinatorias, los números catalanes son una secuencia de números naturales que ocurren en varios problemas de conteo, a menudo involucrando objetos definidos recursivamente. Llevan el nombre del matemático franco-belga Eugène Charles Catalan.

El nésimo número catalán 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!}}=prod limits _{k=2}^{n}{frac {n+k}{k}}qquad {text{for }}ngeq 0.}

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

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

Propiedades

Una expresión alternativa para C_n es

{displaystyle C_{n}={2n choose n}-{2n choose n+1}}

para

ngeq 0,

que equivale a la expresión dada anteriormente porque ${tbinom {2n}{n+1}}={tfrac {n}{n+1}}{tbinom {2n}{n}}$ . Esta expresión muestra que C_n es un entero, que no es inmediatamente obvio de la primera fórmula dada. Esta expresión constituye la base para una prueba de la corrección de la fórmula.

Otra expresión alternativa es

{displaystyle C_{n}={frac {1}{2n+1}}{2n+1 choose n},,}

que se puede interpretar directamente en términos del lema del ciclo; vea abajo.

Los números catalanes satisfacen las relaciones de recurrencia

{displaystyle C_{0}=1quad {text{and}}quad C_{n+1}=sum _{i=0}^{n}C_{i}C_{n-i}quad {text{for }}ngeq 0}

{displaystyle C_{0}=1quad {text{and}}quad C_{n+1}={frac {2(2n+1)}{n+2}}C_{n}.}

Asintóticamente, los números catalanes crecen como

{displaystyle C_{n}sim {frac {4^{n}}{n^{3/2}{sqrt {pi }}}},}

n!

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 primos catalanes son C₂ = 2 y C₃ = 5.

Los números catalanes tienen las representaciones integrales

{displaystyle C_{n}={frac {1}{2pi }}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.}

que cede inmediatamente ${displaystyle sum _{n=0}^{infty }{frac {C_{n}}{4^{n}}}=2}$ .

Esto tiene una simple interpretación probabilística. Considere un paseo aleatorio en la línea entero, comenzando a 0. Dejar -1 ser un estado "trap", tal que si el caminante llega a -1, permanecerá allí. El caminante puede llegar al estado de la trampa a veces 1, 3, 5, 7... y el número de maneras que el caminante puede llegar al estado de la trampa a la vez $2k+1$ es $C_{k}$ . Puesto que el paseo aleatorio 1D es recurrente, la probabilidad de que el caminante llegue finalmente a -1 es ${displaystyle sum _{n=0}^{infty }{frac {C_{n}}{2^{2n+1}}}=1}$ .

Aplicaciones en combinatoria

Hay muchos problemas de conteo en combinatoria cuya solución viene dada por los números catalanes. El libro Combinatoria enumerativa: Volumen 2 del combinatorialista Richard P. Stanley contiene un conjunto de ejercicios que describen 66 interpretaciones diferentes de los números catalanes. A continuación se muestran algunos ejemplos, con ilustraciones de los casos C₃ = 5 y C₄ = 14.

Lattice de las 14 palabras Dyck de la longitud 8 – () y ) interpretada arriba y abajo

C_n es el número de palabras Dyck de longitud 2n. Una palabra Dyck es una cuerda que consiste en n X's and n Y es tal que ningún segmento inicial de la cuerda tiene más Y's que X's. Por ejemplo, las siguientes son las palabras Dyck hasta la longitud 6:

XXYY XYXY

XXXYYYY XYXYY XYXY XXYYXY XXYXY

Reinterpretando el símbolo X como paréntesis abierta y Y como paréntesis cercana, C_n cuenta el número de expresiones que contienen n pares de paréntesis que se ajustan correctamente:

(())) (()())())())()()()()())()()()())()())()())()()()())()()()()()()())())()())())()))()))()))()))())))))))))))((())))))))()()))()()))))))((()))())))))))))(((((()))))))))(()))))))()()(()())))))))))()((((((())))))))()))))))))))))(((()))))))))))))))))))))(((

C_n es el número de diferentes maneras n+ 1 factores pueden ser completamente paréntesis (o el número de formas de asociación n aplicaciones de un operador binario, como en el problema de multiplicación de cadena de matriz). Para n = 3, por ejemplo, tenemos las siguientes cinco paréntesis diferentes de cuatro factores:

(ab)c)d (a(bc)))d (ab)(cd) a(bc)d) a(b(cd)))

Aplicaciones exitosas de un operador binario pueden ser representadas en términos de un árbol binario completo, etiquetando cada hoja a,b,c,d. De ello se desprende que C_n es el número de árboles binarios completos con n+ 1 hojas, o, equivalentemente, con un total de n nodos internos:

La asociación del orden 4 con el C₄=14 árboles binarios llenos con 5 hojas

C_n es el número de árboles no isómorfos ordenados (o plano) con n + 1 vertices. Vea la codificación de árboles generales como árboles binarios.
C_n es el número de caminos monotónicos de celo a lo largo de los bordes de una rejilla con n × n células cuadradas, que no pasan por encima de la diagonal. Un camino monotónico es uno que comienza en la esquina inferior izquierda, termina en la esquina superior derecha, y consiste enteramente en bordes que apuntan hacia la derecha o hacia arriba. Contando estos caminos es equivalente a contar palabras Dyck: X significa "hacer la derecha" y Y significa "salir".

Los siguientes diagramas muestran el caso n = 4:

Esto se puede representar enumerando los elementos catalanes por altura de columna:

El triángulo oscuro es el nodo raíz, los triángulos de luz corresponden a los nodos internos de los árboles binarios, y las barras verdes son las hojas.

[0,0,0] [0,0,1] [0,0,0,2] [0,0,1,1]

[0,1,1,1] [0,0,1,2] [0,0,0,3] [0,1,1,2] [0,0,2,2] [0,0,1,3]

[0,0,2,3] [0,1,1,3] [0,1,2,2] [0,1,2,3]

Un polígono convexo con n+ 2 lados se pueden cortar en triángulos conectando vértices con segmentos de líneas no cruzadas (una forma de triangulación de polígono). El número de triángulos formados es n y el número de diferentes formas de lograrlo C_n. Los siguientes hexágonos ilustran el caso n = 4:

C_n es el número de permutaciones de {1,... n}. Una permutación w se llama surtido de pila si S()w) = (1,...,n), donde S()w) se define recursivamente como sigue: escribir w =Unv Donde n es el elemento más grande en w y u y v son secuencias más cortas, y conjunto S()w)S()u)S()v)n, con S ser 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 la longitud 3); es decir, el número de permutaciones sin subsequencia creciente de tres plazos. 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}. A fortiori, C_n nunca supera los nEl número de Bell. C_n es también el número de particiones no cruzadas del conjunto {1,..., 2n} en que cada bloque es de tamaño 2.
C_n es el número de maneras de inclinar una forma de escalera de altura n con n Rectángulos. Cortar a través de la antidiagonal y mirar sólo los bordes da árboles binarios completos. La siguiente figura ilustra el caso n= 4:

C_n es el número de maneras de formar un "rango de montaje" con n upstrokes y n derriba que todos permanecen por encima de una línea horizontal. La interpretación de la cordillera es que las montañas nunca van por debajo del horizonte.

Gamas de montaña
${displaystyle n=0:}$	*	1 camino
${displaystyle n=1:}$	/	1 camino
${displaystyle n=2:}$	0000000/ //,0/00	2 maneras
${displaystyle n=3:}$	0000000000000000000000000000000000/ 00000000000/0000/000000//0000/00 ///,0/00,0/00/,0/0000,0/0000	5 maneras

C_n es el número de estándar Mesetas jóvenes cuyo diagrama es de 2 por 2n rectángulo. En otras palabras, es el número de maneras los números 1, 2,..., 2n se puede organizar en un 2 porn rectángulo para que cada fila y cada columna aumente. Como tal, la fórmula puede derivarse como un caso especial de la fórmula de la longitud de gancho.

123 124 125 134 135
456 356 346 256 246

$C_{n}$ es el número de longitud $n$ secuencias que comienzan con $1$ , y puede aumentar por ${displaystyle 0}$ o $1$ , o disminución por cualquier número (al menos $1$ ). Para $n=4$ estos son ${displaystyle 1234,1233,1232,1231,1223,1222,1221,1212,1211,1123,1122,1121,1112,1111}$ . Desde un camino Dyck, empieza un contador 0. Una X aumenta el contador por 1 y una Y lo disminuye 1. Grabar los valores en sólo X's. Comparado con la representación similar de los números de Bell, sólo ${displaystyle 1213}$ Está desaparecido.

Prueba de la fórmula

Hay varias formas de explicar por qué la fórmula

C_{n}={frac {1}{n+1}}{2n choose n}

resuelve los problemas combinatorios enumerados anteriormente. La primera prueba a continuación utiliza una función generadora. Las otras pruebas son ejemplos de pruebas biyectivas; implican contar literalmente una colección de algún tipo de objeto para llegar a la fórmula correcta.

Primera prueba

Primero observamos que todos los problemas combinatorios enumerados anteriormente satisfacen la relación de recurrencia de Segner

C_{0}=1quad {text{and}}quad C_{n+1}=sum _{i=0}^{n}C_{i},C_{n-i}quad {text{for }}ngeq 0.

Por ejemplo, cada palabra de Dyck w de longitud ≥ 2 se puede escribir de forma única en la forma

w = Xw₁Yw₂

con palabras de Dyck (posiblemente vacías) w₁ y w₂.

La función generadora de los números catalanes está definida por

c(x)=sum _{n=0}^{infty }C_{n}x^{n}.

La relación de recurrencia dada arriba se puede resumir en forma de función generadora mediante la relación

{displaystyle c(x)=1+xc(x)^{2};}

En otras palabras, esta ecuación se deriva de la relación de recurrencia al expandir ambos lados en series de potencias. Por un lado, la relación de recurrencia determina de manera única los números catalanes; por otro lado, interpretando xc² − c + 1 = 0 como una función cuadrática ecuación de c y usando la fórmula cuadrática, la relación de la función generadora se puede resolver algebraicamente para producir dos posibilidades de solución

{displaystyle c(x)={frac {1+{sqrt {1-4x}}}{2x}}}

{displaystyle c(x)={frac {1-{sqrt {1-4x}}}{2x}}}

De las dos posibilidades, se debe elegir la segunda porque solo la elección de la segunda da

{displaystyle C_{0}=lim _{xto 0}c(x)=1}

El término raíz cuadrada se puede expandir como una serie de potencias usando la serie binomial

{displaystyle {sqrt {1+y}}=sum _{n=0}^{infty }{{frac {1}{2}} choose n}y^{n}=sum _{n=0}^{infty }{frac {(-1)^{n+1}}{4^{n}(2n-1)}}{2n choose n}y^{n}}

como sabemos

{displaystyle {binom {-{frac {1}{2}}}{n}}={frac {(-1)^{n}(2n-1)!!}{2^{n}n!}}={frac {(-1)^{n}(2n)!}{(2^{n}n!)^{2}}}={frac {(-1)^{n}}{4^{n}}}{binom {2n}{n}}}

{displaystyle {binom {frac {1}{2}}{n}}={frac {-1}{2n-1}}{binom {-{frac {1}{2}}}{n}}}

Configurar y = −4x da

{displaystyle {sqrt {1-4x}}=sum _{n=0}^{infty }{frac {-1}{2n-1}}{2n choose n}x^{n}=1-sum _{n=1}^{infty }{frac {1}{2n-1}}{2n choose n}x^{n}}

y sustituyendo esta serie de potencias en la expresión de c(x), la expansión se simplifica a

{displaystyle sum _{n=1}^{infty }{frac {1}{2(2n-1)}}{2n choose n}x^{n-1}}

Vamos ${displaystyle N=n-1}$ Así que

{displaystyle sum _{N=0}^{infty }{frac {1}{2(2N+1)}}{2N+2 choose N+1}x^{N}}

y porque ${displaystyle {frac {1}{2(2N+1)}}{2N+2 choose N+1}=C_{N}}$ (ver prueba de recurrencia)

tenemos

c(x)=sum _{n=0}^{infty }{2n choose n}{frac {x^{n}}{n+1}}.

Segunda prueba

Gráfico 1. La porción inválida del camino (rojo dotado) es volteada (rojo sólido). Caminos malos (después de la vuelta) alcanzar (n- 1,n+ 1) en lugar de (n,n).

Contamos el número de caminos que comienzan y terminan en la diagonal de una n×n Cuadrícula. Todos estos caminos tienen n derecho y derecho n arriba de pasos. Ya que podemos elegir cuál de los 2n pasos arriba o derecha, hay en total ${tbinom {2n}{n}}$ caminos monotónicos de este tipo. A malo el camino cruza la diagonal principal y toca la siguiente diagonal superior (rojo en la ilustración).

La parte de la ruta después de la diagonal superior se voltea sobre esa diagonal, como se ilustra con la línea de puntos roja. Esto cambia todos los pasos correctos por pasos ascendentes y viceversa. En la sección del camino que no se refleja, hay un escalón más hacia arriba que hacia la derecha, por lo tanto, la sección restante del camino incorrecto tiene un paso hacia la derecha más que un paso hacia arriba. Cuando se refleje esta parte del camino, tendrá un paso más arriba que los pasos correctos.

Dado que todavía hay 2n pasos, ahora hay n + 1 pasos hacia arriba y n − 1 pasos correctos. Entonces, en lugar de llegar a (n,n), todos los malos caminos después de la reflexión terminan en (n − 1, n + 1). Debido a que cada ruta monótona en la cuadrícula (n − 1) × (n + 1) se encuentra con la diagonal superior, y debido a que el proceso de reflexión es reversible, la reflexión es, por lo tanto, una biyección entre malos caminos en la grilla original y caminos monótonos en la nueva grilla.

Por lo tanto, el número de malos caminos es:

{n-1+n+1 choose n-1}={2n choose n-1}={2n choose n+1}

y el número de caminos catalanes (es decir, buenos caminos) se obtiene eliminando el número de malos caminos del número total de caminos monótonos de la grilla original,

{displaystyle C_{n}={2n choose n}-{2n choose n+1}={frac {1}{n+1}}{2n choose n}.}

En términos de palabras Dyck, comenzamos con una secuencia (no Dyck) de n X's y n Y's e intercambiamos todas X's y Y's después de la primera Y que viola la condición de Dyck. Después de esta Y, observe que hay exactamente una Y más que X.

Tercera prueba

Esta prueba biyectiva proporciona una explicación natural para el término n + 1 que aparece en el denominador de la fórmula para C_n. Se puede encontrar una versión generalizada de esta prueba en un artículo de Rukavicka Josef (2011).

Gráfico 2. Un camino con excedencia 5.

Dada una ruta monótona, la excedencia de la ruta se define como el número de aristas verticales por encima de la diagonal. Por ejemplo, en la Figura 2, los bordes por encima de la diagonal están marcados en rojo, por lo que la superación de este camino es 5.

Dada una ruta monótona cuya excedencia no es cero, aplicamos el siguiente algoritmo para construir una nueva ruta cuya excedencia es 1 menor que la que comenzamos.

Partiendo de la parte inferior izquierda, siga el camino hasta que viaje primero por encima de la diagonal.
Seguir el camino hasta que siga touches la diagonal otra vez. Denote by X el primer tal borde que se alcanza.
Cierra la porción del camino que ocurre antes X con la porción que ocurre después X.

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

Gráfico 3. Se están intercambiando porciones verdes y rojas.

La superación se ha reducido de 3 a 2. De hecho, el algoritmo hace que la excedencia disminuya en 1 para cualquier camino que lo alimentemos, porque el primer paso vertical que comienza en la diagonal (en el punto marcado con un punto negro) es el único paso vertical. borde que pasa desde arriba de la diagonal hasta debajo de ella después de aplicar el algoritmo; todos los demás bordes verticales permanecen en el mismo lado de la diagonal.

Gráfico 4. Todos los caminos monotónicos en una cuadrícula 3×3, que ilustran el algoritmo de reducción de la superación.

Se puede ver que este proceso es reversible: dado cualquier camino P cuya excedencia sea menor que n, hay exactamente un camino que produce P cuando se le aplica el algoritmo. De hecho, el borde (negro) 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 Alternativamente, invierta el algoritmo original para buscar el primer borde que pasa por debajo de la diagonal.

Esto implica que el número de caminos de la superación n es igual al número de caminos de superación n− 1, que es igual al número de caminos de superación n2, y así sucesivamente, hasta cero. En otras palabras, hemos dividido el conjunto de Todos caminos monotónicos hacia n+ 1 clases de igual tamaño, correspondientes a los posibles excedencias entre 0 y n. Ya que hay ${displaystyle textstyle {2n choose n}}$ caminos monotónicos, obtenemos la fórmula deseada ${displaystyle textstyle C_{n}={frac {1}{n+1}}{2n choose n}.}$

La Figura 4 ilustra la situación para n = 3. Cada uno de los 20 caminos monótonos posibles aparece en algún lugar de la tabla. La primera columna muestra todos los caminos 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.

Usando palabras Dyck, comience con una secuencia desde ${displaystyle textstyle {binom {2n}{n}}}$ . Vamos $X_{d}$ ser el primero $X$ que trae una subsecuencia inicial a la igualdad, y configura la secuencia como ${displaystyle (F)X_{d}(L)}$ . La nueva secuencia es ${displaystyle LXF}$ .

Cuarta prueba

Esta prueba utiliza la definición de triangulación de los números catalanes para establecer una relación entre C_n y C_n+1.

Dado un polígono P con n + 2 lados y una triangulación, marca uno de sus lados como base, y también orienta uno de sus 2n + 1 bordes totales. Hay (4n + 2)C_n tales triangulaciones marcadas para una base dada.

Dado un polígono Q con n + 3 lados y una triangulación (diferente), nuevamente marca uno de sus lados como base. Marque uno de los lados que no sea el lado de la base (y no un borde del triángulo interior). Hay (n + 2)C_{n + 1} tales triangulaciones marcadas para una base dada.

Hay una biyección simple entre estas dos triangulaciones marcadas: Podemos colapsar el triángulo en Q cuyo lado está marcado (de dos maneras, y restar las dos que no pueden colapsar la base), o, al revés, expanda el borde orientado en P a un triángulo y marque su nuevo lado.

Así

{displaystyle (4n+2)C_{n}=(n+2)C_{n+1}}

Escriba ${displaystyle textstyle {frac {4n-2}{n+1}}C_{n-1}=C_{n}.}$

Porque

{displaystyle (2n)!=(2n)!!(2n-1)!!=2^{n}n!(2n-1)!!}

tenemos

{displaystyle {frac {(2n)!}{n!}}=2^{n}(2n-1)!!=(4n-2)!!!!.}

Aplicar la recursión con $C_{0}=1$ da el resultado.

Quinta prueba

Esta prueba se basa en la interpretación de palabras Dyck de los números catalanes, así que $C_{n}$ es el número de maneras de coincidir correctamente $n$ pares de corchetes. Denotamos una cadena (posiblemente vacía) correcta con $c$ y su inverso con $c '$ . Desde cualquier $c$ se puede descomponer ${displaystyle c=(c_{1})c_{2}}$ , resumiendo sobre las longitudes posibles de $c_{1}$ inmediatamente da la definición recursiva

{displaystyle C_{0}=1quad {text{and}}quad C_{n+1}=sum _{i=0}^{n}C_{i},C_{n-i}quad {text{for }}ngeq 0}

Vamos $b$ ser una cuerda equilibrada de longitud $2n$ , es decir. $b$ contiene un número igual de $($ y $)$ Así que ${displaystyle textstyle B_{n}={2n choose n}}$ . Una cuerda equilibrada también se puede descomponer en ${displaystyle (c)b}$ o ${displaystyle)c'(b}$ Así que

{displaystyle B_{n+1}=2sum _{i=0}^{n}B_{i}C_{n-i}.}

Cualquier cadena equilibrada incorrecta (no católica) comienza con ${displaystyle c)}$ , y la cuerda restante tiene una más $($ que $)$ Así que

{displaystyle B_{n+1}-C_{n+1}=sum _{i=0}^{n}{2i+1 choose i}C_{n-i}}

Además, a partir de las definiciones, tenemos:

{displaystyle B_{n+1}-C_{n+1}=2sum _{i=0}^{n}B_{i}C_{n-i}-sum _{i=0}^{n}C_{i},C_{n-i}=sum _{i=0}^{n}(2B_{i}-C_{i})C_{n-i}.}

Por lo tanto, como esto es cierto para todos los $n$ ,

{displaystyle 2B_{i}-C_{i}={binom {2i+1}{i}}}

{displaystyle C_{i}=2B_{i}-{binom {2i+1}{i}}}

{displaystyle C_{i}=2{binom {2i}{i}}-{binom {2i+1}{i}}}

{displaystyle C_{i}={frac {1}{i+1}}{binom {2i}{i}}}

Sexta prueba

Esta prueba se basa en la interpretación de palabras de Dyck de los números catalanes y utiliza el lema del ciclo de Dvoretzky y Motzkin.

Llamamos una secuencia de X's y Y's dominando si, leyendo de izquierda a derecha, el número de X es siempre estrictamente mayor que el número de Y. El lema del ciclo declara que cualquier secuencia $m$ X's and $n$ Y's, dónde $n}" xmlns="http://www.w3.org/1998/Math/MathML">m■n{displaystyle m prendan}n}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/637039c4a193f33fee72ebfeb6cb003593696160" style="vertical-align: -0.338ex; width:6.534ex; height:1.843ex;"/>$ , tiene precisamente $m-n$ dominando turnos circulares. Para ver esto, organizar la secuencia dada de $m+n$ X y Y están en un círculo. Repetidamente eliminando pares XY hojas exactamente $m-n$ X's. Cada uno de estos X's fue el comienzo de un cambio circular dominante antes de que nada fuera eliminado. Por ejemplo, considere ${displaystyle {mathit {XXYXY}}}$ . Esta secuencia es dominante, pero ninguno de sus cambios circulares ${displaystyle {mathit {XYXYX}}}$ , ${displaystyle {mathit {YXYXX}}}$ , ${displaystyle {mathit {XYXXY}}}$ y ${displaystyle {mathit {YXXYX}}}$ Sí.

Una cuerda es una palabra de Dyck $n$ X's and $n$ Y es si y sólo si prepasar una X a la palabra Dyck da una secuencia dominante con $n+1$ X's and $n$ Sí, así podemos contar el primero contando el segundo. En particular, cuando ${displaystyle m=n+1}$ , hay exactamente un cambio circular dominante. Hay ${displaystyle textstyle {2n+1 choose n}}$ secuencias con exactamente $n+1$ X's and $n$ Sí. Para cada uno de estos, sólo uno de los $2n+1$ Los cambios circulares están dominando. Por lo tanto hay ${displaystyle textstyle {frac {1}{2n+1}}{2n+1 choose n}=C_{n}}$ secuencias distintas de $n+1$ X's and $n$ Y's que están dominando, cada uno de los cuales corresponde a exactamente una palabra Dyck.

Matriz de Hankel

La matriz de Hankel n×n cuya entrada (i, j) es el número catalán C_i+j−2 tiene determinante 1, independientemente del valor de n. Por ejemplo, para n = 4 tenemos

det {begin{bmatrix}1&1&2&5\1&2&5&14\2&5&14&42\5&14&42&132end{bmatrix}}=1.

Además, si la indexación está "desplazada" para que la entrada (i, j) se rellene con el número catalán C_i+j−1 entonces el determinante sigue siendo 1, independientemente del valor de n. Por ejemplo, para n = 4 tenemos

det {begin{bmatrix}1&2&5&14\2&5&14&42\5&14&42&132\14&42&132&429end{bmatrix}}=1.

Tomadas en conjunto, estas dos condiciones definen de manera única los números catalanes.

Otra característica exclusiva de la matriz catalana-Hankel es que el determinante de la submatriz n×n que comienza en 2 tiene un determinante n + 1.

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

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

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

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

etcétera.

Historia

Números catalanes en el libro de Mingantu El método rápido para obtener la proporción exacta de división de un círculo volumen III

La secuencia catalana fue descrita en el siglo XVIII por Leonhard Euler, quien estaba interesado en la cantidad de formas diferentes de dividir un polígono en triángulos. La secuencia lleva el 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 de reflejos (segunda prueba) para las palabras de Dyck fue encontrado por Désiré André en 1887.

El nombre "números catalanes" se originó en John Riordan.

En 1988, salió a la luz que la secuencia numérica catalana había sido utilizada en China por el matemático mongol Mingantu en 1730. Fue entonces cuando comenzó a escribir su libro Ge Yuan Mi Lu Jie Fa [El método rápido para obtener la proporció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. 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, Ming utilizó la secuencia catalana para expresar expansiones de series de ${displaystyle sin(2alpha)}$ y ${displaystyle sin(4alpha)}$ en términos de $sin(alpha)$ .

Generalizaciones

Los números catalanes pueden ser interpretados como un caso especial del teorema de voto de Bertrand. Específicamente, $C_{n}$ es el número de maneras para un candidato A con n+1 votos contra el candidato B con n votos.

La secuencia de dos parámetros de enteros no negativos ${frac {(2m)!(2n)!}{(m+n)!m!n!}}$ es una generalización de los números catalanes. Estos son nombrados números super-CatalanPor Ira Gessel. Estos no deben confundirse con los números Schröder-Hipparchus, que a veces también se llaman números super-Catalan.

Para $m=1$ , esto es sólo dos veces el número ordinario catalán, y para $m=n$ , los números tienen una descripción combinatoria fácil. Sin embargo, otras descripciones combinatoriales sólo se conocen para ${displaystyle m=2,3}$ y $4$ , y es un problema abierto encontrar una interpretación combinatoria general.

Sergey Fomin y Nathan Reading han dado un número catalan generalizado asociado a cualquier grupo de Coxeter cristalino finito, a saber, el número de elementos totalmente comunicativos del grupo; en términos del sistema raíz asociado, es el número de anti-chains (o ideales de orden) en la posición de raíces positivas. El número clásico catalán $C_{n}$ corresponde al sistema raíz de tipo $A_{n}$ . La relación clásica de recurrencia generaliza: el número catalán de un diagrama de Coxeter es igual a la suma de los números catalanes de todos sus subdiagramas óptimos.

Los números catalanes son una solución de una versión del problema del momento de Hausdorff.

Convolución plegada en k catalana

La convolución catalana k-fold es:

{displaystyle sum _{i_{1}+cdots +i_{m}=n atop i_{1},ldotsi_{m}geq 0}C_{i_{1}}cdots C_{i_{m}}={begin{cases}{dfrac {m(n+1)(n+2)cdots (n+m/2-1)}{2(n+m/2+2)(n+m/2+3)cdots (n+m)}}C_{n+m/2},&m{text{ even,}}\[5pt]{dfrac {m(n+1)(n+2)cdots (n+(m-1)/2)}{(n+(m+3)/2)(n+(m+3)/2+1)cdots (n+m)}}C_{n+(m-1)/2},&m{text{ odd.}}end{cases}}}

Contenido relacionado

Más resultados...