Tekst źródłowy strony Nieporządek

{{Integracja|Podsilnia|Artykuł [[Podsilnia]] zawiera niektóre fakty podane w tym artykule; ''podsilnia'' sama w sobie jest jedynie nazwą oznaczenia, ''nieporządek'' to pojęcie szersze, które oznaczenie to wykorzystuje}}
[[Plik:n! v !n.svg|thumb|300px|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 [[punkt stały|punktu stałego]]).

Liczbę nieporządków danego n-elementowego zbioru oznacza się symbolem [[Podsilnia|podsilni]] !n, n¡ lub <math>d_n</math> (zwanej również „dolną silnią”){{odn|Graham|Knuth|Patashnik|2006|s=223–229}}.

Problem zliczania nieporządków był rozważany przez [[Pierre Rémond de Montmort|Pierre’a Rémonda de Montmorta]] w 1708{{odn|de Montmort|1708}}{{odn|de Montmort|1713}}; podał on rozwiązanie w 1713, równolegle z [[Nicolaus I Bernoulli|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 <math>i \ne 1</math>. Możliwe są dwie sytuacje:
# Uczeń o numerze ''i'' nie otrzymał sprawdzianu numer 1. Rozdanie sprawdzianów o numerach innych niż ''i'' sprowadza się do problemu z <math>n-1</math> uczniami i <math>n-1</math> sprawdzianami: każda z pozostałych <math>n-1</math> osób ma jeden ''niedozwolony'' numer sprawdzianu (uczniowi o numerze ''i'' nie wolno wziąć sprawdzianu o numerze 1),
# Uczeń o numerze ''i'' dostał sprawdzian numer 1. Ten przypadek redukuje się do problemu dla <math>n-2</math> osób i <math>n-2</math> 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 <math>n-1</math> możliwości dla pierwszego sprawdzianu pozostałe możemy rozdać na <math>{!(n - 1)} + {!(n - 2)}</math> sposobów. To daje równanie rekurencyjne
: <math>!n = (n - 1) ({!(n-1)} + {!(n-2)})</math>

przy warunkach początkowych !0&nbsp;=&nbsp;1 i !1&nbsp;=&nbsp;0.

Identyczna formuła rekurencyjna występuje dla silni (z innymi warunkami startowymi): mamy 0!&nbsp;=&nbsp;1, 1!&nbsp;=&nbsp;1 oraz
: <math>n! = (n - 1) ((n-1)! + (n-2)!).</math>

Podobieństwo to wykorzystuje się do udowadniania związków liczby nieporządków z [[Podstawa logarytmu naturalnego|liczbą e]].

Do wyprowadzenia [[Wzór jawny|wzoru jawnego]] używa się [[Zasada włączeń i wyłączeń|zasady włączeń i wyłączeń]]{{odn|Bobiński|Kourliandtchik|Uscki|2002}}:
: <math>!n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}.</math>

Dowodzi się również poniższe wzory{{odn|Graham|Knuth|Patashnik|2006|s=223–229}}{{odn|Hassani}}:
: <math>!n = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor , \quad n\geq 1,</math>

: <math>!n = \left[ \frac{n!}{e} \right] , \quad n\geq 1,</math>

gdzie <math>\left\lfloor x \right\rfloor</math> jest [[Podłoga i sufit|funkcją podłogi]], a <math>[ x ]</math> zaokrągleniem do najbliższej liczby całkowitej.
: <math>!n = \left\lfloor(e+e^{-1})n!\right\rfloor-\lfloor en!\rfloor , \quad n\geq 2,</math>

: <math>!n = n! - \sum_{i=1}^n {n \choose i} \cdot !(n-i),</math>

Zachodzą również następujące zależności rekurencyjne{{odn|OEIS}}:
: <math>!n = n\left(!(n-1)\right) + (-1)^n.</math>

Poczynając od ''n''&nbsp;=&nbsp;0, liczba nieporządków zbioru ''n''-elementowego wynosi:
: 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... {{OEIS|id=A000166}}.

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 [[Rekurencja|rekurencji]], można pokazać{{odn|Graham|Knuth|Patashnik|2006|s=223–229}}, że
: <math>\lim_{n\to\infty} \frac{!n}{n!} = \frac{1}{e} \approx 0{,}3679\dots</math>

Jest to granica prawdopodobieństw ''p''<sub>''n''</sub> = ''d''<sub>''n''</sub>/''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.

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę |nazwisko=Bobiński |imię=Zbigniew |nazwisko2=Kourliandtchik |imię2=Lev |nazwisko3=Uscki |imię3=Mirosław |tytuł=Miniatury matematyczne. Elementarne metody w kombinatoryce |wydawca=Wydawnictwo Aksjomat |miejsce=Toruń |strony=16–17 |rok=2002 |isbn=83-87329-35-5 |odn=tak}}
* {{Cytuj książkę|nazwisko=Graham|imię=Ronald|nazwisko2=Knuth|imię2=Donald|nazwisko3=Patashnik|imię3=Oren|tytuł=Matematyka konkretna|isbn=978-83-01-14764-8|wydawca=[[Wydawnictwo Naukowe PWN|PWN]]|rok=2006|miejsce=Warszawa|strony=223–229|odn=tak}}
* {{cytuj pismo |nazwisko=Hassani |imię=Mehdi |tytuł=Derangements and Applications |url=https://cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.pdf |czasopismo=Journal of Integer Sequences |wolumin=6 |rok=2003 |numer=03.1.2 |strony=1–8 |odn=tak}}
* {{cytuj książkę |nazwisko=de Montmort |imię=Pierre Rémond |tytuł=Essay d’analyse sur les jeux de hazard |rok=1708 |miejsce=Paryż |wydawca=Jacque Quillau |odn=tak}}
* {{cytuj książkę |nazwisko=de Montmort |imię=Pierre Rémond |tytuł=Seconde Edition, Revue & augmentée de plusieurs Lettres |rok=1713 |miejsce=Paryż |wydawca=Jacque Quillau |odn=tak}}

== Linki zewnętrzne ==
{{Wikisłownik|nieporządek}}
* {{OEIS|id=A000166}}
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/Derangement Derangement]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].

{{Kombinatoryka}}
{{Funkcje matematyczne}}

{{Kontrola autorytatywna}}

[[Kategoria:Kombinatoryka]]
[[Kategoria:Rachunek prawdopodobieństwa]]
[[Kategoria:Teoria punktów stałych]]
[[Kategoria:Ciągi]]