Число Каталана
Числа Каталана — числова послідовність, що зустрічається в багатьох задачах комбінаторики. Послідовність названа на честь бельгійського математика Каталана, хоча була відома ще Л. Ейлеру.
Перших декілька чисел Каталана:
Означення
n-те число Каталана можна визначити одним із наступних способів:
- Кількість розбиттів опуклого (n+2)-кутника на трикутники діагоналями, що не перетинаються.
- Кількість правильних дужкових структур довжини 2n.
- Наприклад, для n=3 існує 5 таких послідовностей:
((())), ()(()), ()()(), (())(), (()())
- тобто .
- Кількість способів з'єднання 2n точок на колі n хордами, які не перетинаються.
- Кількість неізоморфних упорядкованих бінарних дерев з коренем з n+1 листом.
Властивості
- Числа Каталана задовольняють рекурентному співвідношенню:
- і для
Це співвідношення легко отримати, помітивши, що будь-яка непуста правильна структура однозначно представлена в формі w=(w1)w2, де w1, w2 — правильні структури.
- Генератриса для чисел Каталана:
- Числа Каталана можна виразити через біноміальні коефіцієнти:
Див. також
Посилання
- С. К. Ландо Лекції по комбінаториці, МЦНМО, 1994.
- А. Шень. Программирование: теоремы и задачи[недоступне посилання з травня 2019], M: МЦНМО, 2004. (разделы 2.6 и 2.7)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.