Skarbonki i klucze

[splinter]

Mam do zrobienia takie oto zadanie z kombinatoryki:

Mamy \(\displaystyle{ n}\) skarbonek i \(\displaystyle{ n}\) kluczy, przy czym każdy klucz pasuje do dokładnie jednej skarbonki. Wrzucamy losowo po jednym kluczu do każdej skarbonki, po czym rozbijamy \(\displaystyle{ k}\) skarbonek, \(\displaystyle{ 1 \le k \le n}\). Oblicz prawdopodobieństwo tego, że dzięki temu będzie można otworzyć wszystkie pozostałe skarbonki.

[Mruczek]

Patrz tutaj:

Kod: Zaznacz cały

https://math.stackexchange.com/questions/320485/probability-of-opening-all-piggy-banks

Przed zadaniem pytania warto użyć Google, wpisując hasło zarówno po polsku jak i po angielsku.

[janusz47]

Doświadczenie losowe polega na:

- losowym wrzuceniu po jednym z \(\displaystyle{ n}\) kluczy do każdej z \(\displaystyle{ n}\) skarbonek;
- losowym rozbiciu \(\displaystyle{ k , \ \ 1 \leq k \leq n}\) spośród \(\displaystyle{ n}\) skarbonek.

Model doświadczenia:

\(\displaystyle{ ( \Omega, F, P ):}\)

\(\displaystyle{ \Omega = \left\{ \omega= (1,2,...n)\rightarrow (i_{1}, i_{2}...,i_{n}),i_{1},i_{2},...,i_{n} \in \left \{1,2,...,n\right\} \right\},}\)

\(\displaystyle{ F = 2^{\Omega}}\)

\(\displaystyle{ P(\omega_{i})= \frac{1}{n!},\ \ i=1, 2,...,n}\) (1)

\(\displaystyle{ A}\) - zdarzenie "po rozbiciu \(\displaystyle{ k}\) skarbonek będzie można otworzyć wszystkie pozostałe skarbonki ".

\(\displaystyle{ |A| = S(n, k).}\)

\(\displaystyle{ S(n,k) -}\) liczba permutacji \(\displaystyle{ n}\) - elementowych o dokładnie \(\displaystyle{ k, \ \ 1\leq k \leq n}\) cyklach ( liczba Stirlinga II rodzaju)

Z zależności rekurencyjnych dla liczb Stirlinga

\(\displaystyle{ S(k,k) = k!}\)

\(\displaystyle{ S(n+1, k) = nS(n,k)}\)

\(\displaystyle{ S(n, k) = k!k (k+1)...(n-1)= k (n-1)!}\)

oraz (1), otrzymujemy

\(\displaystyle{ P(A) = \frac{|A|}{|\Omega|}= \frac{S(n,k)}{n!} = \frac{k(n-1)!}{n!} = \frac{k}{n}.}\)

Interpretacja otrzymanego wyniku.

Realizując doświadczenie losowe należy oczekiwać, że w \(\displaystyle{ \frac{k}{n}\cdot 100\%}\) ogólnej liczbie wyników - po rozbiciu \(\displaystyle{ k}\) skarbonek będzie można otworzyć wszystkie pozostałe.

[Mruczek]

\(\displaystyle{ S(n,k) -}\) liczba permutacji \(\displaystyle{ n}\) - elementowych o dokładnie \(\displaystyle{ k, \ \ 1\leq k \leq n}\) cyklach ( liczba Stirlinga II rodzaju)

To są liczby Stirlinga I, a nie II rodzaju.

Powyższe rozwiązanie jest całkowicie błędne. Zależności rekurencyjne są niepoprawne.

[janusz47]

Panie Mruczek proszę przedstawić swoje rozwiązanie, a nie odsyłać do forum Stackexchange czy Google i zapoznać się z literaturą np:

Geoffrey Grimmett, David Stirzaker One Thousand Exercises in Probability. pp. 17. Oxford University Press 2001.

[a4karo]

Realizując doświadczenie losowe należy oczekiwać, że w \(\displaystyle{ \frac{k}{n}\cdot 100\%}\) ogólnej liczbie wyników - po rozbiciu \(\displaystyle{ k}\) skarbonek będzie można otworzyć wszystkie pozostałe.

Przy \(\displaystyle{ n=5}\) i \(\displaystyle{ k=1}\) trudno oczekiwać, że jednym kluczem da się otworzyć pozostałe cztery skarbonki

[janusz47]

Szansa otwarcia jest \(\displaystyle{ 20 \%.}\)

[a4karo]

Przeczytaj jeszcze raz zadanie