Números de Catalan

Em combinatória os números de Catalan formam uma sequência de números naturais que ocorrem em vários problemas de contagem, frequentemente envolvendo objetos definidos recursivamente. Apesar do nome ser uma referência ao matemático belga Eugène Charles Catalan (1814–1894), na verdade eles foram descoberto por um astrônomo chinês chamado Minggatu (1692– 1763) mais de um século antes.

O n-ésimo número de Catalan é dado em termos de coeficientes binomiais por:

$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\mbox{ para }}n\geq 0.$

Os primeiros números de Catalan para n = 0, 1, 2, 3, … são:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …