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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Числа Каталана == <wikitex> {{Определение |id = def1 |definition =Числа Каталана {{---}} последовательнос...»)
 
(Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями)
Строка 25: Строка 25:
 
к ней примыкают соответственно треугольники $BCA$, $BCF$, $BCE$ и $BCD$.
 
к ней примыкают соответственно треугольники $BCA$, $BCF$, $BCE$ и $BCD$.
  
Рассмотрим выпуклый $n$-угольник, разрезанный диагоналями на треугольники. Легко доказать, что количество диагоналей проведенных из одной вершины равно $n$−3.
+
Для семиугольника можно выделить одну из сторон и расклассифицировать разрезания в зависимости от того, какой треугольник к этой стороне примыкает. Имеем 5 разных случаев. В первом и последнем из них количество разбиений равно 14,
 +
ибо после отрезания треугольника остаётся шестиугольник. Во втором и четвёртом
 +
случаях при вырезании треугольника семиугольник распадается на треугольник и
 +
пятиугольник. В третьем случае семиугольник распадается на два четырёхугольника. Поскольку каждый из них можно разбить двумя способами, получаем
 +
                                                                2·2 = 4
 +
варианта. Итак, семиугольник можно разбить всего
 +
                                                          14+5+2·2+5+14 = 42
 +
способами. Рассматривая восьмиугольник, аналогично получаем
 +
                                                        42+14+2·5+5·2+14+42 = 132
 +
способа.Такие вычисления можно проводить и дальше.
 
</wikitex>
 
</wikitex>

Версия 22:24, 18 октября 2014

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

<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$.

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

                                                               2·2 = 4

варианта. Итак, семиугольник можно разбить всего

                                                          14+5+2·2+5+14 = 42

способами. Рассматривая восьмиугольник, аналогично получаем

                                                       42+14+2·5+5·2+14+42 = 132

способа.Такие вычисления можно проводить и дальше. </wikitex>