Шесть непересекающихся хорд на 12 точках окружности: 132 способа и числа Каталана

Условие

На окружности отмечены 12 точек. Нужно провести 6 отрезков с концами в отмеченных точках так, чтобы никакие два отрезка не имели общих точек: ни общих концов, ни точек пересечения. Сколькими способами это можно сделать? Обобщите ответ на случай 2n точек.

Решение

У шести отрезков 12 концов, и все они должны быть различными. Значит, каждая отмеченная точка служит концом ровно одного отрезка: точки разбиваются на пары, и отрезки, соединяющие пары, не должны пересекаться.

Обозначим через a_n число таких разбиений для 2n точек и положим a₀ = 1 (пустой набор точек можно «разбить» одним способом). Занумеруем точки по часовой стрелке числами 1, 2, …, 2n. Точка 1 соединена с какой-то точкой k. Отрезок 1k делит оставшиеся точки на две дуги: точки 2, …, k − 1 и точки k + 1, …, 2n. Ни один отрезок не может пересекать 1k, поэтому точки каждой дуги разбиваются на пары только между собой. Для этого на каждой дуге должно быть чётное число точек: k − 2 = 2i, где i = 0, 1, …, n − 1. Тогда на дугах 2i и 2(n − 1 − i) точек, и их разбиения выбираются независимо:

a_n = a₀a_n−1 + a₁a_n−2 + … + a_n−1a₀.

Это рекуррентное соотношение для чисел Каталана. Последовательно получаем: a₁ = 1, a₂ = 2, a₃ = 5, a₄ = 14, a₅ = 42, a₆ = 1·42 + 1·14 + 2·5 + 5·2 + 14·1 + 42·1 = 132.

Числа Каталана имеют и явную формулу C_n = C(2n, n)/(n + 1). При n = 6 она даёт 924/7 = 132.

Ответ

132 способа. Для 2n точек ответ равен n-му числу Каталана C(2n, n)/(n + 1).

Проверка

Программа перебрала все разбиения 12 точек на пары: их 11·9·7·5·3·1 = 10 395, и ровно в 132 из них отрезки не пересекаются. Для 2, 4, 6, 8 и 10 точек перебор даёт 1, 2, 5, 14 и 42 — первые числа Каталана.

Типичные ошибки

• Соединять точку 1 с точкой, после которой на дуге остаётся нечётное число точек. Такие дуги нельзя разбить на пары, и эти слагаемые равны нулю.
• Считать все разбиения на пары (10 395) без проверки пересечений.
• Делить ответ на 12, отождествляя картинки, переходящие друг в друга при повороте. Точки отмечены и различимы, поэтому повороты дают разные способы.
• Путать индекс: 12 точек соответствуют C₆, а не C₁₂. Тот же ответ 132 имеет задача о разрезании выпуклого восьмиугольника на треугольники.

Задача по мотивам problems.ru, № 32082. Формулировка и решение — редакция damirock.com.