Zaburzenia - Derangement

Liczba możliwych permutacji i odchyleń n elementów. n ! ( n silnia) to liczba n -permutacji; ! n ( n podczynnik) to liczba odchyleń — n -permutacji, w których wszystkie n elementów zmieniają swoje początkowe miejsca.

W kombinatorycznych matematyki , A derangement jest permutacji z elementów zestawu , tak, że żaden element nie występuje w pierwotnej pozycji. Innymi słowy, derangement jest permutacją, która nie ma ustalonych punktów .

Liczba zaburzeniami z zestawu wielkości n jest znany jako subfactorial o n i o n p pomieszania liczby lub n -tego de liczby Montmort . Powszechnie używane notacje dla subfaktorów obejmują ! n, D n , d n lub n .

Można to pokazać! n jest najbliższą liczbą całkowitą n !/ e, gdzie n ! oznacza silni z n i e jest liczba Eulera .

Problem liczenia derangements został po raz pierwszy rozważony przez Pierre'a Raymonda de Montmort w 1708 roku; rozwiązał go w 1713 r., podobnie jak mniej więcej w tym samym czasie Mikołaj Bernoulli .

Przykład

Podkreślono 9 odchyleń (z 24 permutacji)

Załóżmy, że profesor dał test czterem studentom – A, B, C i D – i chce pozwolić im na wzajemne ocenianie testów. Oczywiście żaden uczeń nie powinien oceniać swojego testu. Na ile sposobów profesor może przekazać testy z powrotem uczniom do oceny, tak aby żaden uczeń nie otrzymał z powrotem swojego testu? Z 24 możliwych permutacji (4!) do oddania testów,

ABCD , AB DC, CB D , CDB, DBC, A D C B,
licencjat CD , ZŁE , BCA D , BCDA , BDAC , BD C A,
KABINA D , CADB , C B D , C B DA CDAB , CDBA ,
DBC , DA C B, D B AC, D BC A, DCAB , DCBA .

jest tylko 9 odchyleń (pokazanych niebieską kursywą powyżej). W każdej innej permutacji tego 4-członowego zestawu co najmniej jeden uczeń otrzymuje z powrotem swój własny test (zaznaczony pogrubioną czcionką na czerwono).

Inna wersja problemu pojawia się, gdy pytamy o liczbę sposobów, w jakie n listów, każdy zaadresowany do innej osoby, można umieścić w n zaadresowanych kopertach, aby żadna litera nie pojawiła się w prawidłowo zaadresowanej kopercie.

Liczenie zaburzeń

Liczenie odchyleń zbioru sprowadza się do problemu sprawdzania kapeluszy , w którym bierze się pod uwagę liczbę sposobów, w jakie n kapeluszy (nazwijmy je h 1 do h n ) można zwrócić n osobom ( P 1 do P n ) tak, że nie kapelusz wraca do właściciela.

Każda osoba może otrzymać dowolną z n  − 1 czapek, która nie jest jej własną. Zadzwoń do tego, który kapelusz P 1 otrzyma h i i rozważ właściciela h i : P i otrzymuje albo kapelusz P 1 , h 1 , albo inny. W związku z tym problem dzieli się na dwa możliwe przypadki:

  1. P i otrzymuje kapelusz inny niż h 1 . Ten przypadek jest równoważny rozwiązaniu problemu z n  − 1 osobami i n  − 1 kapeluszami, ponieważ dla każdej z n  − 1 osób oprócz P 1 jest dokładnie jeden kapelusz spośród pozostałych n  − 1 kapeluszy, których mogą nie otrzymać (dla dowolny P j oprócz P í The unreceivable kapelusz jest h j , natomiast dla P i to h 1 ).
  2. P i otrzymuje h 1 . W tym przypadku problem sprowadza się do n  - 2 ludzi i n  - 2 kapelusze, ponieważ P 1 otrzymane h i jest kapelusza i P i otrzymane godzinie h 1 ' y kapelusz skuteczne wprowadzenie zarówno OUT dalszej analizy.

Dla każdego z n  − 1 kapeluszy, które P 1 może otrzymać, liczba sposobów, w jakie P 2 , … , P n może otrzymać kapelusze, jest sumą zliczeń dla dwóch przypadków.

To daje nam rozwiązanie problemu sprawdzania kapeluszy: podana algebraicznie liczba ! n rozbieżności zbioru n -elementowego to

dla ,

gdzie i .

Liczbę odchyleń o małych długościach podano w poniższej tabeli.

Liczba odchyleń zbioru n- elementowego (sekwencja A000166 w OEIS ) dla małych n
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13
! n 1 0 1 2 9 44 265 1854 14,833 133 496 1 334 961 14 684 570 176 214 841 2 290 792 932

Istnieje wiele innych wyrażeń dla ! n , równoważne wzorowi podanemu powyżej. Obejmują one

dla

oraz

dla

gdzie jest najbliższą funkcją całkowitą i jest funkcją podłogi .

Inne powiązane formuły obejmują

oraz

Zachodzi również następująca powtarzalność:

Wyprowadzenie przez zasadę włączenia-wykluczenia

Można również wyprowadzić nierekurencyjny wzór na liczbę rozbieżności n - zbioru . Ponieważ definiujemy jako zbiór permutacji n obiektów, które ustalają k- ty obiekt. Wszelkie skrzyżowanie z kolekcji I tych zestawów rozwiązuje konkretnego zbioru i obiektów, a zatem zawiera permutacji. Są takie kolekcje, więc zasada włączenia-wykluczenia daje

a ponieważ derangement jest permutacją, która nie pozostawia żadnego z n obiektów ustalonych, oznacza to:

Wzrost liczby zaburzeń w miarę zbliżania się do n

Z

oraz

zastępując je natychmiast uzyskuje się, że

Jest to granica prawdopodobieństwa, że losowo wybrana permutacja dużej liczby obiektów jest zaburzeniem. Prawdopodobieństwo zbliża się do tej granicy niezwykle szybko wraz ze wzrostem n , dlatego ! n jest najbliższą liczbą całkowitą n !/ e . Powyższy wykres półlogarytmiczny pokazuje, że wykres derangement jest opóźniony w stosunku do wykresu permutacji o prawie stałą wartość.

Więcej informacji o tym wyliczeniu i powyższym limicie można znaleźć w artykule dotyczącym statystyk permutacji losowych .

Asymptotyczna ekspansja w postaci liczb Bella

Asymptotyczne rozwinięcie liczby derangements w postaci liczb Bella jest następujące:

gdzie jest dowolną stałą dodatnią liczbą całkowitą i oznacza -tą liczbę Bella . Co więcej, stała implikowana przez duże O nie przekracza .

Uogólnienia

Problem rencontres pyta, ile permutacji zbioru o rozmiarze n ma dokładnie k ustalonych punktów.

Derangementy są przykładem szerszego zakresu permutacji ograniczonych. Na przykład problem menażowania pyta, czy n par przeciwnej płci siedzi mężczyzna-kobieta-mężczyzna-kobieta-... wokół stołu, na ile sposobów można je usiąść, aby nikt nie siedział obok jego partnera?

Bardziej formalnie, podanych zestawów A i S , a niektóre z zestawów U i V z surjectionsS , często chce poznać szereg par funkcji ( fg ), tak że F jest U i g jest V , a dla wszystkich a w A , f ( a ) ≠ g ( a ); innymi słowy, gdzie dla każdego f i g istnieje rozbieżność φ S taka, że f ( a ) = φ ( g ( a )).

Kolejnym uogólnieniem jest następujący problem:

Ile jest anagramów bez stałych liter danego słowa?

Na przykład, dla słowa składającego się tylko z dwóch różnych liter, powiedzmy n liter A i m liter B, odpowiedź brzmi oczywiście 1 lub 0 w zależności od tego, czy n = m, czy nie, jako jedyny sposób utworzenia anagramu bez środki litery jest wymiana wszystkich a z B , co jest możliwe tylko wtedy, gdy n = m . W ogólnym przypadku dla słowa o n 1 literach X 1 , n 2 literach X 2 , ..., n r liter X r okazuje się (po poprawnym wykorzystaniu formuły włączeń-wykluczeń ), że odpowiedź ma Formularz:

dla pewnego ciągu wielomianów P n , gdzie P n ma stopień n . Ale przede odpowiedź dla przypadku r = 2 daje relację ortogonalności, skąd P n „s są takie wielomiany Laguerre'a ( aż do znaku, który jest łatwo ustalenia).

w płaszczyźnie złożonej.

W szczególności w przypadku klasycznych zaburzeń

Złożoność obliczeniowa

Jest NP-zupełny , aby określić, czy dana grupa permutacji (opisane przez dany zestaw permutacji, które je wytwarzają) zawiera żadnych zaburzeniami.

Bibliografia

Zewnętrzne linki