Просмотр исходного текста страницы Числа Каталана

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

{{Определение
|id = def1
|definition ='''Числа Каталана''' {{---}} последовательность чисел, выражающих:
*количество [[Дерево_поиска,_наивная_реализация|не изоморфных упорядоченных бинарных деревьев]] с корнем и <tex dpi = 120> n + 1 </tex> листьями
*количество способов соединения <tex dpi = 120> 2n </tex> точек на окружности <tex dpi = 120> n </tex> не пересекающимися хордами
*количество [[Триангуляция_полигонов_(ушная_%2B_монотонная)|триангуляций выпуклого <tex dpi = 120> n </tex>-угольника]]
*количество способов полностью разделить скобками <tex dpi = 120> n + 1 </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 = 150>C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i} </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} + \cdot \cdot \cdot + C_{n-1} C_0 </tex>. Так как <tex dpi = 120>C_0 = 1</tex>, то последовательность совпадает с числами Каталана. Если занести всё под знак суммы, то получаем конечную формулу:

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

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

<tex dpi = 150> C_n = \frac{1}{n+1} \binom {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 {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> (Смотри рис.).
[[Файл:Каталан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> до точки 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>(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 = 150> C_n = \binom {2n} {n} - \binom {2n} {n-1} = \frac{2n!}{n!n!} - \frac{2n!}{(n-1)!(n+1)!} = \frac{2n!}{n!} (\frac{1}{n!} - \frac{1}{(n-1)! (n+1)}) = \frac{2n!}{n!n!(n+1)} = \frac{1}{n+1} \binom {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>. Пронумеруем вершины многоугольника, начиная с произвольной против часовой стрелки. Рассмотрим произвольную триангуляцию и выделим треугольник, примыкающий к стороне 01 (см. рис.).

Пусть <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} + \cdot \cdot \cdot + 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> 5 </tex> способов. При <tex dpi = 120> n = 6 </tex> — первый не вполне очевидный ответ: <tex dpi = 120> 14 </tex> способов (см. рис.); чтобы
не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых
к ней примыкают соответственно треугольники <tex dpi = 120> BCA, BCF, BCE </tex> и <tex dpi = 120> BCD </tex>.

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

==Подсчет чисел Каталана==
Воспользуемся рекуррентной формулой <tex dpi = 150>C_n = \sum_{i = 0}^{n - 1} C_i C_{n - 1 - i} </tex>, описанной выше.

'''Псевдокод:'''
 '''int''' catala_number(n: '''int''')
  '''int''' d[n+1]
  <font color="Green">// создаем массив d, где будут храниться числа Каталана</font>
  d[0] = 1
  '''for''' i = 1 '''to''' n
    '''for''' j = 0 '''to''' i-1
      d[i] += d[j]*d[i-1-j]
  '''return''' d[n]

==Смотри также==
*[[Правильные_скобочные_последовательности|Правильные скобочные последовательности]]

==Источники информации==
*[http://e-maxx.ru/algo/catalan_numbers MAXimal :: algo :: Числа Каталана]

*[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 Числа Каталана — Википедия]

*[http://kvant.mccme.ru/1978/07/chisla_katalana.htm Журнал "Квант"]

*[http://desolt.ru/karimova.html Глава 5. Комбинаторика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Комбинаторика ]]