Каталанови бројеви

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

Дефиниција

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

$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}=\prod _{k=2}^n\frac{n+k}{k}\text{ za }n\ge 0.$

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

$C_n=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n+1})\text{ za }n\ge 0,$

Рекурзија

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

$C_0=1,C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}$ за $n\ge 0$

Пошто је $(\genfrac{}{}{0ex}{}{2n}{n})=\sum _{i=0}^n{(\genfrac{}{}{0ex}{}{n}{i})}^2,$ онда је:

$C_n=\frac{1}{n+1}\sum _{i=0}^n{(\genfrac{}{}{0ex}{}{n}{i})}^2.$.

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

$C_0=1,C_{n+1}=\frac{2(2n+1)}{n+2}{C}_n,$

Својства

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

$\sum _{n=0}^{\mathrm{\infty }}{C}_n{z}^n=\frac{1-\sqrt{1-4z}}{2z}.$

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

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

Комбинаторика

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

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

Литература

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