Теория вероятностей

[Joe Black]

Добрый день! Направьте пожалуйста на правильный путь в данной задаче:

Из совокупности всех подмножеств множества $S = \left\{ 1, 2,..., N \right\} $ по схеме случайного выбора с возвращением выбираются два множества. Найти вероятность того, что эти множества не пересекаются

[arseniiv]

А вероятность того, что две равновероятно выбранные двоичные строки не имеют единиц в одинаковых разрядах, вам будет найти не проще?

[Joe Black]

поподробней пожалуйста

[Dan B-Yallay]

$S\ = \ \{1,2,3,4,5,6,7,8,9,10\}$
$M_1=\{1,2,\ ,\ ,5,\ ,\ ,\ ,\ ,\, \} \to 1100100000$
$M_2=\{\ , \ , 3, \ , \ , \ , \ , \ , \ , \ , \} \to 0010000000$

[Joe Black]

Так, вроде почти понял

-- 05.09.2013, 21:22 --

Вроде получается $ \left( \frac{1}{4} \right)^n $

-- 05.09.2013, 21:29 --

Верно?

[Dan B-Yallay]

Тут надо немного подумать. Как Вы получили это?

[provincialka]

Маловато будет. Получается, что есть только одна пара непересекающихся множеств. Потому что в знаменателе стоит число всех пар множеств.
Я попробовала для небольших $N$. $N=2$, тогда $p=9/16$, при $N=3, p=27/64$.
Считала в уме, могла ошибиться.

[Joe Black]

Опираясь на ваши подмножества:

в $M_1$ выбираем $1$ с вероятностью $\frac{1}{2}$
далее в $M_2$ в том же разряде выбираем $0$ с той же вероятностью и так n раз

[provincialka]

Вы посчитали только для одной пары множеств. Можно ведь выбрать и наоборот.

[Joe Black]

Да, верно

-- 05.09.2013, 22:22 --

Честно говоря, не понимаю как перебрать таким образом все возможные строки

[provincialka]

Что-то не вижу пока, чем строки лучше. Может, просто просуммировать варианты по всем размерам множеств? Например,
первое - пустое, второе - любое - $2^N$ вариантов
в первом 1 элемент ($N$ подмножеств), второе набирается из оставшихся $N-1$, там $2^{N-1}$ подмножество, всего получаем $N\cdot 2^{N-1}$ пар
в первом множестве 2 элемента (таких будет $C_N^2$), во втором - не более $N-2$, всего получаем $C_N^2\cdot 2^{N-2}$
и т.д.

Все складываем и делим на $2^{2N}$.

Сумма легко сворачивается. Впрочем, зная ответ, можно придумать метод подсчета и без суммирования. Пока не напишу, подумайте сами.

[Joe Black]

Что-то похоже на бином Ньютона

-- 05.09.2013, 22:39 --

Тогда имеем $\left( 2+ 1 \right) ^ N = \left( 3 \right) ^ N$

[provincialka]

Он самый. Но можно обойтись и без него. Каждый элемент исходного множества $\{1,2,3...,N\}$ можно пометить одной из 3 меток: $A, B, -$, т.е. принадлежит $A$, принадлежит $B$, не входит ни в одно из них. Такой набор пометок как раз и задает пару непересекающихся множеств. Дальше ясно?

[Joe Black]

А всего вариантов $2^N 2^N = 4 ^ N$

-- 05.09.2013, 22:44 --

То что три метки можно сделать понятно, а как дальше задать подмн-во?

[Dan B-Yallay]

Joe Black в сообщении #760901 писал(а):

То что три метки можно сделать понятно, а как дальше задать подмн-во?

Какое еще подмножество?

provincialka в сообщении #760900 писал(а):

принадлежит $A$, принадлежит $B$, не входит ни в одно из них. Такой набор пометок как раз и задает пару непересекающихся множеств...

$$\{A,-,B,A,B,B,-,-,-,A \} \quad \to \qquad \begin{matrix}A= \{1 & - & - & 4 & - & - & - & - & - & 10\} \\ & & & & & & & & & \\ B= \{ - & - & 3 & - & 5 & 6 & - & - & - & -\} \end{matrix}$$

Так что в числителе будет $3^N$ а знаменатель Вы уже нашли.