Назад
Задача

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

Решение

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

  Например, разрезанию шестиугольника на рисунке соответствует расстановка скобок (x0((x1x2)x3))x4.

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

Cn.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

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