Nieporządek

permutacja bez punktów stałych

Nieporządekpermutacja elementów zbioru, która nie pozostawia żadnego elementu na swoim oryginalnym miejscu (innymi słowy nie posiada żadnego punktu stałego).

Wykres pokazujący liczbę możliwych permutacji (n!) oraz nieporządków (!n) w miarę wzrostu n.

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”.

Przykład

edytuj

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:

BADC, BCDA, BDAC,
CADB, CDAB, CDBA,
DABC, DCAB, DCBA.

W każdym innym przypadku przynajmniej jeden uczeń otrzyma swój własny sprawdzian.

Zliczanie nieporządków

edytuj

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:

  1. Uczeń o numerze i nie otrzymał sprawdzianu numer 1. Rozdanie sprawdzianów o numerach innych niż i sprowadza się do problemu z   uczniami i   sprawdzianami: każda z pozostałych   osób ma jeden niedozwolony numer sprawdzianu (uczniowi o numerze i nie wolno wziąć sprawdzianu o numerze 1),
  2. Uczeń o numerze i dostał sprawdzian numer 1. Ten przypadek redukuje się do problemu dla   osób i   sprawdzianów (każda z osób poza uczniami 1 oraz i nie może dostać tylko swojego sprawdzianiu).

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:

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... (ciąg   A000166 w OEIS).

Są to kolejne wartości podsilni oraz problemu permutacji z 0 punktami stałymi (patrz niżej).

Granica stosunku nieporządków do permutacji zbioru n-elementowego

edytuj

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.

Uogólnienia

edytuj

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.

Przypisy

edytuj

Bibliografia

edytuj
  • Zbigniew Bobiński, Lev Kourliandtchik, Mirosław Uscki: Miniatury matematyczne. Elementarne metody w kombinatoryce. Toruń: Wydawnictwo Aksjomat, 2002, s. 16–17. ISBN 83-87329-35-5.
  • Ronald Graham, Donald Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: PWN, 2006, s. 223–229. ISBN 978-83-01-14764-8.
  • Mehdi Hassani. Derangements and Applications. „Journal of Integer Sequences”. 6 (03.1.2), s. 1–8, 2003. 
  • Pierre Rémond de Montmort: Essay d’analyse sur les jeux de hazard. Paryż: Jacque Quillau, 1708.
  • Pierre Rémond de Montmort: Seconde Edition, Revue & augmentée de plusieurs Lettres. Paryż: Jacque Quillau, 1713.

Linki zewnętrzne

edytuj