Задача 60448

Темы:    [ Числа Каталана ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4 Классы: 8,9,10,11

Условие

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

Решение

  Построим взаимно однозначное соответствие между триангуляциями многоугольника и расстановками скобок в произведении x₀x₁...x_n. Выделим одну из сторон AB  (n+2)-угольника; все остальные стороны занумеруем по порядку символами x₀, x₁, ..., x_n. Каждая проведенная диагональ "отсекает" от многоугольника последовательность сторон, не содержащую AB. Соответствующую часть произведения x₀x₁...x_n заключим в скобки. Всего будет расставлена  n – 1  пара скобок.
  Например, разрезанию шестиугольника на рисунке соответствует расстановка скобок (x₀((x₁x₂)x₃))x₄.

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

Ответ

C_n.

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

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