Каталанови бројеви представљају низ природних бројева значајних у комбинаторици. Првих неколико Каталанових бројева је: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190.. Названи су у част белгијскога математичара Ежена Шарла Каталана.

Могу се дефинисати преко биномних коефицијената:

${\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 {\mbox{ za }}n\geq 0.}$

Алтернативан израз је:

${\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}\quad {\text{ za }}n\geq 0,}$

Каталанови бројеви задовољавају рекурзију:

${\displaystyle C_{0}=1,C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}}$ за ${\displaystyle n\geq 0}$

Пошто је ${\displaystyle {\tbinom {2n}{n}}=\sum _{i=0}^{n}{\tbinom {n}{i}}^{2},}$ онда је:

${\displaystyle C_{n}={\frac {1}{n+1}}\sum _{i=0}^{n}{n \choose i}^{2}.}$.

Задовољавају и следећу рекурзију:

${\displaystyle C_{0}=1,C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},}$

Генерирајућа функција Каталанових бројева је:

${\displaystyle \sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.}$

Асимптотска вредност је:

${\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}.}$

Постоје многи проблеми у комбинаторици, чије решење су управо Каталанови бројеви. Нпр. конвексни полигон са n + 2 стране да се расећи управо на ${\displaystyle C_{n}}$ троуглова. На слици је приказан пример за случај n = 4:

Потпуно бинарно стабло, где сваки вертекс има или двоје деце или је без деце, може да представља пример за Каталанове бројеве. Каталанови број ${\displaystyle C_{n}}$ је број потпуних бинарних стабала са n + 1 листом.

• Каталанови бројеви
• -author=Koshy, Thomas -