Числа Каталана — числова (послідовність), що зустрічається в багатьох задачах комбінаторики. Послідовність названа на честь бельгійського математика [en], хоча була відома ще (Л. Ейлеру).
Перших декілька чисел Каталана:
- (1), (1), (2), (5), (14), (42), (132), 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452 … (послідовність A000108 з (Онлайн енциклопедії послідовностей цілих чисел), OEIS)
Означення
n-те число Каталана можна визначити одним із наступних способів:
- Кількість розбиттів опуклого (n+2)-(кутника) на (трикутники) (діагоналями), що не перетинаються.
- Кількість (правильних дужкових структур) довжини 2n.
- Наприклад, для n=3 існує 5 таких послідовностей:
((())), ()(()), ()()(), (())(), (()())
- тобто .
- Кількість способів з'єднання 2n точок на колі n (хордами), які не перетинаються.
- Кількість (неізоморфних) упорядкованих (бінарних дерев) з коренем з n+1 листом.
Властивості
- Числа Каталана задовольняють (рекурентному співвідношенню):
- і для
Це співвідношення легко отримати, помітивши, що будь-яка непуста правильна структура однозначно представлена в формі w=(w1)w2, де w1, w2 — правильні структури.
- (Генератриса) для чисел Каталана:
- Числа Каталана можна виразити через (біноміальні коефіцієнти):
- (Асимптотично)
Див. також
- (Центральний біноміальний коефіцієнт)
Посилання
- С. К. Ландо Лекції по комбінаториці, (МЦНМО), 1994.
- А. Шень. Программирование: теоремы и задачи[недоступне посилання з травня 2019], M: (МЦНМО), 2004. (разделы 2.6 и 2.7)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет