Zasugerowano, aby zintegrować ten artykuł z artykułem Podsilnia (dyskusja).
|
Nieporządek – permutacja elementów zbioru, która nie pozostawia żadnego elementu na swoim oryginalnym miejscu (innymi słowy nie posiada żadnego punktu stałego).
Liczbę nieporządków danego n-elementowego zbioru oznacza się symbolem podsilni !n, n¡ lub (zwanej również „dolną silnią”)[1].
Problem zliczania nieporządków był rozważany przez Pierre’a Rémonda de Montmorta w 1708[2][3] ; podał on rozwiązanie w 1713, równolegle z Nicolausem Bernoullim. Stąd też innym określeniem nieporządków jest „liczby de Montmorta”.
Nauczyciel rozdał czterem uczniom – A, B, C i D – sprawdziany i poprosił, aby sami ocenili swoje prace. Oczywiście żaden uczeń nie powinien oceniać swojego własnego testu. Na ile sposobów nauczyciel może rozdać sprawdziany, aby żaden uczeń nie dostał swojego? Z 24 permutacji (4!) zbioru czteroelementowego tylko 9 jest nieporządkami:
W każdym innym przypadku przynajmniej jeden uczeń otrzyma swój własny sprawdzian.
Wykorzystajmy przykład, aby odnaleźć liczbę nieporządków zbioru n-elementowego. Przypuśćmy, że mamy teraz n uczniów oraz n sprawdzianów, oznaczonych od 1 do n. Chcemy policzyć, na ile sposobów możemy rozdać każdej osobie jeden sprawdzian, tak aby żaden uczeń nie otrzymał swojego sprawdzianu. Załóżmy, że pierwszy uczeń otrzymał sprawdzian o numerze . Możliwe są dwie sytuacje:
Stąd dla każdej z możliwości dla pierwszego sprawdzianu pozostałe możemy rozdać na sposobów. To daje równanie rekurencyjne
przy warunkach początkowych !0 = 1 i !1 = 0.
Identyczna formuła rekurencyjna występuje dla silni (z innymi warunkami startowymi): mamy 0! = 1, 1! = 1 oraz
Podobieństwo to wykorzystuje się do udowadniania związków liczby nieporządków z liczbą e.
Do wyprowadzenia wzoru jawnego używa się zasady włączeń i wyłączeń[4] :
Dowodzi się również poniższe wzory[1][5] :
gdzie jest funkcją podłogi, a zaokrągleniem do najbliższej liczby całkowitej.
Zachodzą również następujące zależności rekurencyjne[6] :
Poczynając od n = 0, liczba nieporządków zbioru n-elementowego wynosi:
Są to kolejne wartości podsilni oraz problemu permutacji z 0 punktami stałymi (patrz niżej).
Używając powyższych rekurencji, można pokazać[1], że
Jest to granica prawdopodobieństw pn = dn/n! zdarzeń polegających na tym, że losowo wybrana permutacja zbioru o n elementach jest nieporządkiem. Prawdopodobieństwo to szybko zmierza do stałej granicy, w miarę jak wartości n rosną. Powyższy wykres pokazuje, że krzywa reprezentująca liczbę nieporządków jest przesunięta od krzywej liczby permutacji o mniej więcej stałą wartość.
Przywołując wcześniejszy przykład losowego rozdawania do poprawy sprawdzianów uczniom wnioskujemy, że prawdopodobieństwo, że jakiś uczeń natrafi na swój własny sprawdzian wynosi około 63% i nie zmienia się to wraz ze wzrostem ilości uczniów.
Problem nieporządków można rozszerzyć na pytanie o liczbę permutacji zbioru n-elementowego o dokładnie k punktach stałych.
Nieporządki są przykładem znacznie większej klasy permutacji o pewnych narzuconych ograniczeniach. Problem par małżeńskich zadaje pytanie, na ile sposobów dookoła okrągłego stołu można rozmieścić n par małżeńskich, tak, by osoby przeciwnej płci siedziały na zmianę, a żadna osoba nie siedziała obok swojego współmałżonka.
Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.
Zawartość tej strony pochodzi stąd.