Вероятность пересечения двух множеств

[xolodec]

Есть такая задача:
Из совокупности всех подмножеств множества $S = \{ 1, 2, ..., N\}$ выбирают случайным образом (по схеме с возвращением) два множества $A_1, A_2$. Найти вероятность, что $A_1 \cap A_2 = \varnothing $

Мои рассуждения:
1. Всего различных вариантов $2^N$, куда входит и $\varnothing$.
2. Всего вариантов взять по два множества из совокупности всех подмножеств $C_{2^N}^2 = \frac{2^N !} { (2^{N} - 2)! 2! }$
3. Подсчитаем число удовлетворяющих нас случаев:
3.1 Понятно, что если мы возьмем пустое множество, как один двух элементов, то все остальные подойду под требование задачи, то есть $2^N$.
3.2 пусть мы выбрали одноэлементное множество, как одно из $A_1, A_2$, тогда всего непересекающихся вариантов $ N \cdot ( 2^{N-1} - 1) $, поскольку множество $S = \{ 1, 2, ..., N\}$ без выбранного множества имеет мощность $N-1$ и всевозможные комбинации таким образом $2^{N-1}$. Отсюда следует вычесть пустое множесто, так как мы его уже учли (пункт 3.1)
3.3 Аналогичный расчет следует провести и для каждого выбора двухэлементного, трехэлементного и т.д множества. На каждом iм шаге справедлива будет формула всех комбинаций $C_{N}^i (2^{N-i} -1)$
3.4 Как посчитать сумму всех удовлетворяющих нас комбинаций $\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1)$ я не знаю. Я могу ее посчитать без числа сочетаний, но в смысле решения этой задачи это не поможет.

[popolznev]

xolodec в сообщении #917548 писал(а):

3.4 Как посчитать сумму всех удовлетворяющих нас комбинаций $\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1)$ я не знаю.

$$\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1) = \sum_{i=0}^{N-1} C_{N}^i 2^{N-i} - \sum_{i=0}^{N-1} C_{N}^i = \sum_{i=0}^{N-1} C_{N}^i \cdot 1^i \cdot 2^{N-i} -\sum_{i=0}^{N-1} C_{N}^i \cdot 1^i \cdot 1^{N-i}.$$

[Sonic86]

xolodec в сообщении #917548 писал(а):

3.4 Как посчитать сумму всех удовлетворяющих нас комбинаций $\sum_{i=0}^{N-1} C_{N}^i (2^{N-i} -1)$ я не знаю.

бином Ньютона, слышали?

[Someone]

xolodec в сообщении #917548 писал(а):

1. Всего различных вариантов $2^N$, куда входит и $\varnothing$.

Наверное, не вариантов, а подмножеств. (Впрочем, это, скорее, придирка.)

xolodec в сообщении #917548 писал(а):

2. Всего вариантов взять по два множества из совокупности всех подмножеств $C_{2^N}^2 = \frac{2^N !} { (2^{N} - 2)! 2! }$

Написано ведь:

xolodec в сообщении #917548 писал(а):

по схеме с возвращением

Поэтому сочетания тут ни при чём.

[xolodec]

Благодарю за биномиальную формулу и число сочетаний!
Действительно не уводел первого и ошибся во втором. А также, кажется ошибся в том, что можно выбрать пустое множество, когда мы его уже выбрали первый раз (схема с возвращением), поскольку пересечение двух пустых есть также пустое.

[VAL]

А xolodec,
А стоит ли рассматривать отдельно пустое, одноэлементные etc.
Для того, чтобы множества не пересекались необходимо и достаточно, чтобы ни один элемент не был выбран дважды.

[xolodec]

Этого действительно достаточно, только вот я не могу посчитать как этим способом сосчитать количество комбинаций не пересекающихся множеств.
Это же множество всех подмножеств, как вы прежподагаете, это можно посчитать?

Биномиальной схемой посчитано, с ответом сошлось, благодарю!

[VAL]

xolodec в сообщении #917845 писал(а):

Этого действительно достаточно, только вот я не могу посчитать как этим способом сосчитать количество комбинаций не пересекающихся множеств.
Это же множество всех подмножеств, как вы прежподагаете, это можно посчитать?

А я не предлагаю считать количество непересекающихся множеств.
Я предлагаю считать вероятность того, что множества не пересекаются.
Веорятность того, что данный элемент не вошел в пересечение очевидно равна $1-\left(\frac12\right)^2=\frac34$. Всего элементов $N$. Поэтому искомая вероятность $\left(\frac34\right)^N$. Все.

Цитата:

Биномиальной схемой посчитано, с ответом сошлось, благодарю!

Надеюсь, ответ такой же?

[xolodec]

Да, ответ сошелся. Очень красивое решение, только мне непонятное пока.

Цитата:

Веорятность того, что данный элемент не вошел в пересечение

Если честно, не могу понять: данный элемент, это, видимо, элемент множества S.
Непопадание в какое пересечение вы считаете?

[VAL]

xolodec в сообщении #918026 писал(а):

Да, ответ сошелся. Очень красивое решение, только мне непонятное пока.

Цитата:

Веорятность того, что данный элемент не вошел в пересечение

Если честно, не могу понять: данный элемент, это, видимо, элемент множества S.

Да.
Поочередно перебираем все элементы $S$.
Каждый элемент с вероятностью $\frac12$ попадает в $A$. Аналогично в $B$. Следовательно, с вероятностью $\frac14$ он попадает в пересечение.
Для того, чтобы пересечение было пусто, нужно чтобы ни один элемент из $S$ туда не попал.

Цитата:

Непопадание в какое пересечение вы считаете?

В то, о котором спрашивается в условии.

[xolodec]

$A$ и $B$, насколько я понимаю, есть аналоги множеств $A_1, A_2$, о которой говорилось в задаче.

Цитата:

Каждый элемент с вероятностью $\frac{1}{2}$ попадает в $A$

Всего вариантов выбора $2^N$, вариантов выбора, куда попадет конкретный элемент $2^{N-1}$.
Да, действительно $\frac{1}{2}$.
Благодарю за интересное решение!