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

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