Nieporządek

Błąd przy generowaniu miniatury:

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

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 $d_n$ (zwanej również „dolną silnią”)Szablon:Odn.

Problem zliczania nieporządków był rozważany przez Pierre’a Rémonda de Montmorta w 1708Szablon:OdnSzablon:Odn; 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

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

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 $i\ne 1$. 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 $n-1$ uczniami i $n-1$ sprawdzianami: każda z pozostałych $n-1$ 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 $n-2$ osób i $n-2$ 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 $n-1$ możliwości dla pierwszego sprawdzianu pozostałe możemy rozdać na $!(n-1)+!(n-2)$ sposobów. To daje równanie rekurencyjne

$!n=(n-1)(!(n-1)+!(n-2))$

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

$n!=(n-1)((n-1)!+(n-2)!).$

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ńSzablon:Odn:

$!n=n!\sum _{i=0}^n\frac{(-1{)}^i}{i!}.$

Dowodzi się również poniższe wzorySzablon:OdnSzablon:Odn:

$!n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor ,n\ge 1,$

$!n=\left[\frac{n!}{e}\right],n\ge 1,$

gdzie $\lfloor x\rfloor$ jest funkcją podłogi, a $[x]$ zaokrągleniem do najbliższej liczby całkowitej.

$!n=\lfloor (e+e^{-1})n!\rfloor -\lfloor en!\rfloor ,n\ge 2,$

$!n=n!-\sum _{i=1}^n(\genfrac{}{}{0ex}{}{n}{i})\cdot !(n-i),$

Zachodzą również następujące zależności rekurencyjneSzablon:Odn:

$!n=n(!(n-1))+(-1{)}^n.$

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, ... Szablon: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

Używając powyższych rekurencji, można pokazaćSzablon:Odn, że

$\underset{n\to \mathrm{\infty }}{\lim }\frac{!n}{n!}=\frac{1}{e}\approx 0,3679\dots$

Jest to granica prawdopodobieństw p_n = d_n/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 liczby uczniów.

Uogólnienia

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.

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę
• Szablon:Cytuj pismo
• Szablon:Cytuj książkę
• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:OEIS
• Szablon:Otwarty dostęp Derangement Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].