Условие
Выпуклый девятиугольник разрезают на треугольники диагоналями, которые не пересекаются внутри него. Сколько существует таких разрезаний? Найдите общую формулу для выпуклого (n + 2)-угольника.
Решение
Обозначим через Tm число разрезаний (триангуляций) выпуклого m-угольника A1A2…Am. Удобно считать T2 = 1: «двуугольник» — это просто отрезок, разрезать его не нужно. Ясно, что T3 = 1.
В любой триангуляции сторона A1Am принадлежит ровно одному треугольнику A1AjAm, где 2 ≤ j ≤ m − 1. Этот треугольник отрезает многоугольник A1…Aj (j вершин) и многоугольник Aj…Am (m − j + 1 вершин), которые разрезаются независимо. При j = 2 или j = m − 1 один из кусков вырождается в сторону, и как раз здесь нужно соглашение T2 = 1. Получаем
Tm = T2Tm−1 + T3Tm−2 + … + Tm−1T2.
Если обозначить tn = Tn+2, формула превращается в tn = t0tn−1 + t1tn−2 + … + tn−1t0 с t0 = 1 — это рекуррента чисел Каталана. Значит, Tn+2 = Cn = C(2n, n)/(n + 1).
Значения: треугольник — 1, четырёхугольник — 2, пятиугольник — 5, шестиугольник — 14, семиугольник — 42, восьмиугольник — 132, девятиугольник — 429. Для девятиугольника n = 7: C(14, 7)/8 = 3432/8 = 429.
Попутно полезно заметить: любая триангуляция m-угольника состоит из m − 2 треугольников и использует m − 3 диагонали (сумма углов треугольников равна сумме углов многоугольника, (m − 2)·180°). Для девятиугольника это 7 треугольников и 6 диагоналей.
Ответ
429 способов. Выпуклый (n + 2)-угольник разрезается на треугольники C(2n, n)/(n + 1) способами.
Проверка
В девятиугольнике 27 диагоналей. Программа перебрала все наборы из 6 диагоналей и отобрала наборы попарно непересекающихся: их ровно 429. Для многоугольников с 3, …, 9 вершинами перебор дал 1, 2, 5, 14, 42, 132, 429, а рекуррентная формула — те же числа и 1430 для десятиугольника.
Типичные ошибки
- Перебирать «первую проведённую диагональ». Одна и та же триангуляция содержит несколько диагоналей и будет посчитана много раз.
- Забывать слагаемые с j = 2 и j = m − 1, когда треугольник примыкает к соседней стороне. Без соглашения T2 = 1 ответ получается меньше.
- Думать, что ответ зависит от формы многоугольника. Для выпуклого многоугольника важен только порядок вершин.
Задача по мотивам problems.ru, № 60448. Формулировка и решение — редакция damirock.com.