Calculadora de Números de Catalan
Calcule números de Catalan e explore as estruturas que eles contam: árvores, triangulações, parênteses e caminhos em reticulado.
Os resultados são calculados automaticamente conforme você informa os dados.
Visualização
Decomposição recursiva
Tabela da sequência
▼ Veja explicações e dicas abaixo ▼
Calculadoras relacionadas
O que são números de Catalan?
Os números de Catalan formam uma sequência de números inteiros que conta muitos tipos diferentes de estruturas ordenadas, sem cruzamentos ou bem equilibradas. A sequência começa assim:
$$
1,\ 1,\ 2,\ 5,\ 14,\ 42,\ 132,\ 429,\ \ldots
$$
O número de Catalan de índice \(n\) geralmente é escrito como \(C_n\) ou \(C(n)\). O índice \(n\) é um número inteiro não negativo: \(0, 1, 2, 3, \ldots\). Embora a sequência seja apenas uma lista de números, ela aparece em muitos problemas de contagem que, à primeira vista, parecem diferentes.
Por exemplo, o mesmo valor \(C_n\) pode contar:
- sequências válidas formadas por \(n\) pares de parênteses,
- caminhos em uma rede com \(n\) passos para o norte e \(n\) passos para o leste que permanecem de um lado da diagonal,
- triangulações de um polígono convexo com \(n+2\) lados,
- cordilheiras com \(n\) passos ascendentes e \(n\) passos descendentes que nunca ficam abaixo da linha de base.
É isso que torna os números de Catalan úteis na combinatória. Eles mostram que vários problemas visualmente diferentes compartilham a mesma estrutura subjacente.
Por que os números de Catalan são importantes
Os números de Catalan são um exemplo clássico de como os matemáticos contam possibilidades estruturadas sem listar cada possibilidade uma por uma. Eles são especialmente úteis em matemática discreta, combinatória, ciência da computação e projeto de algoritmos, pois contam objetos construídos a partir de escolhas aninhadas ou recursivas.
Uma sequência de parênteses é um exemplo simples. Com \(3\) pares de parênteses, há apenas \(5\) arranjos válidos. Com \(8\) pares, há \(1430\). A contagem cresce rapidamente, então uma fórmula ou recorrência é muito mais útil do que fazer uma lista manual.
Os números de Catalan também ajudam os estudantes a conectar várias ideias importantes: coeficientes binomiais, recursão, bijeções, caminhos em uma rede, sequências equilibradas, triangulações de polígonos e funções geradoras. Entender uma interpretação dos números de Catalan geralmente facilita o aprendizado das outras.
Termos importantes
- Número de Catalan: um número da sequência \(C_0, C_1, C_2, \ldots\) que conta muitas estruturas combinatórias padronizadas.
- Índice \(n\): o número inteiro não negativo que seleciona qual número de Catalan calcular.
- Coeficiente binomial: o número \(\binom{m}{r}\), lido como “\(m\) escolhido \(r\)”, que conta as maneiras de escolher \(r\) itens de um conjunto com \(m\) itens.
- Coeficiente binomial central: o coeficiente \(\binom{2n}{n}\), que aparece na forma fechada de \(C_n\).
- Relação de recorrência: uma regra que define um valor usando valores anteriores da mesma sequência.
- Parênteses equilibrados: uma sequência em que cada parêntese de abertura é corretamente associado a um parêntese de fechamento posterior.
- Caminho de Dyck: um caminho formado por passos equilibrados para cima/baixo ou para o norte/leste que nunca cruza abaixo — ou acima, dependendo da convenção — do limite permitido.
- Triangulação: uma maneira de dividir um polígono em triângulos usando diagonais que não se cruzam.
Como funcionam os números de Catalan
A forma fechada mais comum para o número de Catalan de índice \(n\) é:
$$
C_n = \frac{1}{n+1}\binom{2n}{n}
$$
A mesma fórmula também pode ser escrita com fatoriais:
$$
C_n = \frac{(2n)!}{n!(n+1)!}
$$
Em que:
- \(n\) é um número inteiro não negativo,
- \(C_n\) é o número de Catalan de índice \(n\),
- \(\binom{2n}{n}\) é o coeficiente binomial central,
- \(n!\) significa o produto \(n \times (n-1) \times \cdots \times 1\), com \(0! = 1\).
Uma maneira útil de entender essa fórmula é pensar em caminhos. Há \(\binom{2n}{n}\) maneiras de organizar \(n\) passos de um tipo e \(n\) passos de outro tipo. Os números de Catalan contam apenas os arranjos que permanecem dentro do limite exigido, como caminhos que não cruzam a diagonal ou sequências de parênteses que nunca fecham mais parênteses do que abriram.
Os números de Catalan também obedecem a uma recorrência:
$$
C_0 = 1
$$
$$
C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}\quad \text{for } n \ge 1
$$
Essa recorrência diz que uma estrutura de Catalan de tamanho \(n\) muitas vezes pode ser dividida em uma parte esquerda de tamanho \(k\) e uma parte direita de tamanho \(n-1-k\). Para cada divisão, multiplique o número de escolhas da parte esquerda pelo número de escolhas da parte direita e depois some todas as divisões possíveis.
Por exemplo, para \(n=4\):
$$
C_4 = C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0
$$
Usando \(C_0=1\), \(C_1=1\), \(C_2=2\) e \(C_3=5\):
$$
C_4 = 1\times5 + 1\times2 + 2\times1 + 5\times1 = 14
$$
A forma fechada é eficiente para obter a contagem exata. A recorrência ajuda a entender por que a mesma sequência aparece em estruturas recursivas, como sequências de parênteses válidas, árvores binárias e triangulações de polígonos.
Exemplos práticos de números de Catalan
Exemplo 1: parênteses válidos com 3 pares
Suponha que \(n=3\). A forma fechada fornece:
$$
C_3 = \frac{1}{3+1}\binom{6}{3}
$$
$$
C_3 = \frac{1}{4}\times 20 = 5
$$
Portanto, há \(5\) sequências válidas formadas por \(3\) pares de parênteses:
-
((())) -
(()()) -
(())() -
()(()) -
()()()
Cada sequência é equilibrada, pois todo parêntese de fechamento tem um parêntese de abertura correspondente anterior.
Exemplo 2: triangulação de um polígono
Na interpretação de triangulação, \(C_n\) conta as triangulações de um polígono convexo com \(n+2\) lados. Se \(n=4\), o polígono tem:
$$
n+2 = 4+2 = 6
$$
Assim, \(C_4\) conta as triangulações de um hexágono convexo:
$$
C_4 = \frac{1}{5}\binom{8}{4}
$$
$$
C_4 = \frac{70}{5} = 14
$$
Há \(14\) maneiras de dividir um hexágono convexo em triângulos usando diagonais que não se cruzam.
Exemplo 3: o caso vazio \(n=0\)
Os números de Catalan começam com \(C_0=1\). A forma fechada confirma esse resultado:
$$
C_0 = \frac{1}{0+1}\binom{0}{0} = 1
$$
Isso pode parecer surpreendente no início, porque não há “nada” para organizar. Na combinatória, a estrutura vazia costuma ser contada como uma estrutura válida. Para os números de Catalan, \(C_0=1\) também faz a recorrência funcionar de maneira consistente, pois estruturas maiores podem ser construídas a partir de partes vazias e não vazias menores.
Como interpretar o resultado
O resultado \(C(n)\) é o número exato de estruturas contadas pelos números de Catalan para o índice normalizado \(n\). Trata-se de uma contagem, não de uma medida, portanto não tem unidade física.
Um resultado pequeno geralmente significa que as estruturas podem ser listadas e verificadas manualmente. Por exemplo, \(C_3=5\) é fácil de exibir como sequências de parênteses ou caminhos. Um resultado grande significa que há muitas estruturas possíveis, e a contagem exata é mais útil do que uma lista completa.
Mudar a interpretação altera a forma como as estruturas são exibidas, mas não muda o próprio número de Catalan. Para o mesmo \(n\), parênteses válidos, caminhos que não cruzam a diagonal, triangulações de um \((n+2)\)-gono e cordilheiras têm a mesma contagem \(C_n\).
A decomposição da recorrência mostra de onde vem a contagem. Cada linha representa uma divisão da estrutura em duas partes menores de Catalan. A contribuição de uma divisão é o produto das duas contagens menores, e o número de Catalan completo é a soma de todas essas contribuições.
Os exemplos gerados são amostras controladas pela interpretação selecionada e pelo limite de exemplos. Quando a contagem exata é maior que o número de exemplos exibidos, a lista de exemplos não é completa.
Erros e equívocos comuns
Um erro comum é pensar que a interpretação selecionada altera a resposta numérica. Não altera. A interpretação muda os exemplos e a visualização, enquanto o valor \(C_n\) permanece igual para o mesmo índice \(n\).
Outro erro é confundir \(n\) com o número de lados do polígono no modelo de triangulação. A interpretação de triangulação usa um \((n+2)\)-gono. Por exemplo, \(n=4\) corresponde a um hexágono, não a um quadrilátero.
Também é fácil supor que uma lista de exemplos exibida contenha todas as estruturas possíveis. Isso só é verdade quando a contagem exata não é maior que o limite de exemplos selecionado e a geração de exemplos não está limitada.
Decimais e valores negativos não são casos separados de números de Catalan nesta calculadora. Os números de Catalan são indexados por inteiros não negativos. As entradas decimais são arredondadas para um inteiro, e as entradas negativas são normalizadas para \(0\).
Por fim, \(C_0=1\) não deve ser interpretado como a existência de um objeto visível para desenhar. Isso significa que existe uma estrutura vazia, que é o caso-base padrão da sequência.
Quando usar números de Catalan
Use os números de Catalan quando um problema envolver a contagem de objetos estruturados que precisam permanecer equilibrados, aninhados, ordenados ou sem cruzamentos.
Os usos comuns incluem:
- contar sequências válidas de parênteses com \(n\) pares,
- contar caminhos que permanecem do lado permitido de uma diagonal ou linha de base,
- contar triangulações de um polígono convexo,
- estudar estruturas recursivas em matemática discreta,
- comparar modelos combinatórios diferentes que acabam tendo a mesma contagem.
Os números de Catalan são especialmente úteis quando listar todos os arranjos possíveis seria demorado ou sujeito a erros.
Limitações e pontos importantes
Os números de Catalan se aplicam a índices inteiros não negativos. Em geral, eles não descrevem índices negativos, fracionários ou simbólicos nas interpretações elementares de contagem usadas aqui.
Esta calculadora normaliza as entradas antes de calcular. O índice \(n\) é arredondado para o inteiro mais próximo e limitado ao intervalo de \(0\) a \(100\). O limite de exemplos é arredondado para o inteiro mais próximo e limitado ao intervalo de \(1\) a \(40\).
A contagem exata de Catalan é exibida como um número inteiro. A contagem não é arredondada, abreviada nem estimada. Valores muito grandes podem ser extensos, pois os números de Catalan crescem rapidamente.
Os exemplos e as visualizações são mais limitados que a contagem exata. Para manter a interface responsiva, os exemplos gerados e as visualizações são limitados a \(n=30\). Quando \(n\) é maior que \(30\), a contagem exata ainda reflete o índice informado após a normalização, mas os exemplos e a saída visual podem ser limitados ou ficar indisponíveis.
A visualização não está disponível para todos os casos. A interpretação com parênteses é baseada em texto, \(n=0\) não tem uma estrutura não vazia visível para desenhar, e o download do gráfico depende do suporte do navegador à preparação do arquivo de imagem.
Como usar esta calculadora
- Informe o índice de Catalan \(n\).
- Escolha uma interpretação: parênteses válidos, caminhos em uma rede, triangulações ou cordilheiras.
- Informe o número máximo de exemplos a gerar, de \(1\) a \(40\).
- Confira o resultado exato \(C(n)\) e os cartões de métricas.
- Use os cartões de fórmulas, a decomposição da recorrência e a tabela da sequência para entender como o resultado se encaixa na sequência de Catalan.
- Selecione um exemplo gerado para atualizar a visualização quando houver um modo visual disponível.
- Use a opção de download do gráfico para salvar a visualização exibida como PNG quando disponível.
Perguntas frequentes
Qual é o primeiro número de Catalan?
A sequência começa com \(C_0=1\). Isso representa a estrutura vazia e serve como caso-base da recorrência. Os valores seguintes são \(C_1=1\), \(C_2=2\), \(C_3=5\) e \(C_4=14\).
Por que parênteses, caminhos, polígonos e cordilheiras têm a mesma contagem?
Esses modelos podem ser relacionados por correspondências que preservam a estrutura. Por exemplo, um parêntese de abertura pode ser tratado como um passo para cima ou para o norte, enquanto um parêntese de fechamento pode ser tratado como um passo para baixo ou para o leste. A regra de que os parênteses permanecem equilibrados torna-se a regra de que o caminho permanece dentro do limite permitido.
\(C_n\) conta todos os caminhos de um canto de uma grade até outro?
Não. O coeficiente binomial central \(\binom{2n}{n}\) conta todos os arranjos de \(n\) passos de cada tipo. O número de Catalan conta apenas os caminhos válidos que permanecem do lado exigido da diagonal ou da linha de base.
Por que a recorrência multiplica números de Catalan menores?
Para uma divisão fixa, a parte esquerda e a parte direita podem ser escolhidas de forma independente. Se a parte esquerda tiver \(C_k\) possibilidades e a parte direita tiver \(C_{n-1-k}\) possibilidades, essa divisão contribuirá com \(C_kC_{n-1-k}\) estruturas. Somar todas as divisões resulta em \(C_n\).
Por que os exemplos e as visualizações têm um limite?
Os números de Catalan crescem rapidamente, então gerar e desenhar todas as estruturas pode ficar caro mesmo quando a contagem exata é fácil de exibir. O limite mantém a interface responsiva e ainda mostra o número de Catalan exato para os índices compatíveis.
Fontes e referências
Livros
- Richard P. Stanley. Catalan Numbers. Cambridge University Press, 2015. Propriedades introdutórias e catálogo de estruturas contadas pelos números de Catalan. ISBNs 9781107075092, 9781107427747; DOI: https://doi.org/10.1017/CBO9781139871495.
- Thomas Koshy. Catalan Numbers with Applications. Oxford University Press, 2009. Capítulo 5, “Catalan Numbers”, pp. 103–148. ISBN 9780195334548; DOI do capítulo: https://doi.org/10.1093/acprof:oso/9780195334548.003.0005.
- Steven Roman. An Introduction to Catalan Numbers. Compact Textbooks in Mathematics, Birkhäuser Cham/Springer, 2015. Capítulos “Dyck Words”, “The Catalan Numbers” e “Catalan Numbers and Paths”, pp. 7–22. DOI: https://doi.org/10.1007/978-3-319-22144-1.
Fontes online e educacionais
- Richard Grassl e Oscar Levin. “The Catalan Numbers”. More Discrete Mathematics via Graph Theory, Open Math Books, acesso em 27 de junho de 2026. https://discrete.openmathbooks.org/more/mdm/sec_basic-catalan.html
- OEIS Foundation. “A000108 — Catalan Numbers”. The On-Line Encyclopedia of Integer Sequences, acesso em 27 de junho de 2026. https://oeis.org/A000108
- Eric W. Weisstein. “Catalan Number”. Wolfram MathWorld, acesso em 27 de junho de 2026. https://mathworld.wolfram.com/CatalanNumber.html