рассадка за круглым столом

[Покоритель курумника]

Добрый день.

Проверьте пожалуйста, правильное ли мое решение?

Задача: За круглый стол садятся n мужчин и n женщин. Какова вероятность того, что гостей можно разбить на непересекающиеся пары, состоящие из мужчины и женщины, сидящих рядом.

Решение: Всего рассадок имеется (2n-1)!. Посчитаем вероятность дополнительного события - что на пары разбить нельзя. Разбить на пары нельзя, если есть 3 мужчины сидящих рядом. Следовательно, число рассадок, при которых на пары разбить нельзя равно

$$\frac{C_{n}^{3}\cdot 3! \cdot (2n-3)!}{2n \cdot ((2n-1)!)}$$

. Т.е. сначала мы выбираем 3 мужчин, потом упорядочиваем их как хотим, потом упорядочиваем как угодно остальных, и делим на 2n - т.к. стол круглый.

Я не уверен, что это решение правильное.

[TOTAL]

$MMFMMFFMFF$ - разбейте на пары.

[ewert]

Не годится. Во-первых, Вы не учли, что эта тройка мужиков может оказаться в любом месте. Во-вторых (более принципиально), Ваши варианты не являются взаимоисключающими.

На мой взгляд, надо так. Разобьем все "хорошие" варианты на два класса: "чётный" (когда пары занимают места (1;2), (3;4), (5;6), ...) и "нечётный" (когда пары занимают места (2;3), (4;5), (6;7), ...). Эти два класса тоже пересекаются, но уже по легко отслеживаемым комбинациям: тем и только тем, в которых мужчины и женщины чередуются.

[Хорхе]

Покоритель курумника писал(а):

Я не уверен, что это решение правильное.

Это хорошо, что Вы не уверены. Потому что оно неправильное.
Во-первых, Ваше первоначальное утверждение (разбить нельзя, если есть три мужчины сидят рядом) не вполне правильно. Конечно, в таком случае нельзя разбить. Но нельзя разбить и в других случаях, скажем, ммжммж....
Во-вторых, одну и ту же рассадку Вы можете посчитать несколько раз.

Вместо этого посчитайте: 1) количество способов разбить мужчин и женщин по парам 2) количество способов разместить эти пары в кольцо 3) количество способов решить в каждой паре, сидит ли мужчина левее женщины или правее
Но это решение не совсем правильно, потому что какие-то рассадки мы посчитали дважды. Это именно те рассадки, когда разбить на пары можно не единственным способом (двумя способами). Это очень легко посчитать -- в конце надо это число отнять от того, что получилось после пункта 3.

Добавлено спустя 1 минуту 59 секунд:

ewert писал(а):

На мой взгляд, надо так. Разобьем все "хорошие" варианты на два класса: "чётный" (когда пары занимают места (1;2), (3;4), (5;6), ...) и "нечётный" (когда пары занимают места (2;3), (4;5), (6;7), ...).

Я думаю, что речь шла о циклических рассадках. То есть две рассадки, отличающиеся поворотом, совпадают. Поэтому это один и тот же класс.

[ewert]

Хорхе в сообщении #159868 писал(а):

Я думаю, что речь шла о циклических рассадках. То есть две рассадки, отличающиеся поворотом, совпадают. Поэтому это один и тот же класс.

Это не имеет значения. Речь о вероятности, поэтому повороты можно как учитывать, так и нет -- смотря что удобнее. Удобнее учитывать (т.е. считать расстановки, совпадающие после поворота, различными).

[Хорхе]

ewert писал(а):

Это не имеет значения. Речь о вероятности, поэтому повороты можно как учитывать, так и нет -- смотря что удобнее. Удобнее учитывать (т.е. считать расстановки, совпадающие после поворота, различными).

Вы правы. Я почему-то решил, что задача посчитать количество способов, а не вероятность

[Покоритель курумника]

Большое спасибо за ответы, TOTAL, ewert и Хорхе.

ewert писал(а):

Не годится. Во-первых, Вы не учли, что эта тройка мужиков может оказаться в любом месте. Во-вторых (более принципиально), Ваши варианты не являются взаимоисключающими.

На мой взгляд, надо так. Разобьем все "хорошие" варианты на два класса: "чётный" (когда пары занимают места (1;2), (3;4), (5;6), ...) и "нечётный" (когда пары занимают места (2;3), (4;5), (6;7), ...). Эти два класса тоже пересекаются, но уже по легко отслеживаемым комбинациям: тем и только тем, в которых мужчины и женщины чередуются.

Правильно ли я понимаю, что число вариантов в четном и в нечетном случае по

$$2^{n} \cdot (n!)^{2}$$

, в случае пересечения 2\cdot (n!)^{2} и ответ

$$\frac{2^{n+1} \cdot (n!)^{2} - 2(n!)^{2}}{(2n)!}$$

?

[ewert]

Да (если я чего не зевнул).

[Хорхе]

Очень похоже на правду.

[Покоритель курумника]

ewert писал(а):

Да (если я чего не зевнул).

По крайней мере для n=1,2 это верно, т.к. вероятность равна 1.

Еще раз спасибо.

[xolodec]

Также очень благодарю всех отвечавших, очень хорошее пояснение.
Мне вот непонятно только одно - почему ответ действительно оказывается правильным, несмотря на то, что мы учитываем случаи циклического сдвига как разные рассадки? То есть учитываем количество этих случаев как в числителе, так и знаменателе.
Есть какой то строгий способ доказать, что такая операция правомерна?