🔢 Числа Каталана

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

Оновлено: 5 липня 2026 р.

Усі 5 об'єктів для n = 3
Послідовність Каталана C₀ … Cₙ
Один лік, багато форм. Збалансовані дужки, шляхи Дика, бінарні дерева, тріангуляції многокутника та діаграми неперетинних хорд перелічуються одним і тим самим числом Cₙ, бо між ними існують бієкції. «(» — це крок вгору і ліве піддерево; «)» — крок вниз і праве піддерево. Тріангуляція (n+2)-кутника через вибір трикутника на фіксованому ребрі розбиває його так само, як і рекурентна формула Cₙ₊₁ = Σ Cᵢ·Cₙ₋ᵢ. Тож, розв'язавши одну задачу, ви розв'язуєте всі п'ять.

Про числа Каталана

Числа Каталана C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, … — одна з найпоширеніших послідовностей у комбінаториці, що виникає в десятках, здавалося б, не пов'язаних задач підрахунку. Формула Cₙ = (2n)! / ((n+1)! n!) досліджувалась Ейлером, Зегнером і Каталаном у XVIII–XIX ст. Ключовий висновок, доведений існуванням явних бієкцій (взаємно-однозначних відповідностей): рядки збалансованих дужок, шляхи Дика, повні бінарні дерева, трикутуляції опуклого многокутника та некросингові акордові діаграми — всі рахуються одним і тим самим числом Cₙ, тому розв'язання будь-якої однієї задачі автоматично розв'язує всі інші.

Симуляція дозволяє досліджувати всі п'ять бієкцій одночасно для n від 0 до 8. Режим «Показати всі» відображає кожен Cₙ-об'єкт одразу; режим «Вибірка» анімує випадковий прохід по множині. Стовпчиковий графік нижче показує послідовність Каталана C₀ … Cₙ, що зростає експоненційно (Cₙ ~ 4ⁿ / (n^(3/2) √π)), а панель формули оновлюється і показує відношення C_(n+1)/Cₙ, що наближається до 4.

Часті запитання

Що таке числа Каталана?

Cₙ — це кількість способів виконати комбінаторну задачу, що має певну рекурсивну структуру, а саме: задачу, яку можна розбити на дві незалежні підзадачі розмірів 0 і n–1, або 1 і n–2, …, або n–1 і 0. Закрита формула: Cₙ = (2n)! / ((n+1)! n!) = C(2n,n) / (n+1), де C(2n,n) — центральний біноміальний коефіцієнт. Перші значення: 1, 1, 2, 5, 14, 42, 132, 429, 1430; асимптотично Cₙ ~ 4ⁿ / (n^(3/2) √π).

Що таке рядки збалансованих дужок і як вони пов'язані з Cₙ?

Рядок збалансованих дужок довжини 2n — це послідовність з n відкриваючих «(» і n закриваючих «)», у якій жоден префікс не містить більше «)», ніж «(». Для n = 3 є рівно C₃ = 5 таких рядків: ((())), (()()), (())(), ()(()), ()()(). Бієкція до шляхів Дика пряма: «(» → крок вгору, «)» → крок вниз, правило незаглиблення під вісь відповідає правилу невиходу нижче осі x.

Що таке шлях Дика?

Шлях Дика довжини 2n — це решітчастий шлях з (0, 0) в (2n, 0), що робить n кроків вгору (+1) і n кроків вниз (–1) і ніколи не опускається нижче осі x. Таких шляхів є Cₙ. Вони виникають в аналізі виборчих послідовностей, невід'ємних випадкових блукань і перерахуванні послідовностей у теорії формальних мов (наприклад, валідні Lisp-програми з парними дужками).

Як трикутуляція опуклого многокутника дає Cₙ?

Опуклий (n+2)-кутник можна розбити на трикутники проведенням n–1 непересічних діагоналей; кількість способів зробити це дорівнює Cₙ. Для квадрилатерала (n = 2): два способи; для п'ятикутника (n = 3): п'ять способів. Бієкція до рядків дужок: фіксуємо одне ребро як «корінь», трикутник на ньому ділить многокутник на два менших — це відображає рекуренцію Каталана Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ Cₙ₋₁₋ᵢ. Трикутуляції використовуються у обчислювальній геометрії, скінченноелементному сітковому поділі та проектуванні компіляторів.

Що таке некросингові акордові діаграми?

Некросингова акордова діаграма — це 2n точок на колі, з'єднаних n акордами, що не перетинаються. C₃ = 5 способів з'єднати 6 точок трьома некросинговими акордами — рівно п'ять об'єктів Каталана для n = 3. Ці діаграми виникають у передбаченні вторинної структури РНК (пари основ — некросингові акорди на послідовності), теорії вузлів (алгебри Темперлі–Ліба) та вільній теорії ймовірностей (некросингові розбиття визначають вільні кумулянти).

Яке рекурентне співвідношення для чисел Каталана?

Числа Каталана задовольняють рекуренції C₀ = 1 і Cₙ₊₁ = Σᵢ₌₀ⁿ Cᵢ Cₙ₋ᵢ. Ця формула відображає структуру «розділення в корені», спільну для всіх п'яти сімейств: для рядка дужок кореневе «(» закривається в деякій позиції, ділячи рядок на дві незалежні збалансовані підрядки довжин 2i і 2(n–i). Підсумовування по всіх позиціях розбиття дає рекуренцію. Твірна функція C(x) = Σ Cₙ xⁿ задовольняє x C(x)² – C(x) + 1 = 0.

Чому так багато комбінаторних задач дають числа Каталана?

Уніфікуюча причина: всі сімейства Каталана мають однакову рекурсивну структуру — об'єкт розміру n однозначно будується вибором «кореня», який ділить дані на два незалежних підоб'єкти розмірів i і n–1–i. Це рівно рекуренція Каталана. Бієкції між сімействами часто елегантні: «(» у рядку дужок стає лівим дочірнім ребром у бінарному дереві і кроком вгору на шляху Дика — комбінаторні дані буквально той самий об'єкт у трьох різних «костюмах».

Як швидко зростають числа Каталана?

За формулою Стірлінга Cₙ ~ 4ⁿ / (n^(3/2) √π). Відношення Cₙ₊₁/Cₙ = 2(2n+1)/(n+2) прагне до 4, тому кожне наступне число Каталана приблизно у чотири рази більше за попереднє. C₁₀ = 16 796; C₂₀ ≈ 6,56 × 10¹⁰; C₅₀ ≈ 1,37 × 10²⁸. Для n = 8 (максимум у симуляції) C₈ = 1 430 — достатньо мало, щоб намалювати всі об'єкти. При n > 10 перерахування всіх стає непрактичним і потрібне випадкове сампулювання.

Що таке повні бінарні дерева і як вони рахуються Cₙ?

Повне бінарне дерево — вкорінене дерево, де кожен внутрішній вузол має рівно двох нащадків. Кількість таких дерев із n+1 листками дорівнює Cₙ. Для n = 3: C₃ = 5 дерев із 4 листками. Бієкція до рядків дужок: кожен лист → «)», кожен внутрішній вузол → «(», прочитано у передпорядку. Повні бінарні дерева — структура синтаксичного розбору виразів, кодування Гаффмана і дерева Штерна–Броко для дробів.

Хто першим відкрив числа Каталана?

Ейлер порахував трикутуляції многокутника у 1751 р. і знайшов послідовність 1, 2, 5, 14, 42, … але не мав закритої формули. Зегнер знайшов рекуренцію у 1758 р. Бельгійський математик Ежен Шарль Каталан дав закриту формулу у 1838 р. Однак ще раніше, близько 1730 р., китайський математик Мін Анту відкрив ту саму послідовність у зв'язку з тригонометричними розкладами. Їхні незалежні відкриття — яскравий приклад математичної універсальності.

Де числа Каталана зустрічаються поза чистою математикою?

Числа Каталана зустрічаються в інформатиці (кількість стекосортовних перестановок, кількість бінарних дерев пошуку з n ключами), біоінформатиці (вторинні структури РНК рахуються їх некросинговою дужковою структурою), фізиці (некросингові діаграми Фейнмана в планарній квантовій теорії поля, моменти напівкруглого закону Вігнера в теорії випадкових матриць) і лінгвістиці (кількість дерев розбору неоднозначної КС-граматики). Книга Стенлі «Числа Каталана» (2015) наводить 214 різних комбінаторних інтерпретацій.