Число Моцкина

Введение

Число Моцкина M(n)M(n) — это специальное число в комбинаторике, которое подсчитывает количество различных способов нарисовать непересекающиеся хорд между nn точками на окружности и одновременно применяется в других задачах, связанных с графами и последовательностями. Оно часто встречается в теории формальных языков и математической биологии.

Операция

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

M(n)={1,если n=0 или n=1,2(2n−1)n+1M(n−1)+3(n−1)n+1M(n−2),если n≥2\begin{equation*} \begin{aligned} M(n) = \begin{cases} 1, & \text{если } n = 0 \text{ или } n = 1, \\ \frac{2(2n-1)}{n+1}M(n-1) + \frac{3(n-1)}{n+1}M(n-2), & \text{если } n \geq 2 \end{cases} \end{aligned} \end{equation*}

Кроме того, для вычисления M(n)M(n) существует прямая формула через биномиальные коэффициенты:

M(n)=∑k=0n1k+1(2kk)(nk−1)\begin{equation*} \begin{aligned} M(n) = \sum_{k=0}^{n} \frac{1}{k+1} \binom{2k}{k} \binom{n}{k-1} \end{aligned} \end{equation*}

Свойства

  • Инициализация: M(0)=1M(0) = 1 и M(1)=1M(1) = 1.
  • Рекуррентная зависимость: Каждое M(n)M(n) зависит от двух предыдущих значений M(n−1)M(n-1) и M(n−2)M(n-2).
  • Число хорд: Определяет количество способов соединения точек хордой на окружности.
  • Симметрия: Формула числа Моцкина включает симметрические параметры комбинаторики.

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

Пример 1

Вычислите число Моцкина для n=4n = 4 с помощью рекуррентной формулы:

M(2)=2(4−1)2+1M(1)+3(2−1)2+1M(0)=2⋅1+33⋅1=2,M(3)=2(6−1)3+1M(2)+3(3−1)3+1M(1)=104⋅2+64⋅1=204+64=5+1.5=6,M(4)=2(8−1)4+1M(3)+3(4−1)4+1M(2)=145⋅6+95⋅2=16.8+3.6=20.4\begin{equation*} \begin{aligned} M(2) &= \frac{2(4-1)}{2+1}M(1) + \frac{3(2-1)}{2+1}M(0) = 2 \cdot 1 + \frac{3}{3} \cdot 1 = 2, \\ M(3) &= \frac{2(6-1)}{3+1}M(2) + \frac{3(3-1)}{3+1}M(1) = \frac{10}{4} \cdot 2 + \frac{6}{4} \cdot 1 = \frac{20}{4} + \frac{6}{4} = 5 + 1.5 = 6, \\ M(4) &= \frac{2(8-1)}{4+1}M(3) + \frac{3(4-1)}{4+1}M(2) = \frac{14}{5} \cdot 6 + \frac{9}{5} \cdot 2 = 16.8 + 3.6 = 20.4 \end{aligned} \end{equation*}

Пример 2

Вычислите число Моцкина для n=5n = 5 с помощью прямой формулы:

M(5)=∑k=051k+1(2kk)(5k−1)\begin{equation*} \begin{aligned} M(5) = \sum_{k=0}^{5} \frac{1}{k+1} \binom{2k}{k} \binom{5}{k-1} \end{aligned} \end{equation*}

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

  • Что такое число Моцкина?
    • Это число, обозначающее количество способов соединить nn точек на окружности хордой без пересечения.
  • Как число Моцкина связано с комбинаторикой?
    • Оно описывает структурные свойства объектов, не пересекающихся в конкретных комбинаторных конфигурациях.

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

  • Молекулярная биология: Способы укладки цепочек РНК в трёхмерном пространстве могут быть моделированы числом Моцкина.
  • Компьютерные науки: Используется в анализе алгоритмов, например, для оптимизации раскладок сложных структур данных.

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