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

Числа

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,...

называемые числами Каталана, играют в комбинаторике важную роль. На сегодняшний день известно около 90 задач математики и физики, в которых встречаются эти числа. Многие примеры можно отыскать по ссылкам в энциклопедии целочисленных последовательностей. Последовательность Каталана зарегистрирована там под номером A000108.

Рассмотрим одну классическую задачу, в которой возникает последовательность чисел Каталана, выведем производящую функцию и формулу

\begin{displaymath} C_n = \frac{1}{n+1}\binom{2n}{n}. \end{displaymath}

Правильные скобочные последовательности

Сколько существует правильных скобочных последовательностей, состоящих из 2n скобок (n открывающих и n закрывающих)? Например, если n=3, то таких последовательностей всего 5:

\begin{displaymath} \texttt{()()()}, \texttt{(())()}, \texttt{()(())}, \texttt{(()())}, \texttt{((()))}. \end{displaymath}

Пусть Cn — ответ к нашей задаче. Положим по определению C0=1. Очевидно, что любая правильная скобочная последовательность начинается с открывающей скобки. Между ней и соответствующей ей закрывающей скобкой можно расположить правильную последовательность из 2k скобок (где 0≤k<n):

\begin{displaymath} \overbrace{\texttt{\textcolor{red}{(}$\underbrace{\texttt{... ...r{red}{)}$\underbrace{\texttt{(\ldots)}}_{2(n-k-1)}$}}^{2n}. \end{displaymath}

Таким образом, чтобы узнать количество правильных скобочных последовательностей из 2n скобок, нужно перебрать все возможные способы расположить 2k скобок в зоне между красными скобками (рис) и 2(n-k-1) скобок после неё. Получаем рекуррентное соотношение:

\begin{displaymath}\begin{array}{rcl} \displaystyle C_0&{}={}&1,\\ \display... ...style \sum_{k=0}^{n-1}C_kC_{n-k-1}, \quad n>0. \end{array} \end{displaymath}

Это соотношение нужно резрешить и вывести общую формулу. О решении рекуррентных соотношений подробнее говорилолсь здесь. Будем искать производящую функцию в виде

\begin{displaymath} G(z) = \sum_{n=0}^{\infty}C_nz^n. \end{displaymath}

В рекуррентном соотношении домножаем Cn на zn:

\begin{displaymath}\begin{array}{rcl} z^0 C_0&{}={}&z^0,\\ z^n C_n&{}={}&z^... ...style \sum_{k=0}^{n-1}C_kC_{n-k-1}, \quad n>0. \end{array} \end{displaymath}

Выполняя суммирования по всем n, получаем

\begin{displaymath} G(z) = 1 + \sum_{n=1}^{\infty} z^n \sum_{k=0}^{n-1}C_kC_{n-k-1}. \end{displaymath}

Обратите внимание, что сумма в этом выражении ни что иное как свёртка производящих функций:

\begin{displaymath} G(z)\cdot G(z) = \sum_{n=0}^{\infty} z^n \sum_{k=0}^{n}C_k... ... = \sum_{n=1}^{\infty} z^{n-1} \sum_{k=0}^{n-1}C_kC_{n-k-1}. \end{displaymath}

Значит, окончательное уравнение для производящей функции будет иметь вид

\begin{displaymath} G(z) = 1 + zG^2(z), \end{displaymath}

или, что то же самое,

\begin{displaymath} zG^2(z) - G(z) + 1 = 0. \end{displaymath}

Из этого квадратного уравнения легко найти G(z):

\begin{displaymath} G(z) = \frac{1\pm\sqrt{1-4z}}{2z}. \end{displaymath}

Теперь нужно определиться, какой из двух корней нас интересует. Заметим, что G(z) должно быть равно 1 при z=0, следовательно, нам подходит корень со знаком минус:

\begin{displaymath} G(z) = \frac{1-\sqrt{1-4z}}{2z}. \end{displaymath}

Чтобы проверить это, нужно перейти в этом выражении к пределу при z→0.

Осталось разложить в ряд полученное выражение (здесь мы пользуемся расширенными биномиальными коэффициентами):

\begin{displaymath}\displaylines{ \ig{0.2} G(z) = \frac{1}{2z}-\frac{\sqrt{1-4... ...=\sum_{n=0}^{\infty}\frac{z^n}{n+1}\binom{2n}{n}\ig{0.2} } \end{displaymath}

Откуда получается, что

\begin{displaymath} C_n = [z^n]G(z) = \frac{1}{n+1}\binom{2n}{n}. \end{displaymath}

Выведенная формула даёт ещё одно, более простое рекуррентное соотношение:

\begin{displaymath} C_n = \frac{4n-2}{n+1}C_{n-1}, \quad n>0. \end{displaymath}

В одном из упражнений будет предложено показать, что

\begin{displaymath} C_n = \binom{2n}{n}-\binom{2n}{n+1}. \end{displaymath}

Язык Дика

Правильные скобочные последовательности имею и другое название: слова Дика (Dyck). В случае, когда рассматриваются скобки только одного вида, слова Дика порождаются следующей контекстно-свободной грамматикой

\begin{displaymath}\begin{array}{rcl} A&{}\rightarrow{}&\epsilon,\\ A&{}\rightarrow{}&(A)A. \end{array} \end{displaymath}

Здесь ε — пустое слово. Эта грамматика указывает на то, что все правильные скобочные последовательности (ПСП) строятся по одному и тому же правилу: либо ПСП — это пустое слово, либо ПСП, взятая в скобки, за которыми снова идет ПСП.

Асимптотика

Рассмотрим поведение последовательности чисел Каталана на бесконечности. Для определения главного члена асимптотики воспользуемся формулой Стирлинга

\begin{displaymath} n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n. \end{displaymath}

Отсюда получаем

\begin{displaymath} C_n = \frac{(2n)!}{n!(n+1)!} \approx \frac{\sqrt{4\pi n}\l... ...dot 4^n}{\sqrt{\pi}(n+1)^{3/2}}\left(\frac{n}{n+1}\right)^n. \end{displaymath}

Теперь преобразуем выражение следующим образом:

\begin{displaymath} \frac{e\cdot 4^n}{\sqrt{\pi}(n+1)^{3/2}}\left(\frac{n}{n+1... ...t 4^n}{\sqrt{\pi}n^{3/2}}\left(\frac{n}{n+1}\right)^{n+3/2}. \end{displaymath}

Вспомнив один из замечательных пределов, можно заменить выражение со скобками на 1/e, окончательно записав

\begin{displaymath} C_n \approx \frac{4^n}{n^{3/2}\sqrt{\pi}}. \end{displaymath}

Блуждания на полупрямой

Ещё одна классическая задача, в которой встречаются числа Каталана. Рассмотрим прямую. Некоторый объект находится на прямой в позиции 0. Он может за один шаг переместиться либо влево, либо вправо на одну позицию. Сколькими способами можно переместиться из начальной позиции в неё же за 2n шагов так, чтобы ни разу не оказаться левее нуля?

Сначала рассмотрим случай, когда нулевую отметку можно пересекать (задача о блуждании на прямой). В этом случае нужно совершить 2n шагов, n из которых делаются влево и n — вправо (в любой последовательности). Обозначим символом 0 движение влево, а символом 1 движение вправо. Сколько существует последовательностей из нулей и единиц, в которых нулей и единиц ровно по n? Это число сочетаний:

\begin{displaymath} \binom{2n}{n}. \end{displaymath}

Теперь рассмотрим случай, когда движение левее нуля запрещено. В этом случае на каждом шаге требуется, чтобы количество уже сделанных шагов влево было не больше количества уже сделанных шагов вправо. Представим, что шаг вправо — это открывающая скобка, а шаг влево — закрывающая. Тогда любой путь из 0 в 0, не пересекающий левую границу, может быть представлен правильной скобочной последовательностью. И наоборот, любая правильная последовательность будет задавать путь. Таким образом, число блужданий на полупрямой есть величина

\begin{displaymath} C_n = \frac{1}{n+1}\binom{2n}{n}. \end{displaymath}
↑ наверх ↑
вернуться к содержанию