Aplicaciones de los Números Catalanes

Fondo :
números catalanes
se definen usando la siguiente fórmula:
$C_{n} = (2n)!/(n+1)!n! = \prod^{n}_{k=2} \frac{n+k}{k} for_ n >= 0$
Los números catalanes también se pueden definir usando la siguiente fórmula recursiva.
$C_{0} = 1 C_{n+1} = \sum ^{n} _{i=0} C_{i}C_{n-i} for_ n>=0$
Los primeros números catalanes para n = 0, 1, 2, 3, … son
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

Consulte esto para la implementación del número catalán n.

Aplicaciones:

Número de árboles binarios de búsqueda posibles con n claves .
Número de expresiones que contienen n pares de paréntesis que coinciden correctamente. Para n = 3, las expresiones posibles son ((())),()(()),()()(), (())(), (()()).
Número de formas en que un polígono convexo de n+2 lados puede dividirse en triángulos conectando vértices.
Número de árboles binarios completos (un árbol binario enraizado está lleno si cada vértice tiene dos hijos o ningún hijo) con n+1 hojas.
Puede haber una cantidad de árboles binarios sin etiqueta diferentes con n Nodes .
El número de caminos con 2n pasos en una cuadrícula rectangular desde la parte inferior izquierda, es decir, (n-1, 0) hasta la parte superior derecha (0, n-1) que no se cruzan por encima de la diagonal principal.
Número de formas de insertar n pares de paréntesis en una palabra de n+1 letras, por ejemplo, para n=2 hay 2 formas: ((ab)c) o (a(bc)). Para n=3 hay 5 formas, ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a (b(cd))).
Número de particiones no cruzadas del conjunto {1, …, 2n} en las que cada bloque es de tamaño 2. Una partición no se cruza si y sólo si en su diagrama plano, los bloques son disjuntos (es decir, no se cruzan). Por ejemplo, debajo de dos hay particiones cruzadas y no cruzadas de {1, 2, 3, 4, 5, 6, 7, 8, 9}. La partición {{1, 5, 7}, {2, 3, 8}, {4, 6}, {9}} se cruza y la partición {{1, 5, 7}, {2, 3}, {4 }, {6}, {8, 9}} no se cruza.
Número de palabras Dyck de longitud 2n. Una palabra de Dyck es una string que consta de n X y n Y, de modo que ningún segmento inicial de la string tiene más Y que X. Por ejemplo, las siguientes son las palabras de Dyck de longitud 6: XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.
Número de formas de enlosar una forma de escalón de altura n con n rectángulos. La siguiente figura ilustra el caso n = 4:
Número de formas de unir los puntos de un círculo con cuerdas disjuntas. Esto es similar al punto 3 anterior.
Número de formas de formar una «string montañosa» con n trazos ascendentes y n descendentes que permanecen por encima de la línea original. La interpretación de la cordillera es que las montañas nunca se irán por debajo del horizonte.
Número de permutaciones clasificables por pila de {1, …, n}. Una permutación w se denomina stack-sortable si S(w) = (1, …, n), donde S(w) se define recursivamente de la siguiente manera: escriba 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.
Número de permutaciones de {1, …, n} que evitan el patrón 123 (o cualquiera de los otros patrones de longitud 3); es decir, el número de permutaciones sin 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

Fuentes:

Este artículo es una contribución de Akash Srivastava . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta