Числа Каталана — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Подсчет чисел Каталана)
м (rollbackEdits.php mass rollback)
 
(не показано 79 промежуточных версий 6 участников)
Строка 4: Строка 4:
 
|id = def1
 
|id = def1
 
|definition ='''Числа Каталана''' {{---}} последовательность чисел, выражающих:
 
|definition ='''Числа Каталана''' {{---}} последовательность чисел, выражающих:
*количество не изоморфных упорядоченных бинарных деревьев с корнем и <tex dpi = 120> n + 1 </tex> листьями
+
*количество [[Дерево_поиска,_наивная_реализация|не изоморфных упорядоченных бинарных деревьев]] с корнем и <tex dpi = 120> n + 1 </tex> листьями
 
*количество способов соединения <tex dpi = 120> 2n </tex> точек на окружности <tex dpi = 120> n </tex> не пересекающимися хордами
 
*количество способов соединения <tex dpi = 120> 2n </tex> точек на окружности <tex dpi = 120> n </tex> не пересекающимися хордами
*количество триангуляций выпуклого <tex dpi = 120> n </tex>-угольника
+
*количество [[Триангуляция_полигонов_(ушная_%2B_монотонная)|триангуляций выпуклого <tex dpi = 120> n </tex>-угольника]]
 
*количество способов полностью разделить скобками <tex dpi = 120> n + 1 </tex> множитель
 
*количество способов полностью разделить скобками <tex dpi = 120> n + 1 </tex> множитель
*количество корректных скобочных последовательностей, состоящих из <tex dpi = 120> n </tex> открывающих и <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, ... </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_{i = 0}^{n - 1} C_i C_{n - 1 - i} </tex>
+
===Рекуррентная формула===
 +
<tex dpi = 150>C_n = \sum\limits_{i = 0}^{n - 1} C_i C_{n - 1 - i} </tex>
 
====Доказательство====
 
====Доказательство====
 
Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.
 
Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.
  
Самой левой открывающей скобке <tex dpi = 110> l </tex> соответствует определённая закрывающая скобка <tex dpi = 110> r </tex>, которая разбивает формулу на две части, каждая из которых в свою очередь является правильной скобочной последовательностью. Поэтому, если мы обозначим <tex dpi = 110> i = r - l - 1 </tex>, то для любого фиксированного <tex dpi = 110> r </tex> будет ровно <tex dpi = 135> C_i C_{n-1-i} </tex> способов. Суммируя это по всем допустимым <tex dpi = 110> i </tex>, мы и получаем рекуррентную зависимость на <tex dpi = 135> C_n </tex>.
+
Пусть <tex dpi = 120>X</tex> — произвольная правильная скобочная последовательность длины <tex dpi = 120>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 = 120>B</tex> равна <tex dpi = 120>2(n - k - 1)</tex> и последовательность <tex dpi =120>B</tex> можно составить <tex dpi = 120>C_{n - k - 1}</tex> способами. Комбинация любого способа составить последовательность <tex dpi = 120>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 = 120>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 = \frac{1}{n+1} \binom {2n} {n} </tex>
+
<tex dpi = 150> C_n = \dfrac{1}{n+1} \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>. Открывающей скобке мы сопоставляем горизонтальный отрезок длины 1, а закрывающей — вертикальный.
+
Правильной скобочной структуре из <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 {2n}{n} </tex>.
+
<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> \dbinom {2n}{n} </tex>.
  
Рассмотрим неправильный путь и его первую точку на прямой <tex dpi = 120> y = x </tex> (точка A). Отрезок пути от точки <tex dpi = 120>(0, -1)</tex> до точки A заменим симметричным относительно прямой <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> 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]]
 
[[Файл:Каталан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> и пусть A — первая точка этого пути, лежащая на прямой <tex dpi = 120>y = x</tex>. Заменив участок пути от точки <tex dpi = 120>(−1, 0)</tex> до точки A на симметричный относительно прямой <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> 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>n+1</tex> горизонтальных и <tex dpi = 120>n-1</tex> вертикальных участков. Поэтому, количество таких путей равно <tex dpi = 135> \binom {2n}{n-1} </tex>. Значит, количество правильных путей (т.е. число Каталана <tex dpi = 120>C_n</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 dpi = 150> C_n = \binom {2n} {n} - \binom {2n} {n-1} = \frac{1}{n+1} \binom {2n} {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)}) = \dfrac{2n!}{n!n!(n+1)} = \dfrac{1}{n+1} \dbinom {2n} {n} </tex>
  
==Примеры==
+
==Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями==
  
===Задача разбиения выпуклого <tex dpi = 155 > n </tex>—угольника на треугольники не пересекающимися диагоналями===
+
===Доказательство===
 +
[[Файл:Vectorpaint.png|145px|right]]
  
[[Файл:Каталан.PNG|375px|thumb|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|315px|thumb|right|Разбиение выпуклого шестиугольника]]
 
Ответ на задачу при <tex dpi = 120> n = 3 </tex> тривиален: никаких
 
Ответ на задачу при <tex dpi = 120> n = 3 </tex> тривиален: никаких
 
диагоналей проводить не надо. В четырёхугольнике можно провести любую из
 
диагоналей проводить не надо. В четырёхугольнике можно провести любую из
Строка 53: Строка 68:
 
к ней примыкают соответственно треугольники <tex dpi = 120> BCA, BCF, BCE </tex> и <tex dpi = 120> BCD </tex>.
 
к ней примыкают соответственно треугольники <tex dpi = 120> BCA, BCF, BCE </tex> и <tex dpi = 120> BCD </tex>.
  
Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем 5 разных случаев. В первом и последнем из них количество разбиений равно 14,
+
Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем <tex>5</tex> разных случаев. В первом и последнем из них количество разбиений равно <tex>14</tex>,
 
ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом
 
ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом
 
случаях при вырезании треугольника семиугольник распадается на треугольник и
 
случаях при вырезании треугольника семиугольник распадается на треугольник и
Строка 64: Строка 79:
 
способа.Такие вычисления можно проводить и дальше.
 
способа.Такие вычисления можно проводить и дальше.
  
====Доказательство====
+
==Подсчет чисел Каталана==
Пусть <tex dpi = 120>t_n</tex> — число триангуляций <tex dpi = 120> (n + 2) </tex> угольника при <tex dpi = 120> n >= 1 </tex>; положим <tex dpi = 120> t_0 </tex> = 1. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне 01 (см. рис.).
+
Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится <tex dpi = 120>O(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> по всем <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' = 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>
 +
 
 +
Выберем из двух корней тот, который удовлетворяет определению <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> в ряд.
  
[[Файл:Каталан1.PNG]]
+
<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 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> = \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 dpi = 120>t_{n+1} = t_0 t_n + t_1 t_{n-1} + \cdot \cdot \cdot + t_n t_0 </tex>
 
и поскольку <tex dpi = 120>t_0</tex> = 1, последовательность чисел <tex dpi = 120>t_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}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 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 = 110> () </tex>. Две пары — двумя способами: <tex dpi = 110> ()() </tex> или <tex dpi = 110> (()) </tex>. Три пары —
+
<tex> = \sum\limits_{n = 1}^{\infty} (\dfrac{z^{n - 1}}{(4n - 2)} \cdot \dbinom{2n}{n}) = \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 \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n + 2)!}{(n + 1)! \cdot (n + 1)!}</tex>
пятью способами: <tex dpi = 110> ()()(), ()(()), (())(), (()()) </tex> или <tex dpi = 110> ((())) </tex>. Четыре пары, как нетрудно проверить,— четырнадцатью способам и. Чтобы понять, сколькими способами могут выглядеть правильно расставленные пять пар скобок, рассмотрим закрывающую скобку, парную к первой открывающей скобке. Остальные четыре пары
 
тогда разделятся на две группы: расположенные внутри рассмотренной пары и
 
расположенные справа от неё. (Разумеется, любая из этих групп может состоять из
 
0 скобок.) Способов, когда все четыре пары внутри или все четыре справа, имеется
 
по 14 штук. Когда три пары внутри, а одна справа, имеем 5 способов. Столько
 
же — когда одна внутри, а три справа. Наконец, когда две пары внутри, а две
 
справа, имеем 2 · 2 = 4 способа. Итого
 
<tex dpi = 120> 14 + 5 + 2 \cdot 2 + 5 + 14 = 42 </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 = 120>d[i][j]</tex> - число скобочных последовательностей длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>. Скобочную последовательность длиной <tex dpi = 120>i</tex> с балансом <tex dpi = 120>j</tex>, можно получить из скобочной последовательности длины <tex dpi = 120>i-1</tex> с балансом или <tex dpi = 120>j-1</tex> (добавив в конец открывающуюся скобку), или <tex dpi = 120>j+1</tex> (добавив в конец закрывающуюся скобку), т.е. <tex dpi = 120>d[i][j] = d[i-1][j-1]+d[i-1][j+1]</tex>. База <tex dpi = 120>d[0][0]</tex> = 1. Так же можно заметить, что максимальный баланс правильной скобочной последовательности длины <tex dpi = 120>2n</tex>, равен <tex dpi = 120>n</tex>. <tex dpi = 120> n </tex> -ое число Каталана будет храниться в ячейке <tex dpi = 120>d[2n][0]</tex>.
 
  
'''Псевдокод:'''
+
<tex>= \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} (z^n \cdot \dfrac{1}{n + 1} \cdot \dbinom{2n}{n})</tex>
'''function''' CatalanNumber(n: '''int''')
 
  d[0][0] = 1
 
  '''for''' i = 1 '''to''' 2n
 
    '''for''' j = 0 '''to''' n
 
      d[i][j] = d[i-1][j-1] + d[i-1][j+1]
 
  '''return''' d[2n][0]
 
  
===Таблица значений===
+
Тогда коэффициент при <tex>z^n</tex> в разложении <tex>G(z)</tex> равен <tex>\dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>, что совпадает с аналитической формулой для чисел Каталана. (<tex>C_n = \dfrac{1}{n + 1} \cdot \dbinom{2n}{n}</tex>) Поэтому <tex>G(z) = \sum\limits_{n = 0}^{\infty} z^n \cdot C_n</tex>, поэтому <tex>G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}</tex> является производящей функцией чисел Каталана.
Найдем значения таблицы для <tex dpi = 120>n</tex> = 4
 
{| class="wikitable"
 
|-
 
!width="20"| i\j
 
!width="40"| 0
 
!width="40"| 1
 
!width="40"| 2
 
!width="40"| 3
 
!width="40"| 4
 
!width="40"| 5
 
!width="40"| 6
 
!width="40"| 7
 
!width="40"| 8
 
|-
 
! 0
 
| 1
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
|-
 
! 1
 
| 0
 
| 1
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
| 0
 
|-
 
! 2
 
| 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
 
|}
 
  
 
==Смотри также==
 
==Смотри также==
<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) Триангуляция полигонов]
+
*[[Числа_Стирлинга_первого_рода|Числа Стирлинга первого рода]]
</wikitex>
+
 
==Источники==
+
*[[Числа_Стирлинга_второго_рода|Числа Стирлинга второго рода]]
<wikitex>
+
 
 +
*[[Числа_Эйлера_I_и_II_рода|Числа Эйлера первого и второго рода]]
 +
 
 +
==Источники информации==
 
*[http://e-maxx.ru/algo/catalan_numbers MAXimal :: algo :: Числа Каталана]
 
*[http://e-maxx.ru/algo/catalan_numbers MAXimal :: algo :: Числа Каталана]
 +
 
*[http://habrahabr.ru/post/165295/ Числа Каталана / Хабрахабр]
 
*[http://habrahabr.ru/post/165295/ Числа Каталана / Хабрахабр]
*[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 Числа Каталана — Википедия]
+
 
 +
*[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 Википедия — Числа Каталана]
 +
 
 
*[http://kvant.mccme.ru/1978/07/chisla_katalana.htm Журнал "Квант"]
 
*[http://kvant.mccme.ru/1978/07/chisla_katalana.htm Журнал "Квант"]
 +
 
*[http://desolt.ru/karimova.html Глава 5. Комбинаторика]
 
*[http://desolt.ru/karimova.html Глава 5. Комбинаторика]
 
</wikitex>
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Текущая версия на 19:37, 4 сентября 2022

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

Определение:
Числа Каталана — последовательность чисел, выражающих: и так далее


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

[math] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, \ldots [/math]

Формулы вычисления чисел Каталана

Рекуррентная формула

[math]C_n = \sum\limits_{i = 0}^{n - 1} C_i C_{n - 1 - i} [/math]

Доказательство

Рекуррентную формулу легко вывести из задачи о правильных скобочных последовательностях.

Пусть [math]X[/math] — произвольная правильная скобочная последовательность длины [math]2n[/math]. Она начинается с открывающейся скобки. Найдем парную ей закрывающуюся скобку и представим последовательность [math]X[/math] в виде: [math]X = (A)B[/math], где [math]A[/math] и [math]B[/math] — тоже правильные скобочные последовательности. Если длина последовательности [math]A[/math] равна [math]2k[/math], то последовательность [math]A[/math] можно составить [math]C_k[/math] способами. Тогда длина последовательности [math]B[/math] равна [math]2(n - k - 1)[/math] и последовательность [math]B[/math] можно составить [math]C_{n - k - 1}[/math] способами. Комбинация любого способа составить последовательность [math]A[/math] с любым способом составить последовательность [math]B[/math] даст новую последовательность [math]X[/math], а величина [math]k[/math] может меняться от [math]0[/math] до [math]n - 1[/math]. Получили рекуррентное соотношение: [math]C_n = C_0 C_{n-1} + C_1 C_{n-2} + \ldots + C_{n-1} C_0 [/math]. Так как [math]C_0 = 1[/math], то последовательность совпадает с числами Каталана.

Аналитическая формула

[math] C_n = \dfrac{1}{n+1} \dbinom {2n} {n} [/math]

Доказательство

Правильной скобочной структуре из [math]n[/math] открывающих и [math]n[/math] закрывающих скобок мы поставим в соответствие путь в квадрате [math][0, n]×[0, n][/math]. Путь начинается в точке [math](0,0)[/math] и заканчивается в точке [math](n, n)[/math]. Открывающей скобке мы сопоставляем горизонтальный отрезок длины [math]1[/math], а закрывающей — вертикальный. Если путь сопоставлен правильной структуре, то ни одна его точка не может лежать выше главной диагонали квадрата. Обратно, такому пути ("правильному пути") сопоставляется правильная скобочная структура. Геометрическое представление правильных скобочных структур позволяет найти выражение для чисел Каталана.

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

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

Каталан2.PNG

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

[math] 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)}) = \dfrac{2n!}{n!n!(n+1)} = \dfrac{1}{n+1} \dbinom {2n} {n} [/math]

Задача разбиения выпуклого [math] n [/math]—угольника на треугольники не пересекающимися диагоналями

Доказательство

Vectorpaint.png

Пусть [math]t_n[/math] — число триангуляций выпуклого [math] (n + 2) [/math]-угольника при [math] n \geqslant 1 [/math]. Положим [math] t_0 = 1 [/math]. Пронумеруем вершины многоугольника, начиная с произвольной против часовой стрелки. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне [math]01[/math] (см. рис.).

Пусть [math]k[/math] — номер третьей вершины этого треугольника. Выделенный треугольник разбивает [math](n + 2)[/math] — угольник на [math]k[/math] — угольник и [math](n-k+3)[/math] — угольник, каждый из которых триангулирован диагоналями. Перенумеруем вершины этих многоугольников против часовой стрелки так, чтобы нумерация вершин в каждом из них начиналась с 0. В результате получим пару триангуляций [math]k[/math]-угольника и [math](n-k+3)[/math] — угольника. Наоборот, каждая пара триангуляций [math]k[/math] — угольника и [math](n-k+3)[/math] — угольника определяет триангуляцию исходного многоугольника. Поэтому [math]t_{n+1} = t_0 t_n + t_1 t_{n-1} + \ldots + t_n t_0 [/math] и поскольку [math]t_0 = 1[/math], последовательность чисел [math]t_n[/math] совпадает с последовательностью Каталана.

Пример

Разбиение выпуклого шестиугольника

Ответ на задачу при [math] n = 3 [/math] тривиален: никаких диагоналей проводить не надо. В четырёхугольнике можно провести любую из двух диагоналей, так что способов два. В пятиугольнике — из любой вершины две диагонали, [math] 5 [/math] способов. При [math] n = 6 [/math] — первый не вполне очевидный ответ: [math] 14 [/math] способов (см. рис.); чтобы не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых к ней примыкают соответственно треугольники [math] BCA, BCF, BCE [/math] и [math] BCD [/math].

Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем [math]5[/math] разных случаев. В первом и последнем из них количество разбиений равно [math]14[/math], ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом случаях при вырезании треугольника семиугольник распадается на треугольник и пятиугольник. В третьем случае семиугольник распадается на два четырёхугольника. Поскольку каждый из них можно разбить двумя способами, получаем [math]2 \cdot 2 = 4[/math] варианта. Итак, семиугольник можно разбить всего [math] 14 + 5 + 2 \cdot 2 + 5 + 14 = 42 [/math] способами. Рассматривая восьмиугольник, аналогично получаем [math] 42 + 14 + 2 \cdot 5 + 5 \cdot 2 + 14 + 42 = 132 [/math] способа.Такие вычисления можно проводить и дальше.

Подсчет чисел Каталана

Числа Каталана просто посчитать с помощью рекуррентной формулы. Для этого понадобится [math]O(n)[/math] памяти и [math]O(n^2)[/math] времени. За [math]O(n)[/math] времени их можно посчитать, если использовать аналитическую формулу. Также из аналитической формулы можно выразить простую реккурентную формулу:

[math] C_n = \dfrac{4n-2}{n+1} C_{n-1} [/math].

Вычисление производящей функции чисел Каталана

Лемма:
[math]\dbinom{\frac{1}{2}}{k} = \dfrac{(-1)^{k - 1}}{(2k - 1) \cdot 4^k} \cdot \dbinom{2k}{k} [/math]
Доказательство:
[math]\triangleright[/math]

[math]\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!}[/math]

[math] = \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!}[/math]

[math]= \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!} [/math]

[math] = \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}[/math]
[math]\triangleleft[/math]


Задача:
Вычислить производящую функцию чисел Каталана


Пусть мы имеем последовательность чисел Каталана [math](C_0, C_1, C_2, \ldots)[/math].

Будем искать её производящую функцию в виде [math]G(z) = \sum\limits_{n = 0}^{\infty} C_n \cdot z^n[/math]

Как известно, рекуррентное соотношение для чисел Каталана имеет вид

[math] C_n= \begin{cases} 1,&\text{если $n = 0$;}\\ \sum\limits_{k = 0}^{n - 1}C_k C_{n - k - 1},&\text{если $n \gt 0$.} \end{cases} [/math]

Домножаем [math]C_n[/math] на [math]z^n[/math], получая

[math] 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 \gt 0$.} \end{cases} [/math]

Суммируя [math]C_n z^n[/math] по всем [math]n[/math] от [math]0[/math] до [math]\infty[/math], получаем:

[math]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}[/math] (так как [math]C_0 = 1[/math] по определению чисел Каталана).

Получили, что [math]G(z) = 1 + \sum\limits_{n = 1}^{\infty}z^n \sum\limits_{k = 0}^{n - 1} C_k C_{n - k - 1}~~~~~ \textbf{(1)}[/math]

Распишем произведение [math]G(z) \cdot G(z)[/math] по определению произведения формальных степенных рядов.

[math]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}[/math]

В последнем выражении выполним сдвиг индексации, положив [math]n' = n + 1[/math]. Тогда имеем: [math]n = n' - 1, n = 0 \Rightarrow n' = 1[/math]. Кроме того, [math]z^n = z^{n' - 1}[/math]. [math]n - k[/math] преобразуется в [math]n' - 1 - k[/math] (так как [math]n' - 1 = n[/math]). Тогда, преобразуя предыдущее выражение, получаем:

[math]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}[/math]

Домножая это произведение на [math]z[/math], получаем

[math]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}[/math]

Тогда

[math]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)}[/math]

Из [math] \textbf{(1)}[/math] и [math]\textbf{(2)}[/math] получаем:

[math]G(z) = 1 + z \cdot G^2(z)[/math]

Преобразуя, получаем квадратное уравнение на [math]G(z) :[/math]

[math]z \cdot G^2(z) - G(z) + 1 = 0[/math]

Из этого квадратного уравнения находим два варианта [math]G(z) :[/math]

[math]G(z) = \dfrac{1 \pm \sqrt{1-4z}}{2z}[/math]

Выберем из двух корней тот, который удовлетворяет определению [math]G(z)[/math] как производящей функции чисел Каталана.

Домножая обе части на [math]2z[/math], получаем [math]G(z) \cdot 2z = 1 \pm \sqrt{1-4z} ~~~~~\textbf{(3)}[/math]

Выберем нужный из двух корней, посчитав значение обеих частей при [math]z = 0[/math]

Из определения производящей функции для чисел Каталана известно, что [math]G(z) = C_0 + C_1 \cdot x + \ldots + C_n \cdot x^n + \ldots[/math], тогда [math]G(0) = C_0 = 1[/math]

Тогда при [math]z = 0[/math] выражение [math]\textbf{(3)}[/math] принимает вид [math]G(0) \cdot 2 \cdot 0 = 1 \pm \sqrt{1-4 \cdot 0}[/math], или [math]0 = 1 \pm 1[/math].

Тогда очевидно, нужно выбрать знак [math]-[/math] в выражении, чтобы при [math]z = 0[/math] левая и правая части были равны.

Тогда [math]G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}[/math]

Проверим, что [math]G(z)[/math] действительно является производящей функцией чисел Каталана. Для этого разложим [math]G(z)[/math] в ряд.

[math]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})[/math]

[math] = \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})[/math]

[math] = \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})[/math]

[math]= \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \dfrac{-1}{-1} \cdot 1- \dfrac{1}{2z} \cdot \sum\limits_{n = 1}^{\infty} (\dfrac{-z^n}{(2n - 1)} \cdot \dbinom{2n}{n}) = \dfrac{1}{2z} - \dfrac{1}{2z} - \dfrac{1}{2z} \cdot \sum\limits_{n = 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})[/math]

[math] = \sum\limits_{n = 1}^{\infty} (\dfrac{z^{n - 1}}{(4n - 2)} \cdot \dbinom{2n}{n}) = \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 \dbinom{2n + 2}{n + 1}) = \sum\limits_{n = 0}^{\infty} (\dfrac{z^{n}}{(4n + 2)} \cdot \dfrac{(2n + 2)!}{(n + 1)! \cdot (n + 1)!}[/math]

[math] = \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})[/math]

[math]= \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} (z^n \cdot \dfrac{1}{n + 1} \cdot \dbinom{2n}{n})[/math]

Тогда коэффициент при [math]z^n[/math] в разложении [math]G(z)[/math] равен [math]\dfrac{1}{n + 1} \cdot \dbinom{2n}{n}[/math], что совпадает с аналитической формулой для чисел Каталана. ([math]C_n = \dfrac{1}{n + 1} \cdot \dbinom{2n}{n}[/math]) Поэтому [math]G(z) = \sum\limits_{n = 0}^{\infty} z^n \cdot C_n[/math], поэтому [math]G(z) = \dfrac{1 - \sqrt{1-4z}}{2z}[/math] является производящей функцией чисел Каталана.

Смотри также

Источники информации