Изменения

*количество [[Дерево_поиска,_наивная_реализация|не изоморфных упорядоченных бинарных деревьев ]] с корнем и <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>

Сместим правильный путь на 1 клетку вниз. Теперь правильный путь начинается в точкеПравильной скобочной структуре из <tex dpi = 120> (0, −1) n</tex>, заканчивается в точке открывающих и <tex dpi = 120> (n, n − 1) </tex> и не имеет общих точек с прямой закрывающих скобок мы поставим в соответствие путь в квадрате <tex dpi = 120> y = x [0, n]×[0, n]</tex> — биссектрисой первогоквадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных,и из общего числа путей вычтем количество неправильных.Мы рассматриваем пути из точки Путь начинается в точке <tex fpi dpi = 120> (0, −10) </tex> и заканчивается в точку точке <tex dpi = 120> (n, n − 1) </tex>. Длина такого пути равна 2n и он содержит nвертикальных сегментов и n горизонтальных. Количество всех таких путей равно числу способов выбрать nвертикальных сегментов из общего числа 2n сегментов, т.е. равно Открывающей скобке мы сопоставляем горизонтальный отрезок длины <tex dpi = 135120> \binom {n}{2n} 1</tex>, а закрывающей — вертикальный.Рассмотрим неправильный Если путь и сопоставлен правильной структуре, то ни одна его первую точку на прямой <tex dpi = 120> y = x </tex> (точка A). Отрезок пути от точки(0, −1) до точки A заменим симметричным относительно прямой y = x. Мы получим путь длины 2n, идущийиз точки (−1, 0) в точку (n, n − 1)не может лежать выше главной диагонали квадрата.Такой путь обязательно пересекает прямую y = x.Обратно, пусть нам дан путь длины 2n из точки такому пути (−1, 0) в точку (n, n − 1) и пусть A — первая точкаэтого пути, лежащая на прямой y = x. Заменив участок "правильному пути от точки (−1, 0") до точки A на симметричныйотносительно прямой y = x, мы получим неправильный путь из точки (0, −1) в точку (n, n − 1). Следова-тельно, неправильных путей из точки (0, −1) в точку (n, n − 1) столько же, сколько путей из точки (−1, 0) вточку (n, n−1). Такой путь длины содержит n+ 1 горизонтальных и n−1 вертикальных участковсопоставляется правильная скобочная структура. Поэтому,количество таких путей равно C n−1 2n. Значит, количество Геометрическое представление правильных путей (т.ескобочных структур позволяет найти выражение для чисел Каталана. число Каталана Cn) равно

Сместим правильный путь на одну клетку вниз. Теперь правильный путь начинается в точке<tex dpi = 150120> C_n (0, -1) </tex>, заканчивается в точке <tex dpi = \binom {2n} {120> (n} - \binom {2n} {, n-1} ) </tex> и не имеет общих точек с прямой <tex dpi = 120> y = x </tex> — биссектрисой первого квадранта. Нам нужно найти количество правильных путей. Для этого мы найдем количество неправильных, и из общего числа путей вычтем количество неправильных. Мы рассматриваем пути из точки <tex fpi = \frac{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, 0)</tex> в точку <tex dpi = 120>(n, n-1)</tex> (Смотри рис.).[[Файл:Каталан2.PNG|right]]Такой путь обязательно пересекает прямую <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, 0)</tex> до точки <tex dpi = 120>A</tex> на симметричный относительно прямой <tex dpi = 120>y = x</tex>, мы получим неправильный путь из точки <tex dpi = 120>(0, -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> \dbinom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана <tex dpi = 120>C_n</tex>) равно

<tex> C_n = \dbinom {2n} {n} - \dbinom {2n} {n-1} =\dfrac{2n!}{n!n!} - \dfrac{2n!}{(n-1)!(n+1)!} =\dfrac{2n!}{n!} (\dfrac{1}{n!} - \dfrac{1}{(n-1)! (n+1)}) =Задача разбиения выпуклого <tex dpi \dfrac{2n!}{n!n!(n+1)} = 155 > \dfrac{1}{n+1} \dbinom {2n} {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> 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 dpi > по всем <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 = 1200}^{n - 1} C_k C_{n - k - 1}~~~~~ \textbf{(1)}</tex> Распишем произведение <tex> t_0 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' = n + 1</tex>. Рассмотрим произвольную триангуляцию Тогда имеем: <tex>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>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{\sqrt{1-4z}}{2z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sqrt{1 - 4z} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot (1 - 4z)^{\frac{1}{2}} = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dbinom{\frac{1}{2}}{n})</tex> <tex> = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} ((-4z)^n \cdot \dfrac{(-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^n \cdot 4^n \cdot z^n \cdot (-1)^{n - 1}}{(2n - 1) \cdot 4^n} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 0}^{\infty} (\dfrac{(-1)^{2n - 1} \cdot 4^n \cdot z^n}{(2n - 1) \cdot 4^n} \cdot \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 dpi > = 120>k</tex> — номер третьей вершины этого треугольника. Выделенный треугольник разбивает <tex dpi \sum\limits_{n = 120>1}^{\infty} (\dfrac{z^{n + - 1}}{(4n - 2)</tex>-угольник на <tex dpi } \cdot \dbinom{2n}{n}) = 120>k</tex>-угольник и <tex dpi \sum\limits_{n = 120>0}^{\infty} (\dfrac{z^{n-k}}{(4n +32)</tex>-угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi = 120>(} \cdot \dbinom{2n + 2}{n-k+31})</tex>-угольника. Наоборот, каждая пара триангуляций <tex dpi = 120>k</tex>-угольника и <tex dpi \sum\limits_{n = 120>0}^{\infty} (\dfrac{z^{n-k}}{(4n +32)</tex>-угольникаопределяет триангуляцию исходного многоугольника. Поэтому<tex dpi = 120>t_} \cdot \dbinom{2n + 2}{n+1} ) = \sum\limits_{n = t_0 t_n + t_1 t_0}^{\infty} (\dfrac{z^{n-1} }{(4n + 2)} \cdot \cdot dfrac{(2n + 2)!}{(n + 1)! \cdot (n + t_n t_0 </tex>и поскольку <tex dpi = 120>t_0</tex> = 1, последовательность чисел <tex dpi = 120>t_n)!}</tex> совпадает с последовательностью Каталана.

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

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

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