|
|
 |
Условие
На окружности расположены 20 точек. Эти 20 точек попарно соединяются 10
хордами, не имеющими общих концов и непересекающихся.
Сколькими способами это можно сделать?
Решение
Пусть an – количество способов соединить 2n точек на окружности n непересекающимися хордами. Ясно, что a1 = 1 и a2 = 2. Покажем, что
an = an–1 + an–2a1 + an–3a2 + ... + a1an–2 + an–1.
Фиксируем одну из данных 2n точек. Хорда, выходящая из неё, делит окружность на две дуги, причём на каждой дуге расположено чётное число данных точек. Если на одной дуге расположено 2k точек, то на другой – 2(n – k – 1) точек; эти точки можно соединить непересекающимися хордами (не пересекающими первую хорду) an–k–1ak способами. Осталось просуммировать по k от 0 до 2n – 2.
Таким образом, ..., a10 = 16796.
Ответ
16796 способами.
Замечания
Из полученной рекуррентной формулы видно, что числа an – это числа Каталана. Общую формулу для их вычисления см. в задаче 60451.
