Числа Каталана: комбінаторні інтерпретації та їх узагальнення

Abstract

Магістерська робота присвячена дослідженню чисел Каталана – однієї з найвідоміших послідовностей у дискретній математиці, яка має понад двісті різних комбінаторних інтерпретацій та численні узагальнення. У першому розділі розглянуто теоретичні основи: класичне означення, аналітичні вирази, рекурентні співвідношення та основні властивості чисел Каталана. Наведено приклади та проаналізовано їхній зв’язок з іншими відомими послідовностями (Фібоначчі, Нарайяни, Мотцкіна, Белла, Шредера). Другий розділ присвячений комбінаторним інтерпретаціям: правильним дужковим виразам, Dyck-шляхам, бінарним деревам, тріангуляціям багатокутників, некросинговим паруванням. Ілюстрації та приклади показують універсальність чисел Каталана як моделі для рекурсивних структур. У третьому розділі досліджено узагальнення: числа Фусса–Каталана, k −узагальнення, q − та (q,t) −аналоги, багатовимірні й матричні узагальнення, а також їхні алгебраїчні й топологічні інтерпретації (кластерні алгебри, асоціаедри, гомології вузлів). Побудовано порівняльні таблиці та графіки росту.Четвертий розділ присвячено застосуванням чисел Каталана: у теорії алгоритмів, комп’ютерній геометрії, інформатиці, біоінформатиці (моделі вторинних структур РНК), теорії вузлів і сучасних міждисциплінарних дослідженнях (випадкові матриці, квантові обчислення, штучний інтелект). Результати дослідження підтверджують, що числа Каталана є не лише класичним об’єктом комбінаторики, а й універсальним інструментом для аналізу рекурсивних структур, що знаходить широке застосування у сучасній науці та технологіях.