n prezentów n osób, szansa że k dostanie swój prezent

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
_radek
Użytkownik
Użytkownik
Posty: 97
Rejestracja: 23 gru 2008, o 16:34
Płeć: Mężczyzna
Lokalizacja: Janów Lubelski
Podziękował: 16 razy
Pomógł: 6 razy

n prezentów n osób, szansa że k dostanie swój prezent

Post autor: _radek »

Zadanie pochodzi z książki Jakubowskiego,
Mamy \(\displaystyle{ n}\) prezentów, oraz \(\displaystyle{ n}\) osób, pogubiliśmy karteczki z podpisami, rozdajemy prezenty losowo i chcemy poznać szansę że dokładnie \(\displaystyle{ k}\) osób dostanie swój prezent.
Chciałem jak w podpowiedzi zrobić z włączeń i wyłączeń ale sumie sam to do niczego sensownego nie doszedłem bo ugrzązłem w tym miejscu:
\(\displaystyle{ \Omega = n!}\)
szansa że \(\displaystyle{ 0}\) osób dostanie no i tu rozważam
\(\displaystyle{ \left|X_{1} \cup ..... \cup X_{n} \right|}\)
Gdzie \(\displaystyle{ X_{i}}\) to sytuacja gdzie \(\displaystyle{ i}\)-ta osoba nie dostanie swojego
Więc
\(\displaystyle{ \left| X_{i}\right| = (n-1)(n-1)!}\) bo jej mogę wybrać na \(\displaystyle{ n-1}\) sposobów a resztę jakkolwiek
\(\displaystyle{ \left| X_{i} \cap X_{j}\right| = {n-2 \choose 2}2(n-2)!+(n-2)!}\)
.
.
.
\(\displaystyle{ j}\) elementów \(\displaystyle{ = {n-j \choose j}(n-j)!+}\)....
no i tu muszę dodać taką sytuację że zostaje mi \(\displaystyle{ j}\) prezentów które należy do \(\displaystyle{ j}\) osób i muszę im je tak rozdać żeby żadna swojego nie dostała, resztę jakkolwiek.... no ale to jak te \(\displaystyle{ j}\) to jest to co mam policzyć ... czyli trochę się zapętliłem...


chyba już czaję...
przekrój elementów to takich kombinacji będzie
\(\displaystyle{ {n \choose j}(n-j)!}\)
do tego wzór i już dalej powinno wyjść
Jytug
Użytkownik
Użytkownik
Posty: 73
Rejestracja: 10 gru 2012, o 12:21
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz
Pomógł: 11 razy

n prezentów n osób, szansa że k dostanie swój prezent

Post autor: Jytug »

Problem sprowadza się do znalezienia liczby tzw. \(\displaystyle{ n}\)-nieporządków, czyli \(\displaystyle{ n}\)-permutacji bez punktów stałych. Można to zrobić ze wzoru włączeń i wyłączeń.

Niech \(\displaystyle{ A_i}\) oznacza zdarzenie, że \(\displaystyle{ i}\)-ta osoba dostała swój prezent. Wtedy


\(\displaystyle{ |A_1 \cup \dots \cup A_n|= \underbrace{|A_1| + \dots + |A_n|}_{n \cdot (n-1)!} - \underbrace{|A_1 \cap A_2| - \dots - |A_{n-1}\cap A_n|}_{{n \choose 2}(n-2)! = \frac{n!}{2!}} + \dots +(-1)^{n+1} \underbrace{|A_1 \cap \dots \cap A_n|}_{1} = \sum\limits_{j=1}^{n}(-1)^{j+1} \frac{n!}{j!}}\).

Policzyliśmy tu permutacje, które mają punkt stały, więc trzeba je odjąć od wszystkich permutacji, zatem liczba \(\displaystyle{ n}\)-nieporządków wynosi:

\(\displaystyle{ n!\left(1 - \sum\limits_{j=1}^{n}(-1)^{j+1} \frac{1}{j!}\right) = n!\cdot \left( \sum\limits_{j=0}^{n}(-1)^{j}\frac{1}{j!} \right) \approx n! \cdot \frac{1}{e}}\) dla dużych \(\displaystyle{ n}\)


Skoro już wiemy, ile jest \(\displaystyle{ n}\)-nieporządków, to możemy rozwiązać zadanie:

Dla \(\displaystyle{ k}\) osób wybieramy ich prezent \(\displaystyle{ {n \choose k}}\), pozostałe miejsce musi zajmować \(\displaystyle{ n-k}\)-nieporządek, a więc moc naszego zdarzenia to:

\(\displaystyle{ {n \choose k}(n-k)!\sum\limits_{j=0}^{n-k}\frac{(-1)^j}{j!}}\).

Prawdopodobieństwo to ta liczba podzielona przez \(\displaystyle{ n!}\)

-- 25 cze 2014, o 22:08 --

Inny sposób na policzenie \(\displaystyle{ k}\)-nieporządków można znaleźć u Knutha, Grahama i Patashnika (ja byłem nim zdziwiony ), przy wykorzystaniu tzw. reguły odwracania:

\(\displaystyle{ \sum\limits_{k=0}^n {n \choose k}(-1)^k a_k = b_n \iff \sum\limits_{k=0}^n {n \choose k}(-1)^k b_k = a_n}\). Dowód Knutha wyglądał mniej więcej tak:

Oznaczmy liczbę \(\displaystyle{ n}\)-nieporządków jako \(\displaystyle{ p(n)}\). Liczba wszystkich \(\displaystyle{ n}\)-permutacji to suma po \(\displaystyle{ k}\) permutacji, które mają dokładnie \(\displaystyle{ n-k}\) punktów stałych (jest ich \(\displaystyle{ {n\choose n-k}p(k)={n \choose k}p(k))}\):

\(\displaystyle{ n! = \sum\limits_{k=0}^{n} {n \choose k} p(k)}\), a więc:

\(\displaystyle{ n! = \sum\limits_{k=0}^{n} (-1)^k(-1)^k{n \choose k} p(k)}\), co na mocy tej reguły daje:

\(\displaystyle{ (-1)^n p(n) = \sum\limits_{k=0}^{n}{n \choose k}(-1)^k k!}\)

\(\displaystyle{ (-1)^n p(n) = n! \sum\limits_{k=0}^{n}\frac{1}{(n-k)!}(-1)^k}\), zamieniając zmienną, po której sumujemy:

\(\displaystyle{ s=n-k}\)
\(\displaystyle{ s=0,1 \dots, n}\)
\(\displaystyle{ k = n-s}\), otrzymujesz

\(\displaystyle{ (-1)^n p(n) = (-1)^n n! \sum\limits_{s=0}^{n}\frac{1}{s!}(-1)^{-s}}\)

\(\displaystyle{ p(n) = n! \sum\limits_{s=0}^{n}\frac{1}{s!}(-1)^{s}}\)
_radek
Użytkownik
Użytkownik
Posty: 97
Rejestracja: 23 gru 2008, o 16:34
Płeć: Mężczyzna
Lokalizacja: Janów Lubelski
Podziękował: 16 razy
Pomógł: 6 razy

n prezentów n osób, szansa że k dostanie swój prezent

Post autor: _radek »

Dzięki
ODPOWIEDZ