Рукопожатия

[wpoms.]

Двадцать людей сидят вокруг круглого стола. Сколькими способами шесть пар людей могут могут одновременно обменяться рукопожатиями при условии, что их руки не пересекаются? (Никто не пожимает руку более, чем одному человеку одновременно.)

@темы: Комбинаторика

Comments

[kostyaknop]

Это опять олимпиада какая-нибудь? Ну, тогда кину голый ответ. 125970*132

[Груша Вильямс]

А как 132 найти? Выбираем 12 человек `C_20^12=125970` способами, а посчитать непересекающиеся рукопожатия 12 человек сложно.
2ч - 1р, 4ч - 2р, 6ч - 4р, 8ч - 11р дальше вообще жестоко (если перебором).

[kostyaknop]

Рукопожатий на 6 человек - не 4, а 5 возможностей (12,34,56), (12,36,45), (14,23,56), (16,25,34), (16,23,45).
А дальше - следующие числа Каталана.

[Груша Вильямс]

kostyaknop, да-да, сейчас проснулся, понял, что домножить забыл на n/2, думал количество рукопожатий надо посчитать (невнимательно прочел).
Сейчас посмотрел, для 6 человек 5 способов насчитал, но в попытках придумать рекуррентную формулу забыл про (16,25,34).
Эх, так и не смог рекуррентную формулу придумать (в инете посмотрел)
А задача понравилась, красиво!