Каталанови бројеви
Каталанови бројеви представљају низ природних бројева значајних у комбинаторици. Првих неколико Каталанових бројева је: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190.. Названи су у част белгијскога математичара Ежена Шарла Каталана.
Дефиниција
[уреди | уреди извор]Могу се дефинисати преко биномних коефицијената:
Алтернативан израз је:
Рекурзија
[уреди | уреди извор]Каталанови бројеви задовољавају рекурзију:
- за
Пошто је онда је:
- .
Задовољавају и следећу рекурзију:
Својства
[уреди | уреди извор]Генерирајућа функција Каталанових бројева је:
Асимптотска вредност је:
Комбинаторика
[уреди | уреди извор]Постоје многи проблеми у комбинаторици, чије решење су управо Каталанови бројеви. Нпр. конвексни полигон са n + 2 стране да се расећи управо на троуглова. На слици је приказан пример за случај n = 4:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Catalan-Hexagons-example.svg/400px-Catalan-Hexagons-example.svg.png)
Потпуно бинарно стабло, где сваки вертекс има или двоје деце или је без деце, може да представља пример за Каталанове бројеве. Каталанови број је број потпуних бинарних стабала са n + 1 листом.
![](http://upload.wikimedia.org/wikipedia/commons/0/01/Catalan_number_binary_tree_example.png)
Литература
[уреди | уреди извор]- Каталанови бројеви
- Koshy, Thomas , Catalan Numbers with Applications. . Oxford University Press. 2008. ISBN 978-0-19-533454-8.