докажите что число способов разбить (n+2)-угольник на треугольники непересекающимеся диагоналями равно числу Каталана Cn.

задан 8 Июл '13 18:01

А какое ваше определение чисел Каталана?

(8 Июл '13 18:34) dmg3
10|600 символов нужно символов осталось
1

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

В зависимости о того, какое определение чисел Каталана берётся за основу, доказательство может быть длиннее или короче. Если определять числа $%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})$%. Это произведение можно рассматривать как новую "букву", участвующую в дальнейших произведениях. Отсюда нетрудно видеть, что каждой расстановке скобок в произведении однозначно ставится в соответствие триангуляция, и наоборот.

ссылка

отвечен 9 Июл '13 0:02

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×812

задан
8 Июл '13 18:01

показан
1122 раза

обновлен
9 Июл '13 0:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru