ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60448
Темы:    [ Числа Каталана ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Сколько существует способов разрезать выпуклый (n+2)-угольник диагоналями на треугольники?


Решение

  Построим взаимно однозначное соответствие между триангуляциями многоугольника и расстановками скобок в произведении x0x1...xn. Выделим одну из сторон AB  (n+2)-угольника; все остальные стороны занумеруем по порядку символами x0, x1, ..., xn. Каждая проведенная диагональ "отсекает" от многоугольника последовательность сторон, не содержащую AB. Соответствующую часть произведения x0x1...xn заключим в скобки. Всего будет расставлена  n – 1  пара скобок.
  Например, разрезанию шестиугольника на рисунке соответствует расстановка скобок (x0((x1x2)x3))x4.

  Легко видеть, что так получаются все возможные расстановки скобок в произведении.


Ответ

Cn.

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 2
Название Комбинаторика
Тема Комбинаторика
параграф
Номер 5
Название Числа Каталана
Тема Классическая комбинаторика
задача
Номер 02.114

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .