Nieporządek


Nieporządek w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania Wykres pokazujący liczbę możliwych permutacji (n!) oraz nieporządków (!n) w miarę wzrostu n.

Nieporządekpermutacja 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 symbolem podsilni !n, n¡ lub d n {\displaystyle d_{n}} (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”.

Spis treści

Przykład | edytuj kod

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 kod

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. Musimy wyznaczyć, na ile sposobów żaden uczeń nie otrzyma swojego własnego sprawdzianu. Załóżmy, że pierwszy uczeń otrzymał sprawdzian o numerze i. Może tak się stać na n 1 {\displaystyle n-1} sposobów. Zachodzą teraz dwie możliwości, zależne od tego, czy i-ty uczeń otrzymał sprawdzian 1.:

  1. Uczeń o numerze i nie otrzymał sprawdzianu pierwszego. Nasz przypadek sprowadza się zatem do problemu z n 1 {\displaystyle n-1} uczniami i tyloma sprawdzianami: każda z pozostałych n 1 {\displaystyle n-1} osób ma jeden niedozwolony numer sprawdzianu (uczniowi o numerze i nie wolno wziąć sprawdzianu 1.),
  2. Uczeń o numerze i wziął sprawdzian pierwszy. Teraz przypadek redukuje się do problemu n 2 {\displaystyle n-2} osób i n 2 {\displaystyle n-2} sprawdzianów.

Powyższe rozważania można zawrzeć rekurencją:

! n = ( n 1 ) ( ! ( n 1 ) + ! ( n 2 ) ) , {\displaystyle !n=(n-1)(!(n-1)+!(n-2)),}

przyjmując, że !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 ) ! ) . {\displaystyle 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ń[4]:

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

Dowodzi się również poniższe wzory[1][5]:

! n = n ! e + 1 2 , n 1 , {\displaystyle !n=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor ,\quad n\geq 1,} ! n = n ! e , n 1 , {\displaystyle !n=\left[{\frac {n!}{e}}\right],\quad n\geq 1,}

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

! n = ( e + e 1 ) n ! e n ! , n 2 , {\displaystyle !n=\left\lfloor (e+e^{-1})n!\right\rfloor -\lfloor en!\rfloor ,\quad n\geq 2,} ! n = n ! i = 1 n ( n i ) ! ( n i ) , {\displaystyle !n=n!-\sum _{i=1}^{n}{n \choose i}\cdot !(n-i),}

Zachodzą również następujące zależności rekurencyjne[6]:

! n = n ( ! ( n 1 ) ) + ( 1 ) n . {\displaystyle !n=n\left(!(n-1)\right)+(-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, ... (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 kod

Używając powyższych rekurencji, można pokazać[1], że

lim n ! n n ! = 1 e 0,367 9 {\displaystyle \lim _{n\to \infty }{\frac {!n}{n!}}={\frac {1}{e}}\approx 0{,}3679\dots }

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ść.

Uogólnienia | edytuj kod

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 kod

  1. a b c Graham, Knuth i Patashnik 2006 ↓, s. 223–229.
  2. de Montmort 1708 ↓.
  3. de Montmort 1713 ↓.
  4. Bobiński, Kourliandtchik i Uscki 2002 ↓.
  5. Hassani ↓.
  6. OEIS ↓.

Bibliografia | edytuj kod

  • 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 kod

Na podstawie artykułu: "Nieporządek" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy