Изменения

*количество [[Дерево_поиска,_наивная_реализация|не изоморфных упорядоченных бинарных деревьев ]] с корнем и <tex dpi = 120> n + 1 </tex> листьями

*количество [[Триангуляция_полигонов_(ушная_%2B_монотонная)|триангуляций выпуклого <tex dpi = 120> n </tex>-угольника]]

*количество [[Правильные_скобочные_последовательности|корректных скобочных последовательностей, состоящих из <tex dpi = 120> n </tex> открывающих и <tex dpi = 120> n </tex> закрывающих скобок]]*количество таблиц Юнга размером <tex dpi = 120>2n</tex>*количество монотонных путей в квадрате размером <tex dpi = 120>n \times n</tex>, не пересекающих диагональ*количество способов расставить скобки в произведении <tex dpi = 120>n</tex> множителей*количество способов заполнить лестницу ширины и высоты <tex dpi = 120>n</tex> прямоугольникамии так далее}}

Первые несколько чисел Каталана:

<tex dpi = 120> 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ... \ldots </tex>

<tex dpi = 150>C_n = \sum_sum\limits_{i = 0}^{n - 1} C_i C_{n - 1 - i} </tex>

Самой левой открывающей скобке Пусть <tex dpi = 110120> l X</tex> соответствует определённая закрывающая скобка — произвольная правильная скобочная последовательность длины <tex dpi = 110120> r 2n</tex>. Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность <tex dpi = 120>X</tex> в виде: <tex dpi = 120>X = (A)B</tex>, которая разбивает формулу на две частигде <tex dpi = 120>A</tex> и <tex dpi = 120>B</tex> — тоже правильные скобочные последовательности. Если длина последовательности <tex dpi = 120>A</tex> равна <tex dpi = 120>2k</tex>, каждая из которых в свою очередь является правильной скобочной последовательностьюто последовательность <tex dpi = 120>A</tex> можно составить <tex dpi = 120>C_k</tex> способами. Поэтому, если мы обозначим Тогда длина последовательности <tex dpi = 110120> i B</tex> равна <tex dpi = r 120>2(n - l k - 1 )</tex>, то для любого фиксированного и последовательность <tex dpi = 110120> r B</tex> будет ровно можно составить <tex dpi = 135120> C_i C_{n- k -1-i} </tex> способовспособами. Суммируя это по всем допустимым Комбинация любого способа составить последовательность <tex dpi = 110120> i A</tex> с любым способом составить последовательность <tex dpi = 120>B</tex> даст новую последовательность <tex dpi = 120>X</tex>, мы и получаем рекуррентную зависимость на а величина <tex dpi = 120>k</tex> может меняться от <tex dpi = 120>0</tex> до <tex dpi = 120>n - 1</tex>. Получили рекуррентное соотношение: <tex dpi = 135120> C_n = C_0 C_{n-1} + C_1 C_{n-2} + \ldots + C_{n-1} C_0 </tex>. Так как <tex dpi = 120>C_0 = 1</tex>, то последовательность совпадает с числами Каталана.

<tex dpi = 150> C_n = \fracdfrac{1}{n+1} \binom dbinom {2n} {n} </tex>

Правильной скобочной структуре из <tex dpi = 120>n</tex> открывающих и <tex dpi = 120>n</tex> закрывающих скобок мы поставим в соответствие путь в квадрате <tex dpi = 120>[0, n]×[0, n]</tex>. Путь начинается в точке <tex dpi = 120>(0,0)</tex> и заканчивается в точке <tex dpi = 120>(n, n)</tex>. Открывающей скобке мы сопоставляем горизонтальный отрезок длины <tex dpi = 120>1</tex>, а закрывающей — вертикальный.

Сместим правильный путь на 1 одну клетку вниз. Теперь правильный путь начинается в точке<tex dpi = 120> (0, -1) </tex>, заканчивается в точке <tex dpi = 120> (n, n-1) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки <tex fpi = 120> (0, -1) </tex> в точку <tex dpi = 120> (n, n-1) </tex>. Длина такого пути равна <tex dpi = 120>2n</tex> и он содержит <tex dpi = 120>n</tex> вертикальных сегментов и <tex dpi = 120>n</tex> горизонтальных. Количество всех таких путей равно числу способов выбрать <tex dpi = 120>n</tex> вертикальных сегментов из общего числа <tex dpi = 120>2n</tex> сегментов, т.е. равно <tex dpi = 135> \binom dbinom {2n}{n} </tex>.

Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> (точка <tex dpi = 120>A</tex>). Отрезок пути от точки <tex dpi = 120>(0, -1)</tex> до точки <tex dpi = 120>A </tex> заменим симметричным относительно прямой <tex dpi = 120>y = x</tex>. Мы получим путь длины <tex dpi = 120>2n</tex>, идущий из точки <tex dpi = 120>(−1-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> (Смотри рис.).

Такой путь обязательно пересекает прямую <tex dpi = 120> y = x </tex>. Обратно, пусть нам дан путь длины <tex dpi = 120> 2n </tex> из точки <tex dpi = 120>(-1, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> и пусть <tex dpi = 120> A </tex> — первая точка этого пути, лежащая на прямой <tex dpi = 120>y = x</tex>. Заменив участок пути от точки <tex dpi = 120>(−1-1, 0)</tex> до точки <tex dpi = 120>A </tex> на симметричный относительно прямой <tex dpi = 120>y = x</tex>, мы получим неправильный путь из точки <tex dpi = 120>(0, −1-1)</tex> в точку <tex dpi = 120>(n, n-1)</tex>. Следовательно, неправильных путей из точки <tex dpi = 120>(0, -1)</tex> в точку <tex dpi = 120>(n, n-1)</tex> столько же, сколько путей из точки <tex dpi = 120>(-1, 0)</tex> вточку <tex dpi = 120>(n, n-1)</tex>. Такой путь длины <tex dpi = 120>2n</tex> содержит <tex dpi = 120>n+1</tex> горизонтальных и <tex dpi = 120>n-1</tex> вертикальных участков. Поэтому, количество таких путей равно <tex dpi = 135> \binom dbinom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана <tex dpi = 120>C_n</tex>) равно

<tex dpi = 150> C_n = \binom dbinom {2n} {n} - \dbinom {2n} {n-1} = \dfrac{2n!} {n!n!} - \binom dfrac{2n!} {(n-1)!(n+1)!} = \dfrac{2n!}{n!} (\dfrac{1}{n!} - \dfrac{1}{(n-1)! (n+1)}) = \dfrac{2n!}{n!n!(n+1)} = \fracdfrac{1}{n+1} \binom dbinom {2n} {n} </tex>

==ПримерыЗадача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями==

===Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналямиДоказательство===[[Файл:Vectorpaint.png|145px|right]]

Пусть <tex dpi = 120>t_n</tex> — число триангуляций выпуклого <tex dpi = 120> (n + 2) </tex>-угольника при <tex dpi = 120> n \geqslant 1 </tex>. Положим <tex dpi = 120> t_0 = 1 </tex>. Пронумеруем вершины многоугольника, начиная с произвольной против часовой стрелки. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне <tex dpi = 120>01</tex> (см. рис.). Пусть <tex dpi = 120>k</tex> — номер третьей вершины этого треугольника. Выделенный треугольник разбивает <tex dpi = 120>(n + 2)</tex> — угольник на <tex dpi = 120>k</tex> — угольник и <tex dpi = 120>(n-k+3)</tex> — угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi = 120>(n-k+3)</tex> — угольника. Наоборот, каждая пара триангуляций <tex dpi = 120>k</tex> — угольника и <tex dpi = 120>(n-k+3)</tex> — угольникаопределяет триангуляцию исходного многоугольника. Поэтому<tex dpi = 120>t_{n+1} = t_0 t_n + t_1 t_{n-1} + \ldots + t_n t_0 </tex>и поскольку <tex dpi = 120>t_0 = 1</tex>, последовательность чисел <tex dpi = 120>t_n</tex> совпадает с последовательностью Каталана. ===Пример===[[Файл:Каталан.PNG|375px315px|thumb|right|Разбиение выпуклого шестиугольника]]

Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем <tex>5 </tex> разных случаев. В первом и последнем из них количество разбиений равно <tex>14</tex>,

====Доказательство==Подсчет чисел Каталана==Пусть Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится <tex dpi = 120>t_nO(n)</tex> — число триангуляций памяти и <tex dpi = 120> O(n + ^2) </tex> угольника при времени. За <tex dpi = 120> O(n)</tex> времени их можно посчитать, если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу: <tex dpi = 135> C_n = \dfrac{4n-2}{n+1} C_{n -1} </tex>. ==Вычисление [[Производящая функция |производящей функции]] чисел Каталана== {{Лемма|id=lemma1. |statement=<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \cdot \dbinom{2k}{k} </tex>|proof=<tex>\dbinom{\frac{1}{2}}{k} = \dfrac{\dfrac{1}{2} \cdot (\dfrac{1}{2} - 1) \cdot (\dfrac{1}{2} - 2) \cdots (\dfrac{1}{2} - k + 1)}{k!} = \dfrac{1 \cdot (1 - 2) \cdot (1 - 4) \cdots (1 - 2k + 2)}{2^k \cdot k!} = \dfrac{1 \cdot (-1) \cdot (-3) \cdots (-2k + 3)}{2^k \cdot k!}</tex> <tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 3 \cdot (2k - 3) \cdot (2k - 1)}{2^k \cdot k!} = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{1 \cdot 2 \cdot 3 \cdots (2k - 3) \cdot (2k - 2) \cdot (2k - 1) \cdot 2k}{2 \cdot 4 \cdots (2k - 2) \cdot 2k \cdot 2^k \cdot k!}</tex> <tex>= \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{(2 \cdot 1) \cdot (2 \cdot 2) \cdots (2 \cdot (2k - 1)) \cdot (2 \cdot k) \cdot 2^k \cdot k!} = \dfrac{(-1 )^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot (1 \cdot 2 \cdots (k - 1) \cdot k) \cdot 2^k\cdot k!} </tex> <tex> = \dfrac{(-1)^{k - 1}}{2k - 1} \cdot \dfrac{(2k)!}{2^k \cdot k! \cdot 2^k\cdot k!} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 2^k \cdot 2^k} \cdot \dfrac{(2k)!}{k! \cdot k!}= \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \dbinom{2k}{k}</tex>}} {{Задача|definition = Вычислить производящую функцию чисел Каталана}} Пусть мы имеем последовательность чисел Каталана <tex>(C_0, C_1, C_2, \ldots)</tex>.  Будем искать её производящую функцию в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n \cdot z^n</tex> Как известно, рекуррентное соотношение для чисел Каталана имеет вид <tex> C_n=\begin{cases}1,&\text{если $n = 0$; положим }\\\sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n > 0$.}\end{cases} </tex> Домножаем <tex>C_n</tex> на <tex>z^n</tex>, получая <tex dpi > z^n \cdot C_n=\begin{cases}z^0 = 1,&\text{если $n = 0$;}\\z^n \sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n > 0$.}\end{cases} </tex> Суммируя <tex>C_n z^n</tex> по всем <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>, получаем: <tex>G(z) = \sum\limits_{n = 0}^{\infty} C_n z^n = C_0 z^0 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} =C_0 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}</tex> (так как <tex>C_0 = 1</tex> по определению чисел Каталана).  Получили, что <tex>G(z) = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}~~~~~ \textbf{(1)}</tex> Распишем произведение <tex>G(z) \cdot G(z)</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul | произведения формальных степенных рядов]]. <tex>G(z) \cdot G(z) = (\sum\limits_{n = 0}^{\infty} C_n z^n) \cdot (\sum\limits_{n = 0}^{\infty} C_n z^n) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k}</tex> В последнем выражении выполним сдвиг индексации, положив <tex>n' = 120n + 1</tex>. Тогда имеем: <tex> t_0 n = n' - 1, n = 0 \Rightarrow n' = 1</tex> . Кроме того, <tex>z^n = z^{n' - 1}</tex>. <tex>n - k</tex> преобразуется в <tex>n' - 1- k</tex> (так как <tex>n' - 1 = n</tex>). Рассмотрим произвольную триангуляцию Тогда, преобразуя предыдущее выражение, получаем: <tex>G(z) \cdot G(z) = \sum\limits_{n = 0}^{\infty}z^n \sum\limits_{k = 0}^{n} C_k C_{n - k} = \sum\limits_{n' = 1}^{\infty}z^{n' - 1} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1}</tex> Домножая это произведение на <tex>z</tex>, получаем <tex>z \cdot G^2(z) = z \cdot \sum\limits_{n' = 1}^{\infty}z^{n' - 1} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1} = \sum\limits_{n' = 1}^{\infty}z^{n'} \sum\limits_{k = 0}^{n' - 1} C_k C_{n' - k - 1}</tex> Тогда  <tex>z \cdot G^2(z) = \sum\limits_{n = 1}^{\infty}z^{n} \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1} ~~~~ \textbf{(2)}</tex> Из <tex> \textbf{(1)}</tex> и выделим треугольник<tex>\textbf{(2)}</tex> получаем: <tex>G(z) = 1 + z \cdot G^2(z)</tex> Преобразуя, получаем квадратное уравнение на <tex>G(z) :</tex> <tex>z \cdot G^2(z) - G(z) + 1 = 0</tex> Из этого квадратного уравнения находим два варианта <tex>G(z) :</tex> <tex>G(z) = \dfrac{1 \pm \sqrt{1-4z}}{2z}</tex> Выберем из двух корней тот, примыкающий к стороне 01 который удовлетворяет определению <tex>G(смz)</tex> как производящей функции чисел Каталана. рис Домножая обе части на <tex>2z</tex>, получаем <tex>G(z) \cdot 2z = 1 \pm \sqrt{1-4z} ~~~~~\textbf{(3)}</tex> Выберем нужный из двух корней, посчитав значение обеих частей при <tex>z = 0</tex> Из определения производящей функции для чисел Каталана известно, что <tex>G(z) = C_0 + C_1 \cdot x + \ldots + C_n \cdot x^n + \ldots</tex>, тогда <tex>G(0) = C_0 = 1</tex> Тогда при <tex>z = 0</tex> выражение <tex>\textbf{(3)}</tex> принимает вид <tex>G(0) \cdot 2 \cdot 0 = 1 \pm \sqrt{1-4 \cdot 0}</tex>, или <tex>0 = 1 \pm 1</tex>. Тогда очевидно, нужно выбрать знак <tex>-</tex> в выражении, чтобы при <tex>z = 0</tex> левая и правая части были равны. Тогда <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex> Проверим, что <tex>G(z)</tex> действительно является производящей функцией чисел Каталана. Для этого разложим <tex>G(z)</tex> в ряд.

Пусть <tex dpi > = 120>k</tex> — номер третьей вершины этого треугольника. Выделенный треугольник разбивает <tex dpi \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 120>0}^{\infty} ((-4z)^n + 2\cdot \dfrac{(-1)</tex>^{n -угольник на <tex dpi = 120>k</tex>1}}{(2n -угольник и <tex dpi = 120>(1) \cdot 4^n} \cdot \dbinom{2n}{n-k+3})</tex>-угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций <tex dpi = 120>k</tex>\dfrac{1}{2z} -угольника и <tex dpi \dfrac{1}{2z} \cdot \sum\limits_{n = 120>0}^{\infty} (\dfrac{(-1)^n \cdot 4^n \cdot z^n\cdot (-k+31)</tex>^{n -угольника. Наоборот, каждая пара триангуляций <tex dpi = 120>k</tex>1}}{(2n -угольника и <tex dpi = 120>(1) \cdot 4^n} \cdot \dbinom{2n}{n-k+3})</tex>= \dfrac{1}{2z} -угольникаопределяет триангуляцию исходного многоугольника. Поэтому<tex dpi = 120>t_\dfrac{n+1} {2z} \cdot \sum\limits_{n = t_0 t_n + t_1 t_0}^{n\infty} (\dfrac{(-1)^{2n -1} + \cdot 4^n \cdot z^n}{(2n - 1) \cdot 4^n} \cdot + t_n t_0 </tex>и поскольку <tex dpi = 120>t_0</tex> = 1, последовательность чисел <tex dpi = 120>t_n\dbinom{2n}{n})</tex> совпадает с последовательностью Каталана.

<tex> =\dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n =0}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) =Задача расстановки скобок==\dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-z^0}{2 \cdot 0 - 1} \cdot \dbinom{2 \cdot 0}{0} - \dfrac{1}{2z} \cdot \sum\limits_{n =1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n})</tex>

Рассмотрим какое<tex>= \dfrac{1}{2z} -нибудь арифметическое выражение и сотрём всё, кроме скобок.Получим некоторую систему открывающих и закрывающих скобок. Какими свойствами она обладает? Во\dfrac{1}{2z} \cdot \dfrac{-первых, открывающих скобок ровно столько же, сколько изакрывающих. Во1}{-вторых, ни в каком начальном отрезке количество закрывающихскобок не может оказаться больше количества открывающих скобок. 1} \cdot 1- \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(Например,расстановки <tex dpi 2n - 1)} \cdot \dbinom{2n}{n}) = 110> )( </tex> и <tex dpi \dfrac{1}{2z} - \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 110> (1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n})= \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{z^n}{(2n - 1)} \cdot \dbinom{2n}{n})( </tex> — неправильные.) Эти два условия не только необходимы, но и достаточны.

Рассмотрим несколько примеров. Одна пара скобок может выглядеть единственным способом: <tex dpi = 110> () </tex>. Две пары — двумя способами: <tex dpi = 110> ()() </tex> или <tex dpi \sum\limits_{n = 110> 1}^{\infty} (\dfrac{z^{n - 1}}{(4n - 2)} \cdot \dbinom{2n}{n}) </tex>. Три пары —пятью способами: <tex dpi = \sum\limits_{n = 110> 0}^{\infty} ()\dfrac{z^{n}}{(4n + 2)(), (} \cdot \dbinom{2n + 2}{n + 1})= \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dbinom{2n + 2}{n + 1}), = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2))} \cdot \dfrac{(2n + 2), !}{(()()) </tex> или <tex dpi = 110> ((())) </tex>. Четыре пары, как нетрудно проверить,— четырнадцатью способам и. Чтобы понять, сколькими способами могут выглядеть правильно расставленные пять пар скобок, рассмотрим закрывающую скобку, парную к первой открывающей скобке. Остальные четыре парытогда разделятся на две группы: расположенные внутри рассмотренной пары ирасположенные справа от неё. (Разумеется, любая из этих групп может состоять из0 скобок.n + 1) Способов, когда все четыре пары внутри или все четыре справа, имеетсяпо 14 штук. Когда три пары внутри, а одна справа, имеем 5 способов. Столькоже — когда одна внутри, а три справа. Наконец, когда две пары внутри, а двесправа, имеем 2 · 2 = 4 способа. Итого<tex dpi = 120> 14 + 5 + 2 ! \cdot 2 (n + 5 + 14 = 42 1)!}</tex>способа. Следуя такому походу, можно вычислять количество правильных скобочных последовательностей дальше.

==Подсчет чисел Каталана==Будем вести подсчет с использованием метода динамического программирования. Пусть <tex dpi = 120>d[i][j]</tex> - число скобочных последовательностей длиной <tex dpi = 120>i</tex> с балансом <tex dpi \sum\limits_{n = 120>j</tex>. Скобочную последовательность длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>, можно получить из скобочной последовательности длины <tex dpi = 120>i-0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n)! \cdot (2n + 1</tex> с балансом или <tex dpi = 120>j-) \cdot 2 \cdot (n + 1</tex> )}{(n)! \cdot (добавив в конец открывающуюся скобкуn), или <tex dpi = 120>j! \cdot (n +1</tex> ) \cdot (добавив в конец закрывающуюся скобкуn + 1)}), т.е. <tex dpi = 120>d[i][j] \sum\limits_{n = d[i-1][j-1]0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{2 \cdot (2n +d[i-1][j)}{n +1]</tex>. База <tex dpi = 120>d[0][0]</tex> = 1. Так же можно заметить, что максимальный баланс правильной скобочной последовательности длины <tex dpi = 120>} \cdot \dbinom{2n</tex>, равен <tex dpi }{n}) = 120>\sum\limits_{n</tex>. <tex dpi = 120> 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(4n + 2)}{n </tex> -ое число Каталана будет храниться в ячейке <tex dpi = 120>d[+ 1} \cdot \dbinom{2n][0]}{n})</tex>.

'''Псевдокод:''' '''function''' CatalanNumber<tex>= \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n: '''int'''}}{(4n + 2) d[0][0] = } \cdot \dfrac{2 \cdot (2n + 1 '''for''' i = )}{n + 1 '''to''' } \cdot \dbinom{2n '''for''' j }{n}) = \sum\limits_{n = 0 '''to''' }^{\infty} (z^n d[i][j] = d[i-\cdot \dfrac{1][j-1] + d[i-1][j}{n +1] '''return''' d[} \cdot \dbinom{2n][0]}{n})</tex>

===Таблица значений===Найдем значения таблицы для Тогда коэффициент при <tex>z^n</tex> в разложении <tex>G(z)</tex> равен <tex dpi = 120>\dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex> , что совпадает с аналитической формулой для чисел Каталана. (<tex>C_n = 4\dfrac{| class1}{n + 1} \cdot \dbinom{2n}{n}</tex>) Поэтому <tex>G(z) ="wikitable"|-!width="20"| i\j!widthsum\limits_{n ="40"| 0!width}^{\infty} z^n \cdot C_n</tex>, поэтому <tex>G(z) ="40"| 1!width="40"| 2!width="40"| 3!width="40"| 4!width="40"| 5!width="40"| 6!width="40"| 7!width="40"| 8|-! 0| \dfrac{1| 0| 0| 0| 0| 0| 0| 0| 0|-! 1| 0| 1| 0| 0| 0| 0| 0| 0| 0|-! 2| \sqrt{1| 0| 1| 0| 0| 0| 0| 0| 0|-! 3| 0| 2| 0| 1| 0| 0| 0| 0| 0|-! 4| 2| 0| 3| 0| 1| 0| 0| 0| 0|-! 5| 0| 5| 0| 4| 0| 0| 0| 0| 0|-! 6| 5| 0| 9| 0| 4| 0| 0| 0| 0|-! 7 | 0| 14| 0| 13| 0| 0| 0| 0| 0|-! 8 | 14| 0| 27| 0| 13| 0| 0| 0| 0|4z}}{2z}</tex> является производящей функцией чисел Каталана.

<wikitex>*[[Производящая_функция|Производящая функция]] *[[Числа_Стирлинга_первого_рода|Числа Стирлинга первого рода]] *[http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F Двоичное дерево поиска[Числа_Стирлинга_второго_рода|Числа Стирлинга второго рода]] *[http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D1%80%D0%B8%D0%B0%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D0%BB%D0%B8%D0%B3%D0%BE%D0%BD%D0%BE%D0%B2_(%D1%83%D1%88%D0%BD%D0%B0%D1%8F_%2B_%D0%BC%D0%BE%D0%BD%D0%BE%D1%82%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F) Триангуляция полигонов[Числа_Эйлера_I_и_II_рода|Числа Эйлера первого и второго рода]]</wikitex>

 *[https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 Википедия — Числа Каталана — Википедия]