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

Введение

Числа Каталана — это последовательность натуральных чисел, которые появляются во многих комбинаторных задачах, включая построение деревьев, разбиение многоугольников и вычисление путей на решетке. Данная последовательность названа в честь бельгийского математика Эжена Шарля Каталана. Эти числа играют важную роль в комбинаторике и алгебраической геометрии.

Операция

Число Каталана для некоторого натурального числа nn вычисляется по формуле:

Cn=1n+1(2nn)C_n = \frac{1}{n+1} \binom{2n}{n}

где (2nn)\binom{2n}{n} — это биномиальный коэффициент, который можно вычислить как:

(2nn)=(2n)!(n!)2\binom{2n}{n} = \frac{(2n)!}{(n!)^2}

Таким образом, число Каталана CnC_n можно выразить как:

Cn=(2n)!(n+1)!n!C_n = \frac{(2n)!}{(n+1)!n!}

Свойства

  • Рекурсивность: Числа Каталана можно вычислить рекурсивно: C0=1,Cn+1=∑i=0nCiCn−iC_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}
  • Число делений многоугольника: CnC_n равно числу способов, которыми можно разделить многоугольник с (n+2)(n+2) сторонами на треугольники диагоналями, не пересекающимися внутри.
  • Деревья: CnC_n равно числу допустимых бинарных деревьев с nn внутренними узлами.

Примеры использования

Пример 1

Вычислите C3C_3:

C3=(2×3)!(3+1)!×3!=6!4!×3!=72024×6=720144=5\begin{equation*} \begin{aligned} C_3 &= \frac{(2 \times 3)!}{(3+1)! \times 3!} \\&= \frac{6!}{4! \times 3!} = \frac{720}{24 \times 6} = \frac{720}{144} = 5 \end{aligned} \end{equation*}

Пример 2

Вычислите C4C_4:

C4=(2×4)!(4+1)!×4!=8!5!×4!=40320120×24=403202880=14\begin{equation*} \begin{aligned} C_4 &= \frac{(2 \times 4)!}{(4+1)! \times 4!} \\&= \frac{8!}{5! \times 4!} = \frac{40320}{120 \times 24} = \frac{40320}{2880} = 14 \end{aligned} \end{equation*}

Часто задаваемые вопросы (FAQ)

  • Что такое число Каталана?
    • Это последовательность чисел, используемая в комбинаторике для решения задач, связанных с разбиением и построением структур.
  • Как можно быстро вычислить число Каталана?
    • Используя формулу Cn=(2n)!(n+1)!n!C_n = \frac{(2n)!}{(n+1)!n!}, для небольших значений nn можно точно и быстро вычислить значения.

Примеры из жизни

  • Программирование и алгоритмы: При разработке алгоритмов, связанных с деревьми и графами, числа Каталана помогают оценить количество возможных структур.
  • Геометрическое моделирование: В компьютерной графике разбиение многоугольников на треугольники с помощью чисел Каталана улучшает обработку изображений.

Ссылки на литературу и ресурсы