Теорвер. Число способов разбиения гостей за столом.

[sleepywalker]

Вот есть задача: За круглый стол рассаживаются в случайном порядке $2n$ гостей. Какова вероятность того, что гостей можно разбить на $n$ непересекающихся пар так, чтобы каждая пара состояла из сидящих рядом мужчины и женщины? Объясните, пожалуйста, почему число всевозможных вариантов разбиения на $n$ пар равно $C_{2n}^n$. То есть $C_{2n}^n$ означает же число способов выбрать $n$ элементов из $2n$. Но тут же в задаче говорится немного про другое, про количество способов разбиения на $n$ пар. Как это понимать?

[arseniiv]

Развернём круглый стол в прямоугольный, вдоль которого все сидят. Теперь чтобы рассадить гостей парами, для каждой пары нужно выбрать мужчину, женщину и один из двух порядков, но плюс ещё надо учесть расщепление одной пары при раскручивании стола в прямой — умножаем всё на два. Но теперь мы некоторые рассадки посчитали по два раза, а именно такие, где пол людей чередуется — их вычтем. Это даёт нам в целом $n! \cdot n! \cdot 2^n \cdot 2 - n! \cdot n! \cdot 2$ из всего $(2 n)!$ рассадок (за развёрнутый стол, не круглый — и так как у нас в обоих случаях симметрии круглого стола не учтены одинаковым образом, то мы нашли ту вероятность, которую надо; работать с круглым столом, позволяющим вращения, здесь наверно не так удобно).

В итоге имеем $2\, n!^2\, (2^n - 1) / (2 n)!$, и теперь-то у нас выделится ваше $C^n_{2 n}$ в знаменателе: $2\, (2^n - 1) / C^n_{2 n}$. Эту пару из числителя и знаменателя наверняка можно осмыслить как частоту каких-то комбинаторных объектов среди других комбинаторных объектов, но совсем не обязательно тех, о которых задача! (Но стоит подумать, какие подойдут и как в них преобразовать исходные — это интересная отдельная задача.) Потому вы зря спросили про $C^n_{2 n}$, не приведя полный ответ: а мало ли как мы его запишем и что туда будет входить.

[alisa-lebovski]

Поскольку здесь важен только пол занимающего место, а не индивидуальность, можно выбрать $n$ из $2n$ мест для женщин, а остальные занять мужчинами, либо наоборот.

[svv]

sleepywalker в сообщении #1510123 писал(а):

Объясните, пожалуйста, почему число всевозможных вариантов разбиения на $n$ пар равно $C_{2n}^n$.

Это не число вариантов разбиения на $n$ пар. Это число всех способов рассадить $n$ женщин и $n$ мужчин на $2n$ мест, если важен только пол. В том числе и таких способов, когда условие задачи не выполняется и на пары разбить не получится.

-- Сб мар 20, 2021 18:36:33 --

Кстати, я вообще не вижу, где бы в задаче могло бы использоваться число вариантов разбиения на $n$ пар (из сидящих рядом мужчины и женщины). Чтобы решить задачу, нужно найти число рассадок, при которых такое разбиение возможно.

С числом же разбиений на пары ситуация тривиальная. Когда гости рассажены, то:
0) либо гостей вообще невозможно разбить на пары (например, если подряд сидят трое гостей одного пола);
1) либо можно разбить единственным способом;
2) либо можно разбить двумя способами, но это только когда женщины и мужчины строго чередуются (таких рассадок всего две).

В случае 1) между рядом сидящими гостями одного пола всегда проходит «граница пар».