Dane są dodatnie liczby całkowite

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
max123321
Użytkownik
Użytkownik
Posty: 3388
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 975 razy
Pomógł: 3 razy

Dane są dodatnie liczby całkowite

Post autor: max123321 »

Dane są dodatnie liczby całkowite \(\displaystyle{ k,n}\) przy czym \(\displaystyle{ k>n}\). Wykaż, że prawdopodobieństwo wystąpienia cyklu o długości \(\displaystyle{ k}\) w permutacji zbioru \(\displaystyle{ \left[ 2n\right]}\) równe jest \(\displaystyle{ \frac{1}{k}}\).

Jak to zrobić?
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Dane są dodatnie liczby całkowite

Post autor: Premislav »

Na \(\displaystyle{ {n \choose k}}\) sposobów wybierasz elementy, które ustawisz w cykl długości \(\displaystyle{ k}\). Dla ustalonych \(\displaystyle{ k}\) elementów jest \(\displaystyle{ (k-1)!}\) cykli i to może przydałoby się jakoś uzasadnić, bo to kluczowy element zadania: popatrzmy sobie na jakiś element \(\displaystyle{ x}\) w takim cyklu \(\displaystyle{ p}\). Cykl \(\displaystyle{ p}\) permutacji \(\displaystyle{ \tau}\) jest długości \(\displaystyle{ k}\), zatem \(\displaystyle{ x}\) przechodzi na jeden z \(\displaystyle{ k-1}\) pozostałych elementów podzbioru k-elementowego składającego się na cykl. Natomiast \(\displaystyle{ \tau(x)}\) „pod wpływem" \(\displaystyle{ \tau}\) może przejść na jeden z \(\displaystyle{ k-2}\) elementów (nie na \(\displaystyle{ x}\), o ile oczywiście \(\displaystyle{ k>2}\) i nie na \(\displaystyle{ \tau(x)}\)), i tak dalej; na naszym \(\displaystyle{ k}\)-elementowym podzbiorze \(\displaystyle{ \tau^k}\) jest identycznością, no a \(\displaystyle{ p}\) c'est nieporządek, dlatego wystarczy popatrzeć na to, na co przechodzi \(\displaystyle{ x}\) przy składaniu \(\displaystyle{ \tau}\) z samą sobą. Łącznie mamy \(\displaystyle{ (k-1)\cdot (k-2)\ldots 2\cdot 1=(k-1)!}\) możliwości. Może mało naukowo, ale tak to z grubsza wygląda.

Pozostałe elementy permutujemy na \(\displaystyle{ (2n-k)!}\) sposobów (niczego tu nie liczymy z niedomiarem albo nadmiarem, gdyż \(\displaystyle{ 2n-k<k}\), więc nie może powstać kolejny cykl długości \(\displaystyle{ k}\)) i to wszystko mnożymy przez siebie, a potem dzielimy przez liczbę wszystkich permutacji, czyli \(\displaystyle{ (2n)!}\)
Zatem odpowiedzią jest \(\displaystyle{ \frac{{2n\choose k} \ (k-1)!(2n-k)!}{(2n)!}}\) i poskracaj sobie te silnie/symbole Newtona.
ODPOWIEDZ