Matematyka.pl

Dany jest \(\displaystyle{ n}\)-elementowy zbiór \(\displaystyle{ S}\). Ze zbioru wszystkich podzbiorów zbioru \(\displaystyle{ S}\) losujemy kolejno
ze zwracaniem dwa zbiory (prawdopodobieństwo wylosowania każdego zbioru jest jednakowe).
Oblicz prawdopodobieństwo, że wylosowane zbiory są rozłączne.

\(\displaystyle{ |S|=n \Rightarrow |\mathbb{P}(S)|=2^n}\)

\(\displaystyle{ |\Omega|=2^n \cdot 2^n = 2^{2n}}\)
Bo losujemy ze zwracaniem, czyli możliwym jest wylosowanie 2 razy tego samego zbioru.

Problem mam z liczbą zdarzeń sprzyjających, czyli \(\displaystyle{ A \cap B = \emptyset}\), gdzie \(\displaystyle{ A, B}\) to kolejno pierwszy i drugi wylosowany zbiór.

Wiem, że będzie \(\displaystyle{ n}\) jednoelementowych zbiorów, \(\displaystyle{ n\choose 2}\) 2 elementowych i tak dalej + do tego jeszcze \(\displaystyle{ \emptyset}\) z którym każdy zbiór jest rozłączny, wiem też, że zbiór n-elementowy jest rozłączny tylko z \(\displaystyle{ \emptyset}\).
Dalej nie mam niestety pomysłu, myślałem, aby pójść w stronę wariacji bez powtórzeń, ale to mi też zbyt wiele nie daje (chyba).

Gdy mamy ustalony podzbiór \(\displaystyle{ A}\) k-elementowy (\(\displaystyle{ k \in\left\{ 0,...n\right\}}\)) zbioru n-elementowego, to podzbiorów tegoż zbioru n-elementowego, rozłącznych z \(\displaystyle{ A}\) jest \(\displaystyle{ 2^{n-k}}\). Czyli wydawałoby się, że moc zbioru zdarzeń sprzyjających to
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}2^{n-k}=3^{n}}\). A nieee, głośno "myślę", to pułapka, w ten sposób wiele składników liczymy dwa razy (dajmy na to, mamy jakiś zbiór jednoelementowy i dobieramy do niego podzbiory zbioru \(\displaystyle{ n-1}\)-elementowego, a potem dobieramy jednoelementowe dla \(\displaystyle{ n-1}\)-elementowego). Poprawnie byłoby najwyraźniej

\(\displaystyle{ \sum_{k=0}^{\left\lfloor \frac n 2\right \rfloor}{n \choose k}2^{n-k}}\)

Niestety, ale najwyraźniej nie jest poprawnie, bo Twój wzór dla \(\displaystyle{ n = 2}\) daje

\(\displaystyle{ {2 \choose 0} 2^2 + {2 \choose 1} 2^1 = 4 + 4 = 8}\),

a ja umiem wskazać tylko pięć par: \(\displaystyle{ (\varnothing, \varnothing)}\), \(\displaystyle{ (\varnothing, \{a\})}\), \(\displaystyle{ (\varnothing, \{b\})}\), \(\displaystyle{ (\{a\}, \{b\})}\) i \(\displaystyle{ (\{a, b \}, \varnothing)}\). Nie jest trudnym sprawdzenie, że chcemy mieć

\(\displaystyle{ \frac{3^n + 1}{2}}\).

Dzięki za odpowiedzi

Medea 2 pisze:Nie jest trudnym sprawdzenie, że chcemy mieć

\(\displaystyle{ \frac{3^n + 1}{2}}\).

Sprawdzenie może i nie jest trudnym, ale zauważenie już trochę tak.

Premislav pisze: Czyli wydawałoby się, że moc zbioru zdarzeń sprzyjających to
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k}2^{n-k}=3^{n}}\). A nieee, głośno "myślę", to pułapka, w ten sposób wiele składników liczymy dwa razy (dajmy na to, mamy jakiś zbiór jednoelementowy i dobieramy do niego podzbiory zbioru \(\displaystyle{ n-1}\)-elementowego, a potem dobieramy jednoelementowe dla \(\displaystyle{ n-1}\)-elementowego).

Moim zdaniem to właśnie jest poprawne rozwiązanie. Skoro w treści zadania jest powiedziane, że losujemy kolejno, to znaczy, że na przykład \(\displaystyle{ \left( \left\{1 \right\},\left\{ 2\right\} \right)}\) i \(\displaystyle{ \left( \left\{2 \right\},\left\{ 1\right\} \right)}\) to dwa różne wyniki losowania. Nie zliczamy więc w ten sposób nic podwójnie.

Q.