комбинаторика - Про разбивание на треугольники

Строго говоря, диагонали здесь могут пересекаться, но только в концевых вершинах. Также надо добавить условие выпуклости многоугольника -- в противном случае утверждение будет неверно.

В зависимости о того, какое определение чисел Каталана берётся за основу, доказательство может быть длиннее или короче. Если определять числа $%c_n$% через скобочные выражения, то выводится рекуррентная формула $%c_{n+1}=c_0c_n+c_1c_{n-1}+\cdots+c_nc_0$%. Проверяется, что число способов триангулировать выпуклый $%(n+2)$%-угольник удовлетворяет такому же рекуррентному соотношению. Делается это так: в $%(n+3)$%-угольнике фиксируется некоторая сторона $%AB$%. Она является стороной некоторого треугольника $%ABC$%, входящего в разбиение. Если этот треугольник удалить, то многоугольник распадётся на две части. Одна из них разрезается на $%k$% треугольников, а другая на $%n-k$%. При этом $%k$% принимает значения от $%0$% до $%n$%. Рассуждая по индукции, мы одну часть триангулируем $%c_k$% способами, а другую $%c_{n-k}$% способами. Эти две величины перемножаются, и далее происходит суммирование по $%k$%.

Можно основываться на определении, согласно которому число Каталана $%c_n$% равно количеству способов расставить скобки в произведениии $%x_0x_1\ldots x_n$% (здесь участвует $%n+1$% сомножитель, а число знаков операции произведения равно $%n$%). Например, при $%n=2$% имеется два способа расставить скобки: $%(x_0x_1)x_2$% и $%x_0(x_1x_2)$%.

Разметим стороны $%(n+2)$%-угольника против часовой стрелки буквами $%x_0$%, ..., $%x_n$%, и оставшуюся сторону пометим буквой $%p$% (как произведение). Если какие-то буквы $%x_i$% и $%x_{i+1}$% у нас перемножаются, то проводим в многоугольнике линию, отрезающую треугольник, и помечаем её произведением $%(x_ix_{i+1})$%. Это произведение можно рассматривать как новую "букву", участвующую в дальнейших произведениях. Отсюда нетрудно видеть, что каждой расстановке скобок в произведении однозначно ставится в соответствие триангуляция, и наоборот.