Rendetlenség (permutáció)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. december 20-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A kombinatorikában a rendellenesség fix pontok nélküli permutáció .

Példák

Munka ellenőrzése

Tegyük fel, hogy egy professzor adott négy diáknak (nevezzük őket A-nak, B-nek, C-nek és D-nek) egy tesztet, majd megkérte őket, hogy ellenőrizzék egymással. Természetesen egyetlen diák sem ellenőrizheti saját tesztjét. Hány lehetősége van a professzornak olyan kontrolltesztek szétosztására, amelyekben egyetlen hallgató sem kap saját munkát? A munkába való visszatérés 24 permutációjából (4!) csak 9 rendellenesség alkalmas számunkra:

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

E 4 elem bármely más permutációja esetén legalább egy tanuló ellenőrizni fogja a tesztjét.

Levélprobléma

A rendezetlenség mértékének kiszámítása népszerű probléma a matematika olimpiájában , amely különféle megfogalmazásokban fordul elő, mint például a rendezetlenség , a betűprobléma, a találkozási probléma stb .

Ha a leveleket véletlenszerűen különböző borítékokba helyezzük, mekkora a valószínűsége annak, hogy bármelyik levél a saját borítékába kerül?

n

n

A választ a kifejezés adja meg

1-{\frac {!n}{n!}}\kb 1-{\frac {1}{e}}.

Így a válasz gyengén függ a betűk és a borítékok számától, és megközelítőleg megegyezik a konstanssal . $1-{\frac {1}{e}}\approx 0{,}63212$

Zavargások száma

Az összes n -rendű rendezetlenség számát a befogadás-kizárás elvével számíthatjuk ki, és adjuk meg

!n=n!-{\frac {n!}{1!}}+{\frac {n!}{2!}}-{\frac {n!}{3!}}+\pontok +(-1)^{n}{\frac {n!}{n!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{ k!}},

amelyet n szubfaktoriálisának nevezünk .

A rendellenességek száma kielégíti a rekurzív relációkat $!n=d(n)$

d(n)=(n-1)[d(n-1)+d(n-2)]

és

d(n)=nd(n-1)+(-1)^{n},

hol és . $d(1)=0$ $d(2)=1$

Tekintettel arra, hogy az érték úgy viselkedik , mint . Sőt, amikor a szám kerekítésének eredményeként ábrázolható . $\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$ $!n$ $n$ ${\frac {n!}{e))$ $n>0$ ${\frac {n!}{e))$

Rendetlenség (permutáció)

Példák

Munka ellenőrzése

Levélprobléma

Zavargások száma

Lásd még

Jegyzetek

Linkek