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

Из Википедије, слободне енциклопедије

Каталанови бројеви представљају низ природних бројева значајних у комбинаторици. Првих неколико Каталанових бројева је: 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}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{ za }n\ge 0.

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

C_n = {2n\choose n} - {2n\choose n+1} \quad\text{ za }n\ge 0,

Рекурзија[уреди]

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

C_0 = 1 , C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i} за n\ge 0

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

C_n= \frac 1{n+1} \sum_{i=0}^n {n \choose i}^2..

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

C_0 = 1 , C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

Својства[уреди]

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

\sum_{n=0}^{\infty} C_n z^n = \frac{1-\sqrt{1-4 z}}{2 z}.

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

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

Комбинаторика[уреди]

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

Catalan-Hexagons-example.svg

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

Catalan number binary tree example.png

Литература[уреди]