Mail.ruПочтаМой МирОдноклассникиИгрыЗнакомстваНовостиПоискСмотриComboВсе проекты

Комбинаторика соединения точек на окружности

Владислав Сухарев Гуру (3356), закрыт 1 месяц назад
На окружности заданы 2n точек. Сколькими способами можно попарно соединить эти точки n непересекающимися отрезками?
Лучший ответ
Остальные ответы
Павел А. Коржов Просветленный (40478) 1 месяц назад
Отетом на ваш вопрос являются числа Каталана
С (n) = C(2n,n) / (n+1).
Где С (2n,n) - бином. коэфф.
Можно получить рекуррентную форулу:
С (n) = Sum (C(i) C(n-1-i)) по i=0...n-1.
Для этого рассмотреть все возмржные отрезки из одной фиксированной точки. Отрезок будет делить остальные вершины на две группы.
Послед-ть Каталана имеет вид:
1,1,2,5,14,...
Похожие вопросы
Также спрашивают