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

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

<wikitex>

Определение:

Числа Каталана — последовательность чисел, выражающих: количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями; количество способов соединения $2n$ точек на окружности $n$ не пересекающимися хордами; количество разбиений выпуклого $n$-угольника на треугольники не пересекающимися диагоналями; количество способов полностью разделить скобками $n + 1$ множитель; количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;

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

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ... </wikitex>

Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями

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

Рассмотрим выпуклый $n$-угольник, разрезанный диагоналями на треугольники. Легко доказать, что количество диагоналей проведенных из одной вершины равно $n$−3. </wikitex>