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

Низ природних бројева значајних у комбинаторици

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

ДефиницијаУреди

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

 

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

 

РекурзијаУреди

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

  за  

Пошто је   онда је:

 .

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

 

СвојстваУреди

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

 

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

 

КомбинаторикаУреди

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

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

ЛитератураУреди