задачка про семейные пары

[vicma]

Есть 10 брачных пар. Их делят на 5 групп по 4 человека в каждой для прогулки на лодках так, чтобы в каждой лодке было по 2 мужчины и 2 женщины. Какова вероятность того, что ни в одной лодке не будет ни одной брачной пары?

Не выходит подсчитать число благоприятных случаев.

[elena_t]

Есть 10 семейных пар. Их розбили на 5 групп по 4 особи для прогулки на лодке так, чтобы в каждой лодке было 2 мужчин и 2 женщины. Какая вероятность того, что в никакой лодке не будет ниодной семейной пары.

Добавлено спустя 15 минут 54 секунды:

что имеется ввиду?

[Jnrty]

Jnrty:

Темы объединены, поскольку содержат один и тот же вопрос.

[PAV]

По сравнению с основной массой задач по вероятности и комбинаторике, о которых тут спрашивают, эта дайствительно является нетривиальной. Мне придумался следующий способ ее решения.

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

Мне кажется, что лодки удобнее будет считать различимыми (пронумерованными). И если поменять местами экипажи двух лодок, то это будет считаться другим вариантом.

Порядок же людей внутри лодки будем считать несущественным.

Будьте внимательны и правильно посчитайте число всех вариантов рассадки при этих условиях.

Число же благоприятных вариантов можно попробовать считать так. Обозначим через $k$ число лодок. Рассаживая в них сначала мужей, а потом жен, получаем, что число благоприятных вариантов равно $A_k\cdot B_k$, где $A_k$ - число способов рассадить мужей по паре в каждую лодку без каких-либо ограничений (это число вычислите сами). После того, как мужья рассажены, мы имеем $2k$ жен, которые нужно рассадить по парам в $k$ лодок, причем для каждой жены существует ровно одна лодка, в которую она садиться не должна (это та, в которой сидит ее муж). Это число я обозначил через $B_k$. Ясно, что оно не зависит от прошедшей ранее рассадки мужей.

Числа $B_k$ можно находить индукцией по $k$. Ясно, что $B_2=1$. Допустим, мы знаем $B_{k-1}$ и хотим найти $B_k$. Сначала посадим в последнюю $k$-ю лодку тех двух жен, которые не должны туда сесть, и рассадим $B_{k-1}$ способами остальных (без нарушения условий рассадки). Затем каждая из женщин в $k$-й лодке меняется местами с какой-то одной другой женщиной.

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

В общем, еще надо хорошенько подумать над этой задачей. Может быть, кто-то предложит более простое решение?

[Henrylee]

Может быть вот так.

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

$$ \frac{(2k)!}{(2!)^k} $$

После этого вычисляем количество случаев рассадки женщин. Делаем следующий финт. Делим всех дам на 2 группы по $k$ человек так, чтобы женщины, чьи мужья сидят в одной лодке оказались в разных группах. Берем первую группу из $k$ женщин и рассаживаем их каждую в одну лодку. При этом для каждой из этих женщин запрещена только одна лодка, причем для каждой своя. Таких способов будет $N_k$. Тогда вторую группу женщин рассаживаем точно по такому принципу, причем для оставшихся $k$ женщин условие точно такое же как и для первой группы, таким образом число нужных рассадок будет $N_k^2$. Остается вычислить $N_k$..

Добавлено спустя 3 минуты 27 секунд:

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

[PAV]

При этом один и тот же вариант рассадки может быть получен разными способами, причем не исключено, что число способов для разных вариантов будет неодинаково.

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

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

Добавлено спустя 7 минут 32 секунды:

По-моему, этим способом все должно получиться, хотя вычисления будут достаточно долгими.

Где это такие задачки дают, интересно?

[Brukvalub]

А не проще ли методом включений и исключений подсчитать вероятность противоположного события?

[PAV]

Brukvalub писал(а):

А не проще ли методом включений и исключений подсчитать вероятность противоположного события?

Да, так тоже можно, наверное. Может быть. Это тоже рекурсивно получается. Только тогда надо соединять их по парам (каждому мужчине приписывать по женщине), а уже потом после рассадки учитывать, что внутри лодки они могут поменяться.

Добавлено спустя 23 минуты 38 секунд:

Хотя нет, так не получится. Если разбивать всех на пары "мужчина-женщина", а затем сажать по две пары в одну лодку, то при этом в зависимости от рассадки количество семейных пар в лодке может увеличиться. А если сразу рассаживать по лодкам, то результат не определяется однозначно только лишь количеством пар. Допустим, у нас три лодки и хотим подсчитать число вариантов, при которых две женщины сидят вместе с мужьями. При этом если они сидят в одной лодке, то оставшиеся должны сесть единственно возможным способом. А если в разных лодках, то для оставшихся есть два способа. При большем числе лодок и допустимых пар там будут возникать все более сложные варианты.

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

На самом деле все получится, если рекуррентно считать числа $B_k(x_0,x_1,x_2)$, где $x_i$ - количество лодок, в которых сидят $i$ семейных пар, $x_0+x_1+x_2=k$. Считать надо много и формулы достаточно громоздкие будут, но все должно получиться.

[maxal]

Пусть у нас есть $2n$ брачных пар и $n$ лодок. Будем считать, что лодки различимы (пронумерованы), а места в лодках нет. Тогда количество всех рассаживаний людей по лодкам (исходов) равно $\left(\frac{(2n)!}{2^n}\right)^2$.

Подсчитаем количество благоприятных исходов, используя принцип включений-исключений. Пусть свойство $P_{ij}$, где $i=1,2,\dots,n$ и $j=1,2,\dots,2n$, состоит в том, что в лодку номер $i$ попадает брачная пара номер $j$. При этом рассаживание будет благоприятным тогда и только тогда, когда оно не удовлетворяет ни одному из свойств $P_{ij}$. Пусть $\mathbb{P}$ - это множество всех свойств, и для любого подмножества $T\subset\mathbb{P}$ число рассаживаний удовлетворяющих свойствам из $T$ равно $N_T$. Тогда по принципу включений-исключений число рассаживаний, не удовлетворяющий никакому свойству из $\mathbb{P}$ равно:

$$\sum_{T\subset\mathbb{P}} (-1)^{|T|} N_T.$$

Попробуем представить эту сумму в удобоваримом виде.

Прежде всего заметим, что если в $T$ больше двух свойств вида $P_{ij}$ для фиксированного $i$, то $N_T=0$ (в лодку не могут сесть больше 2-х пар). Аналогично, если в $T$ больше одного $P_{ij}$ для фиксированного $j$, то $N_T=0$ (каждая пара может сесть только в одну лодку). Для остальных $T$ определим сигнатуру как двухкомпонентный вектор $(m_1,m_2)$, где $m_1 = \#\{ i : \exists !j\ P_{ij}\in T\}$ и $m_2=\#\{ i : \exists j\ne j'\ P_{ij}, P_{ij'}\in T\}$, то есть $m_k$ - это число лодок куда согласно $T$ должно сесть как минимум $k$ брачных пар. Понятно, что если $T$ имеет сигнатуру $(m_1,m_2)$, то $|T|=m_1+2m_2$.

Вычислим $N_T$ для подмножества $T\subset\mathbb{P}$ заданной сигнатуры $(m_1,m_2)$. Понятно, что элементы $T$ однозначно определяют $m_1+m_2$ лодок и $m_1+2m_2$ брачных пар, которые в них сидят. Для оставшихся $2n-m_1-2m_2$ пар остается $n-m_1-m_2$ пустых лодок и $m_1$ лодок, заполненных наполовину (т.е. с одной уже сидящей парой). Поэтому

$$N_T = \left( \frac{(2n-m_1-2m_2)!}{2^{n-m_1-m_2}} \right)^2.$$

Чтобы дать окончательный ответ, осталось подсчитать, а сколько у нас есть подмножеств $T$ заданной сигнатуры $(m_1,m_2)$. Так как $|T|=m_1+2m_2$, то чтобы определить $T$, можно сначала выбрать брачные пары, которым $T$ предписывает сидеть в лодках, потом выбрать $m_1+m_2$ лодок, и наконец распределить выбранные пары по выбранным лодкам. Отсюда мы немедленно получаем, что количество различных $T$ заданной сигнатуры $(m_1,m_2)$ равно

$${2n\choose m_1+2m_2}{n\choose m_1+m_2}{m_1+m_2\choose m_1}\frac{(m_1+2m_2)!}{2^{m_2}}=\frac{(2n)!n!}{(2n-m_1-2m_2)!(n-m_1-m_2)!m_1!m_2!2^{m_2}}.$$

Собирая все вместе, получаем количество благоприятных исходов:

$$\sum_{m_1+m_2\leq n} (-1)^{m_1} \frac{(2n)!n!(2n-m_1-2m_2)!}{(n-m_1-m_2)!m_1!m_2!2^{2n-2m_1-m_2}}.$$

Численные значения для $n=1,2,\dots,10$:

? f(n)=sum(m1=0,n,sum(m2=0,n-m1,(-1)^m1*(2*n)!*n!*(2*n-m1-2*m2)!/(n-m1-m2)!/m1!/m2!/2^(2*n-2*m1-m2)))
? vector(10,n,f(n))
%1 = [0, 6, 900, 748440, 1559930400, 6928346502000, 58160619655538400, 845986566719614320000, 19957466912796971445888000, 724891264860942581350908960000]

Соответственно, для $n=5$ получаем искомую вероятность:

$$\frac{1559930400}{12859560000}=\frac{3439}{28350}$$

[mfh]

$ f(n) / n! / (2n-1)!! = A059072(n) = A000459(n)$
= Number of permutations with no hits on 2 main diagonals
= Penrice Christmas gift numbers; card-matching numbers; dinner-diner matching numbers.
http://www.research.att.com/~njas/sequences/A000459

(2n-1)!! =Double factorial numbers: (2n-1)!! = 1.3.5....(2n-1).
http://www.research.att.com/~njas/sequences/A001147

[maxal]

maxal писал(а):

Численные значения для $n=1,2,\dots,10$:

? f(n)=sum(m1=0,n,sum(m2=0,n-m1,(-1)^m1*(2*n)!*n!*(2*n-m1-2*m2)!/(n-m1-m2)!/m1!/m2!/2^(2*n-2*m1-m2)))
? vector(10,n,f(n))
%1 = [0, 6, 900, 748440, 1559930400, 6928346502000, 58160619655538400, 845986566719614320000, 19957466912796971445888000, 724891264860942581350908960000]

Эта последовательность, а также производная от нее для случая неразличимых лодок, теперь тоже в OEIS: A137801 и A137802.

[Батороев]

Если обозначить семейные пары цифрами от 0 до 9, то рассадив джентельменов, мы получаем 5 лодок с начальными условиями:
$ 15.. $, $26..$, $37..$, $48..$, $59..$.
Теперь чтобы получить благоприятный исход (т.е. несовпадающие пары), нам необходимо рассадить барышен (заполнить последние два разряда цифрами) таким образом, чтобы не получить четырехзначные числа с совпадающими двумя цифрами.
Как мне кажется, вероятность такого исхода намного больше 50%.

[maxal]

Батороев, точная формула для вероятности приведена выше - посчитайте и проверьте, насколько хорошо работает ваша интуиция.

[Батороев]

maxal писал(а):

Соответственно, для $n=5$ получаем искомую вероятность:

$$\frac{1559930400}{12859560000}=\frac{3439}{28350}$$

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

[maxal]

Правильно.