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

Шаблон:Не плутатиЧисла Каталана — числова послідовність, що зустрічається в багатьох задачах комбінаторики. Послідовність названа на честь бельгійського математика Шаблон:Не перекладено, хоча була відома ще Л. Ейлеру.

Перших декілька чисел Каталана:

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 … (Шаблон:OEIS)

Означення

n-те число Каталана $C_n$ можна визначити одним із наступних способів:

Розбиття шестикутника (C₄=14)

• Кількість розбиттів опуклого (n+2)-кутника на трикутники діагоналями, що не перетинаються.

• Кількість правильних дужкових структур довжини 2n.

Наприклад, для n=3 існує 5 таких послідовностей:

((())), ()(()), ()()(), (())(), (()())

тобто $C_3=5$.

• Кількість способів з'єднання 2n точок на колі n хордами, які не перетинаються.

• Кількість неізоморфних упорядкованих бінарних дерев з коренем з n+1 листом.

Властивості

• Числа Каталана задовольняють рекурентному співвідношенню:

$C_0=1$ і $C_n=\sum _{i=0}^{n-1}{C}_i{C}_{n-1-i}$ для $n\ge 1.$

Це співвідношення легко отримати, помітивши, що будь-яка непуста правильна структура однозначно представлена в формі w=(w₁)w₂, де w₁, w₂ — правильні структури.

• Генератриса для чисел Каталана:

$\sum _{n=0}^{\mathrm{\infty }}{C}_n{z}^n=\frac{1-\sqrt{1-4z}}{2z}$

• Числа Каталана можна виразити через біноміальні коефіцієнти:

$C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n-1}).$

• Асимптотично $C_n\sim \frac{4^n}{n^{3/2}\sqrt{\pi }}$

Див. також

• Центральний біноміальний коефіцієнт

Посилання

• С. К. Ландо Лекції по комбінаториці, МЦНМО, 1994.
• А. Шень. Программирование: теоремы и задачиШаблон:Недоступне посилання, M: МЦНМО, 2004. (разделы 2.6 и 2.7)