listy i koperty

[vomit]

Wkladamy losowo N listów do N uprzednio zaadresowanych kopert.
Oblicz prawdopodobienstwo zdarzenia, ze dokładnie k listów trafi do własciwej
koperty.

Zadanie dosyć często spotykane, ale gdzieś w rozumowaniu się gubie i nie ten wynik wychodzi co powinien. Znalazlem na forum zad. ze zdarzeniem polegającym na wlożeniu co najmniej jednego listu do wlaściwej koperty, tutaj żądamy aby zostalo dokladnie k listów wlożonych do odpowiednich kopert.
Z góry dziękuję za pomoc

[sigma_algebra1]

No i pewnie możesz je wykorzystać. Pewnie jest związane z zastosowaniem zasady włączeń i wyłączeń. Zobacz, umiesz pewnie policzyć na ile sposobów można wybrać te k listów które trafią do właściwych kopert. Reszta n-k listów ma nie trafić do właściwych. Czyli można posłużyć się zdarzeniem przeciwnym , że co najmniej jeden z nich trafi do właściwej koperty.

[vomit]

A ktoś może policzyl i wie jaki powinien być ostateczny wynik?

[szablewskil]

Nie znam rozwiązania tego zadania ale wiem że tylko jeden list trafi do właściwej osoby

[Emiel Regis]

Nie znam rozwiązania tego zadania ale wiem że tylko jeden list trafi do właściwej osoby

Skąd taki wniosek?


A rozwiązanie zadania wyglada tak:

A - dokładnie k listów trafi do właściwych osób
\(\displaystyle{ P(A)=\frac{(n-k)!}{n!}}\)

Zadanie, o którym wspominałeś (co najmniej jeden list dotrze) jest znacznie ciekawe [trudniejsze] niż to i polecam się z nim zaznajomić.

[sigma_algebra1]

\(\displaystyle{ P(A)=\frac{(n-k)!}{n!}}\)

4 listy, 4 koperty, niech 1 list ma trafic do właściwej koperty, sposoby:

1342
1423
3241
4213
2431
4132
3124
2314

8 sposobów a nie 6.

[vomit]

\(\displaystyle{ P(A)=\frac{(n-k)!}{n!}}\)

No wlaśnie, też myślalem na początku, że tak wygląda rozwiązanie.
Trochę przemyślalem zadanie i wg mnie rozwiązanie powino wyglądać tak:
\(\displaystyle{ P(A)=\frac{ (n-k-1)!}{n!}}\)
Ktoś może to zweryfikować?

[Emiel Regis]

Słuszna uwaga sigma_algebra1, nawet wiem gdzie błąd zrobiłem, ja policzyłem prawdopodobienstwo ze dokładnie k ustalonych listów trafi do adresata. Wtedy wszystkich ustawień jest n!, wsadzam k listów poprawnie a resztę permutuję na (n-k)! sposobów.
Można to pomnożyć razy \(\displaystyle{ C^k_n}\) ale wtedy zaczną sie zdarzenia dość mocno powtarzać... W tej chwili nie wiem jak to zmodyfikować, pomyślę i jak do czegoś dojdę to napiszę.
W ogóle to podziwiam, o takiej godzinie się wziąść za prawdodobieństwo; )


vomit, napisz może jakieś uzasadnienie bo nie widzę czemu odjęcie jedynki nam zniweluje wszelkie powtórzenia zdarzeń...

[edit]
Nie wygląda na poprawny Twój wzór. Zwróc uwagę co sie dzieje gdy k=n czyli gdy każdy ma dostać swój list. Wiadomo skądinąd że prawdopodobieństwo tego wynosi \(\displaystyle{ \frac{1}{n!}}\) a u Ciebie wychodzi \(\displaystyle{ \frac{(-1)!}{n!}}\).


[edit2]
Mam już poprawny wynik...
\(\displaystyle{ P(A)=\frac{1}{k!}\left(\frac{1}{2!} - \frac{1}{3!}+ \ldots + \frac{(-1)^{n-k}}{(n-k)!}\right)}\)

[vomit]

A móglbyś w miare zrozumiale wyjaśnić skąd ten wynik? Bylbym bardzo wdzięczny

[Emiel Regis]

Dobrze, jednak najpierw policz szczególny przypadek tego zadania, mianowicie prawdopodobieństwo tego że żaden list nie będzie poprawnie wsadzony.
Później będziemy cały czas na tym bazować także jest to niezbędne.

[vomit]

Niech \(\displaystyle{ A_i}\) oznacza zdarzenie, że i-ty list trafi do odpowiedniej koperty. Prawdopodobieństwo, że żaden list nie trafi do dobrej koperty wynosi
\(\displaystyle{ P(A_1' \cap A_2' \cap ... \cap A_n') = P((A_1 \cup ... \cup A_n)') = 1-P(A_1 \cup ... \cup A_n)}\)
Policzenie \(\displaystyle{ P( \bigcup_{i=1}^{n}A_i)}\) to jest właśnie to zadanie o którym pisałem w pierwszym poście. Korzystamy z wzoru włączeń i wyłączeń, otrzymujemy:
\(\displaystyle{ P( \bigcup_{i=1}^{n}A_i) = \sum_{i=1}^{n} (-1)^{i-1} {n \choose i} \frac{(n-i)!}{n!} = 1- \sum_{i=0}^{n} \frac{(-1)^i}{i!}}\)
Zatem prawdopodobieństwo, że żaden list nie trafi do dobrej koperty wynosi
\(\displaystyle{ \sum_{i=0}^{n} \frac{(-1)^i}{i!} = 1-1+ \frac{1}{2!}-\frac{1}{3!}+...+\frac{(-1)^n}{n!}}\)

[Emiel Regis]

Zgadza się, a że to jest to zadanie o ktorym pisales to wiem, inaczej bym Ci go nie dawał; )

Do rzeczy. Wprowadzmy sobie oznaczenia:
\(\displaystyle{ p_{k,n}}\) - prawdopodobieństwo, że dokładnie k osób dostanie swój list
Z Twoich rachunków wiesz już że:
\(\displaystyle{ p_{0,n}=\frac{1}{2!}-\frac{1}{3!}+\ldots+\frac{(-1)^n}{n!}}\)
I wróćmy do początkowego pytania...
Policzmy liczbę zdarzeń sprzyjających zdarzeniu, że dokładnie k osób dostanie swój list:
\(\displaystyle{ {n \choose k}p_{0,n-k}(n-k)!=\frac{n!}{k!}p_{0,n-k}}\)
bo:
1. na \(\displaystyle{ {n \choose k}}\) sposobów wybieramy k osób, które dostaną własny list
2. na \(\displaystyle{ p_{0,n-k}(n-k)!}\) sposobów dajemy cudze listy pozostałym n-k osobom
Ostatecznie otrzymujemy:
\(\displaystyle{ p_{k,n}=\frac{1}{k!}p_{0,n-k}=\frac{1}{k!}\left(\frac{1}{2!}-\frac{1}{3!}+\ldots+ \frac{(-1)^{n-k}}{(n-k)!}\right)}\)

Teraz już powinno być wszystko jasne. Jakby nie patrzec to interesujące sobie wybrałeś zadanie.

[vomit]

ok dzięki, juz wszystko jasne