Fundo : Números catalães são definidos usando a fórmula abaixo: Os números catalães também podem ser definidos usando a seguinte fórmula recursiva. Os primeiros poucos números catalães para n = 0, 1, 2, 3, ... são 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

Consulte isto para a implementação do enésimo número catalão.

Formulários :

1. Número de árvores de pesquisa binárias possíveis com n chaves .
2. Número de expressões contendo n pares de parênteses que são correspondidos corretamente. Para n = 3, as expressões possíveis são ((())),() (()),()()(), (())(), (()()).
3. Número de maneiras pelas quais um polígono convexo de n + 2 lados pode se dividir em triângulos conectando vértices.
   
4. Número de árvores binárias completas (uma árvore binária com raiz é cheia se cada vértice tiver dois filhos ou nenhum filho) com n + 1 folhas.
5. O número de diferentes árvores binárias não rotuladas pode estar presente com n nós .
6. O número de caminhos com 2n etapas em uma grade retangular da parte inferior esquerda, ou seja, (n-1, 0) até a parte superior direita (0, n-1) que não se cruzam acima da diagonal principal.
   
7. Número de maneiras de inserir n pares de parênteses em uma palavra de n + 1 letras, por exemplo, para n = 2, há 2 maneiras: ((ab) c) ou (a (bc)). Para n = 3, existem 5 maneiras, ((ab) (cd)), (((ab) c) d), ((a (bc)) d), (a ((bc) d)), (a (b (cd))).
8. Número de partições não cruzadas do conjunto {1,…, 2n} em que cada bloco é de tamanho 2. Uma partição é não cruzada se e somente se em seu diagrama planar, os blocos são disjuntos (ou seja, não se cruzam). Por exemplo, abaixo de dois estão partições cruzadas e não cruzadas de {1, 2, 3, 4, 5, 6, 7, 8, 9}. A partição {{1, 5, 7}, {2, 3, 8}, {4, 6}, {9}} é cruzada e partição {{1, 5, 7}, {2, 3}, {4 }, {6}, {8, 9}} é sem cruzamento.
   
9. Número de palavras Dyck de comprimento 2n. Uma palavra Dyck é uma string que consiste em n X's e n Y's, de forma que nenhum segmento inicial da string tenha mais Y's do que X's. Por exemplo, a seguir estão as palavras Dyck de comprimento 6: <big>XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.</big>
10. Número de maneiras de colocar lado a lado uma forma de escada de altura n com n retângulos. A figura a seguir ilustra o caso n = 4:
    
11. Número de maneiras de conectar os pontos em acordes disjuntos de um círculo. Isso é semelhante ao ponto 3 acima.
12. Número de maneiras de formar uma “cadeia de montanhas” com n movimentos para cima e n para baixo, que ficam todos acima da linha original. A interpretação da cadeia de montanhas é que as montanhas nunca irão abaixo do horizonte.
13. Número de permutações classificáveis ​​em pilha de {1,…, n}. Uma permutação w é chamada de classificação em pilha se S (w) = (1, ..., n), onde S (w) é definido recursivamente da seguinte forma: escreva w = unv onde n é o maior elemento em w e u e v são sequências mais curtas e conjunto S (w) = S (u) S (v) n, com S sendo a identidade para sequências de um elemento.
14. Número de permutações de {1,…, n} que evitam o padrão 123 (ou qualquer um dos outros padrões de comprimento 3); isto é, o número de permutações sem subsequência crescente de três termos. Para n = 3, essas permutações são 132, 213, 231, 312 e 321. Para n = 4, são 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 e 4321

Fontes:

1. https://en.wikipedia.org/wiki/Catalan_number
2. http://mathworld.wolfram.com/CatalanNumber.html
3. http://www-groups.dcs.st-and.ac.uk/history/Misc Miscellaneous/CatalanNumbers/catalan.html
4. http://www.mhhe.com/math/advmath/rosen/r5/instructor/applications/ch07.pdf
5. https://oeis.org/A000108

Este artigo é uma contribuição de Akash Srivastava . Se você gosta de GeeksforGeeks e gostaria de contribuir, você também pode escrever um artigo e enviá-lo para contrib@geeksforgeeks.org. Veja o seu artigo na página principal do GeeksforGeeks e ajude outros Geeks.

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima