Metoda wyłączeń i włączeń - sekretarka

[k3fe]

Tematów o roztargnionej sekretarce było już kilka, jednak nie potrafię poradzić sobie z tym problemem - a dokładniej z użyciem wzoru wyłączeń i włączeń.

Treść zadania jest taka:

Sekretarka napisała \(\displaystyle{ n}\) listów, które trzeba było wysłać do \(\displaystyle{ n}\) osób. Na każdej kopercie wpisała po jednym adresie, po czym wysłała listy. Obliczyć prawdopodobieństwo, że żaden z adresatów nie otrzyma swojego listu.

Na zajęciach miałem podany taki wzór na zasadę wyłączeń i włączeń:

\(\displaystyle{ \left| \bigcup_{i=1}^{n}A_i \right|= \sum_{i=1}^{n}(-1)^{i-1} \sum_{1\le k_1 < k_2 <... <k_1 \le n}^{}\left| A_{k_1} \cap A_{k_2} \cap ... \cap A_{k_i}\right|}\)

I jeśli dobrze rozumiem, korzystając z tego wzoru muszę wyprowadzić kolejny, odpowiedni dla tego problemu wzór. Przeszukując forum znalazłem taką odpowiedź: (343626.htm#p5135240)

2.
Niech \(\displaystyle{ A_{i_k}}\) oznacza zdarzenie, że list na \(\displaystyle{ i_k}\)-tym miejscu trafi do swojej koperty.
Oczywiście wtedy \(\displaystyle{ P(A_{i_1} \cap ... \cap A_{i_k})=\frac{(n-k)!}{n!}}\)
\(\displaystyle{ B}\) - co najmniej jeden trafi na swoje miejsce. Wtedy
\(\displaystyle{ P(B)=P\left( \bigcup_{k=1}^{n} A_k \right)= \sum_{k=1}^{n}(-1)^{k+1} {n \choose k} \frac{(n-k)!}{n!}}\)

I tutaj pojawia się najważniejsze pytanie: Jak, korzystając z zasady wyłączeń i włączeń otrzymać podobną postać wzoru jak w zacytowanym poście? Nie mam pojęcia skąd bierze się \(\displaystyle{ {n \choose k}}\). Z góry dziękuję za odpowiedź

[jutrvy]

No dobra, chcemy się dowiedzieć, jaka jest szansa, że sekretarka zrobi największą rozwałkę, bo jest roztargniona. No to... Zdarzenie przeciwne policzmy...

Niech \(\displaystyle{ A_i}\) oznacza zdarzenie, że \(\displaystyle{ i}\)-ty list zostanie dobrze zaadresowany, tzn widać chyba, że

\(\displaystyle{ P(A_i) = \frac{(n-1)!}{n!} = \frac{1}{n}}\). Świetnie, to teraz zauważmy, że:

\(\displaystyle{ P(A_i\cap A_j) = \frac{(n-2)!}{n!}}\), bo dwa elementy muszą być wysłane w dobre miejsce \(\displaystyle{ }\)ity i \(\displaystyle{ j}\)-ty element, a reszta nie musi. Rozumując podobnie dochodzimy do wniosku, że:

\(\displaystyle{ P\left(\bigcap_{k=1}^{l}A_{i_k}\right) = \frac{(n-l)!}{n!}}\) - to jest proste.

Super, to teraz korzystając ze wzoru włączeń i wyłączeń pokaż, że:

\(\displaystyle{ P\left(\bigcup_{i=1}^nA_i\right) = \sum_{j=1}^{n}(-1)^{j+1}\cdot\sum_{1\le k_1 <\ldots < k_j\le n}P(A_{k_1}\cap\ldots\cap A_{k_j})}\)

[k3fe]

Dzięki za odpowiedź. Do momentu "to jest proste" wszystko jest zrozumiałe. Tego wzoru jednak nie potrafię pokazać. Rozpisując dla trzech zbiorów widzę, że jest ok, ale nie wiem co i jak mam pokazać gdy jest suma \(\displaystyle{ n}\) zbiorów.

[jutrvy]

Pokaż indukcyjnie

[k3fe]

Ciężko będzie...nie wiem jak z tym ruszyć. Mógłbyś zacząć albo dać jakąś wskazówkę?

[jutrvy]

To dam Ci wskazówkę. Myśl o zdarzeniu, jak o zbiorze złożonym ze zdarzeń elementarnych. Np. zdarzenia, że w rzucie dwoma monetami wyjdzie ci jeden orzeł, to suma następujących zdarzeń elementarnych: (Orzeł, Reszka), (Reszka, Orzeł), (Orzeł, Orzeł). Ok? Jak liczysz prawdopodobieństwo sumy zbiorów i chcesz rozbić na taką jakby sumę prawdopodobieństw, to musisz zadbać o to, żebyś każde zdarzenie elementarne liczył dokładnie raz. Dlatego np \(\displaystyle{ P(A\cup B) = P(A) + P(B) - P(A\cap B)}\), bo w sumie \(\displaystyle{ P(A) + P(B)}\) zdarzenia elementarne, które są w części wspólnej \(\displaystyle{ A\cap B}\) liczysz dwa razy.

Żeby udowodnić ogólny wzór musisz wziąć sobie dowolne zdarzenie elementarne \(\displaystyle{ p\in A_1\cup\ldots\cup A_n}\) i pokazać, że po prawej stronie (tej bardziej skomplikowanej) liczysz to zdarzenie dokładnie raz.

Wskazówka: niech \(\displaystyle{ k\in\NN}\) będzie takie, że \(\displaystyle{ p\in A_1\capA_2\cap\ldots\cap A_k\cap A_{k+1}^c\cap\ldots\cap A_n^c}\) (można założyć, że pierwsze \(\displaystyle{ k}\) zbiorów zawiera \(\displaystyle{ p}\), a reszta nie, bo gdyby tak nie było, to wtedy można sobie te zbiory przenumerować). Wtedy \(\displaystyle{ p}\) jest liczone z plusem w wyrażeniach \(\displaystyle{ P(A_i)}\), dla \(\displaystyle{ 1\le i\le k}\), w wyrażeniach \(\displaystyle{ P(A_i\cap A_j)}\) dla \(\displaystyle{ 1\le i<j\le k}\) jest liczone z minusem, i tak dalej. W sumie \(\displaystyle{ p}\) jest liczony

\(\displaystyle{ \sum_{i=1}^{k} (-1)^{i+1}{k \choose i}}\) razy.

Ile to jest? (Chcielibyśmy, żeby było jeden.)

Jak ot pokażemy, to pokażemy, że każde zdarzenie elementarne liczymy dokładnie raz. Pozdrawiam