listy i koperty
- vomit
- Użytkownik
- Posty: 82
- Rejestracja: 13 paź 2005, o 17:59
- Płeć: Mężczyzna
- Lokalizacja: ków
- Podziękował: 7 razy
- Pomógł: 16 razy
listy i koperty
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
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
-
- Użytkownik
- Posty: 384
- Rejestracja: 3 maja 2007, o 22:44
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Pomógł: 92 razy
listy i koperty
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.
-
- Użytkownik
- Posty: 261
- Rejestracja: 18 maja 2007, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kruszyny
- Podziękował: 14 razy
- Pomógł: 21 razy
listy i koperty
Nie znam rozwiązania tego zadania ale wiem że tylko jeden list trafi do właściwej osoby
- Emiel Regis
- Użytkownik
- Posty: 1495
- Rejestracja: 26 wrz 2005, o 17:01
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 71 razy
- Pomógł: 225 razy
listy i koperty
Skąd taki wniosek?Nie znam rozwiązania tego zadania ale wiem że tylko jeden list trafi do właściwej osoby
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ć.
-
- Użytkownik
- Posty: 384
- Rejestracja: 3 maja 2007, o 22:44
- Płeć: Kobieta
- Lokalizacja: Wrocław
- Pomógł: 92 razy
listy i koperty
4 listy, 4 koperty, niech 1 list ma trafic do właściwej koperty, sposoby:\(\displaystyle{ P(A)=\frac{(n-k)!}{n!}}\)
1342
1423
3241
4213
2431
4132
3124
2314
8 sposobów a nie 6.
- vomit
- Użytkownik
- Posty: 82
- Rejestracja: 13 paź 2005, o 17:59
- Płeć: Mężczyzna
- Lokalizacja: ków
- Podziękował: 7 razy
- Pomógł: 16 razy
listy i koperty
No wlaśnie, też myślalem na początku, że tak wygląda rozwiązanie.Drizzt pisze: \(\displaystyle{ P(A)=\frac{(n-k)!}{n!}}\)
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
- Użytkownik
- Posty: 1495
- Rejestracja: 26 wrz 2005, o 17:01
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 71 razy
- Pomógł: 225 razy
listy i koperty
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)}\)
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)}\)
- Emiel Regis
- Użytkownik
- Posty: 1495
- Rejestracja: 26 wrz 2005, o 17:01
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 71 razy
- Pomógł: 225 razy
listy i koperty
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.
Później będziemy cały czas na tym bazować także jest to niezbędne.
- vomit
- Użytkownik
- Posty: 82
- Rejestracja: 13 paź 2005, o 17:59
- Płeć: Mężczyzna
- Lokalizacja: ków
- Podziękował: 7 razy
- Pomógł: 16 razy
listy i koperty
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!}}\)
\(\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
- Użytkownik
- Posty: 1495
- Rejestracja: 26 wrz 2005, o 17:01
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 71 razy
- Pomógł: 225 razy
listy i koperty
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.
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.