ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 77913
Темы:    [ Классическая комбинаторика (прочее) ]
[ Числа Каталана ]
[ Системы точек и отрезков (прочее) ]
Сложность: 4+
Классы: 8,9
В корзину
Прислать комментарий

Условие

На окружности расположены 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.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 13
Год 1950
вариант
Класс 7,8
Тур 2
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .