Zavartság - Derangement

N elem lehetséges permutációinak és elromlásainak száma . n ! ( n faktoriális) az n -permutációk száma ; ! n ( n szubfaktorális) a rendellenességek száma -n -permutációk, ahol az összes n elem megváltoztatja kezdeti helyét.

Értéktábla
${\ displaystyle n}$	Permutációk, ${\ displaystyle n!}$	Rendellenességek, ${\ displaystyle! n}$	${\ displaystyle {\ frac {! n} {n!}}}$
0	1 = 1 × 10 0	1 = 1 × 10 0	= 1
1	1 = 1 × 10 0	0	= 0
2	2 = 2 × 10 0	1 = 1 × 10 0	= 0,5
3	6 = 6 × 10 0	2 = 2 × 10 0	330.33333 33333
4	24 = 2,4 × 10 1	9 = 9 × 10 0	= 0,375
5	120 = 1,20 × 10 2	44 = 4,4 × 10 1	.0,36666 66667
6	720 = 7,20 × 10 2	265 = 2,65 × 10 2	360,36805 55556
7	5 040 = 5,04 × 10 3	1 854 ≈ 1,85 × 10 3	.0,36785 71429
8	40 320 ≈4,03 × 10 4	14 833 ≈1,48 × 10 4	360,36788 19444
9	362 880 633,63 × 10 5	133 496 ≈1,33 × 10 5	.0,36787 91887
10	3 628 800 633,63 × 10 6	1 334 961 ≈1,33 × 10 6	.0,36787 94643
11	39 916 800 99 3,99 × 10 7	14 684 570 ≈1,47 × 10 7	360,36787 94392
12	479 001 600 794,79 × 10 8	176 214 841 ≈1,76 × 10 8	.0,36787 94413
13	6 227 020 800 ≈ 6,23 × 10 9	2 290 792 932 ≈2,29 × 10 9	.0,36787 94412
14	87 178 291 200 72 8,72 × 10 10	32 071 101 049 ≈3,21 × 10 10	.0,36787 94412
15	1 307 674 368 000 ≈1.31 × 10 12	481 066 515 734 ≈4,81 × 10 11	.0,36787 94412
16	20 922 789 888 000 ≈ 2,09 × 10 13	7 697 064 251 745 70 7,70 × 10 12	.0,36787 94412
17	355 687 428 096 000 ≈3,56 × 10 14	130 850 092 279 664 ≈1.31 × 10 14	.0,36787 94412
18	6 402 373 705 728 000 40 6,40 × 10 15	2 355 301 661 033 953 36 2,36 × 10 15	.0,36787 94412
19	121 645 100 408 832 000 ≈1,22 × 10 17	44 750 731 559 645 106 ≈4,48 × 10 16	.0,36787 94412
20	2 432 902 008 176 640 000 432,43 × 10 18	895 014 631 192 902 121 95 8,95 × 10 17	.0,36787 94412
21	51 090 942 171 709 440 000 ≈ 5,11 × 10 19	18 795 307 255 050 944 540 ≈ 1,88 × 10 19	.0,36787 94412
22	1 124 000 727 777 607 680 000 .121,12 × 10 21	413 496 759 611 120 779 881 ≈ 4,13 × 10 20	.0,36787 94412
23	25 852 016 738 884 976 640 000 5 2,59 × 10 22	9 510 425 471 055 777 937 262 9,51 × 10 21	.0,36787 94412
24	620 448 401 733 239 439 360 000 20 6,20 × 10 23	228 250 211 305 338 670 494 289 ≈2,28 × 10 23	.0,36787 94412
25	15 511 210 043 330 985 984 000 000 551,55 × 10 25	5 706 255 282 633 466 762 357 224 5,71 × 10 24	.0,36787 94412
26	403 291 461 126 605 635 584 000 000 ≈ 4,03 × 10 26	148 362 637 348 470 135 821 287 825 ≈1,48 × 10 26	.0,36787 94412
27	10 888 869 450 418 352 160 768 000 000 ≈1.09 × 10 28	4 005 791 208 408 693 667 174 771 274 4,01 × 10 27	.0,36787 94412
28	304 888 344 611 713 860 501 504 000 000 053,05 × 10 29	112 162 153 835 443 422 680 893 595 673 .121,12 × 10 29	.0,36787 94412
29	8 841 761 993 739 701 954 543 616 000 000 848,84 × 10 30	3 252 702 461 227 859 257 745 914 274 516 ≈3,25 × 10 30	.0,36787 94412
30	265 252 859 812 191 058 636 308 480 000 000 ≈ 2,65 × 10 32	97 581 073 836 835 777 732 377 428 235 481 9,76 × 10 31	.0,36787 94412

A kombinatorikus matematika , a zavar egy permutáció az elemek egy sor , oly módon, hogy egyetlen eleme jelenik meg az eredeti helyére. Más szóval, a rendellenesség olyan permutáció, amelynek nincs fix pontja .

A száma zavarokat egy sor méretű n ismert, mint a subfactorial a N vagy N- edik elmezavar száma vagy N- th de Montmort számát . A közös használatú alfaktorok jelölései a következők: n, D _n , d _n vagy n ¡.

Ezt meg lehet mutatni! n értéke a legközelebbi egész számot n ! / e, ahol n ! jelöli a faktoriális a n és e jelentése Euler-féle szám .

A zavarok számolásának problémájával először Pierre Raymond de Montmort foglalkozott 1708 -ban; 1713 -ban megoldotta, akárcsak Nicholas Bernoulli nagyjából ugyanebben az időben.

Példa

A 9 eltérés (24 permutációból) kiemelve van

Tegyük fel, hogy egy professzor négy diáknak adott tesztet - A, B, C és D -, és hagyni szeretné, hogy osztályozzák egymás tesztjeit. Természetesen egyetlen tanuló sem értékelheti saját tesztjét. Hányféleképpen adhatta vissza a professzor a teszteket a diákoknak osztályozás céljából, úgy, hogy egyetlen hallgató sem kapta vissza a saját tesztjét? A tesztek visszaküldésére alkalmas 24 lehetséges permutációból (4!)

ABCD ,	AB DC,	A CB D ,	A CDB,	A DBC,	A D C B,
BA CD ,	BADC ,	BCA D ,	BCDA ,	BDAC ,	BD C A,
CAB D ,	CADB ,	C B A D ,	C B DA,	CDAB ,	CDBA ,
DABC ,	DA C B,	D B AC,	D BC A,	DCAB ,	DCBA .

csak 9 eltérés van (fent kék dőlt betűvel látható). Ennek a 4 tagú sorozatnak minden más permutációjában legalább egy tanuló visszakapja saját tesztjét (vastag piros színnel).

A probléma egy másik változata akkor merül fel, amikor megkérdezzük, hogy n különböző betűkkel címzett betűket hogyan lehet n előre megcímzett borítékban elhelyezni, így egyetlen betű sem jelenik meg a helyesen megcímzett borítékban.

Számítási zavarok

Számlálás zavarokat egy sor összege a kalap-ellenőrzés probléma , amelyben az egyik tartja a számos módon, amelyben n kalapok (nevezzük őket h ₁ a h _n ) vissza lehet n ember ( P ₁ a P _n ) olyan, hogy nincs kalap visszakerül a tulajdonosához.

Minden személy kaphat bármely n  - 1 kalapot, ami nem a sajátja. Hívja bármelyik kalapot, P ₁ kapja a h _i -t, és vegye figyelembe h _i tulajdonosát: P _i vagy P ₁ kalapját, h ₁ -et vagy valami mást kap. Ennek megfelelően a probléma két lehetséges esetre oszlik:

1. P _i kalapot kap, amely nem h ₁ . Ez az eset egyenértékű a probléma megoldásával n  - 1 ember és n  - 1 kalap esetén, mivel a P ₁  mellett minden n - 1 ember esetében pontosan egy kalap van a fennmaradó n  - 1 kalap közül, amelyeket esetleg nem kapnak meg (pl. bármelyik P _j mellett P _i , a meg nem kapható kalap h _j , míg P _i esetében h ₁ ).
2. P _i h _{1 -et} kap . Ebben az esetben a probléma csökken n  - 2 fő, és n  - 2 kalapot, mert P ₁ kapott h _i kalapja és P _i kapott h ₁ ' s kalap, és ezzel gyakorlatilag mind ki további megfontolásra.

Mindegyik n  - 1 kalap esetében, amelyeket P ₁ kaphat, a P ₂ ,…, P _n valamennyi kalapot kapó módok száma a két eset számának összege.

Ez megadja a megoldást a kalap-ellenőrzési feladatra: algebrailag megadva a számot! n egy elemhalmaz elfajulásai közül n

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

hol és . ${\ displaystyle! 0 = 1}$${\ displaystyle! 1 = 0}$

A kis hosszúságú zavarok számát az alábbi táblázat tartalmazza.

Vannak más kifejezések is! n , egyenértékű a fenti képlettel. Ezek tartalmazzák

${\ displaystyle! n = n! \ sum _ {i = 0}^{n} {\ frac {(-1)^{i}} {i!}}}$ számára ${\ displaystyle n \ geq 0}$

és

${\ displaystyle! n = \ left [{\ frac {n!} {e}} \ right] = \ left \ lfloor {\ frac {n!} {e}}+{\ frac {1} {2}} \ jobb \ rfloor}$ számára ${\ displaystyle n \ geq 1,}$

ahol a legközelebbi egész függvény és a padlófüggvény . ${\ displaystyle \ left [x \ right]}$${\ displaystyle \ left \ lfloor x \ right \ rfloor}$

Egyéb kapcsolódó képletek közé tartozik

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

${\ displaystyle! n = \ left \ lfloor (e+e^{ -1}) n! \ right \ rfloor -\ lfloor en! \ rfloor, \ quad n \ geq 2,}$

és

${\ displaystyle! n = n!-\ sum _ {i = 1}^{n} {n \ select i} \ cdot {! (ni)}, \ quad \ n \ geq 1.}$

A következő ismétlődés is érvényes:

${\ displaystyle! n = {\ begin {case} 1 & {\ text {if}} n = 0, \\ n \ left (! (n-1) \ right)+(-1)^{n} & { \ text {if}} n> 0. \ vége {esetek}}}$

Bevezetés - kizárás elve

Egy nem -rekurzív képletet is le lehet vezetni az n -halmaz eltéréseinek számára . A definíció szerint n objektum permutációinak halmaza, amely rögzíti a k- ik objektumot. Ezen halmazok i gyűjteményének bármely metszéspontja rögzíti az i objektumok egy adott halmazát, ezért permutációkat tartalmaz . Vannak ilyen gyűjtemény, így a felvétel-kizárási elv hozamok ${\ displaystyle 1 \ leq k \ leq n}$${\ displaystyle S_ {k}}$${\ displaystyle (ni)!}$${\ displaystyle {n \ select i}}$

${\ displaystyle {\ begin {aligned} | S_ {1} \ cup \ cdots \ cup S_ {n} | & = \ sum _ {i} \ left | S_ {i} \ right |-\ sum _ {i < j} \ bal | S_ {i} \ sapka S_ {j} \ jobb |+\ összeg _ {i <j <k} \ bal | S_ {i} \ sapka S_ {j} \ sapka S_ {k} \ jobb |+\ cdots+(-1)^{n+1} \ left | S_ {1} \ cap \ cdots \ cap S_ {n} \ right | \\ & = {n \ select 1} (n-1) !-{n \ select 2} (n-2)!+{n \ select 3} (n-3)!-\ cdots+(-1)^{n+1} {n \ select n} 0! \ \ & = \ összeg _ {i = 1}^{n} (-1)^{i+1} {n \ select i} (ni)! \\ & = n! \ \ sum _ {i = 1} ^{n} {(-1)^{i+1} \ felett i!} \ vége {igazítva}}}$

és mivel a zavar egy permutációja, amely elhagyja sem a n rögzített tárgyak, ez azt jelenti,

${\ displaystyle! n = n!-| S_ {1} \ cup \ cdots \ cup S_ {n} | = n! \ sum _ {i = 0}^{n} {\ frac {(-1)^{ i}} {i!}}.}$

A zavarok számának növekedése n közeledtével ∞

Tól től

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

és

${\ displaystyle e^{x} = \ sum _ {i = 0}^{\ infty} {x^{i} \ over i!}}$

az egyik helyettesítésével azonnal megkapja azt ${\ displaystyle \ texttyle x = -1}$

${\ displaystyle \ lim _ {n \ to \ infty} {! n \ over n!} = \ lim _ {n \ to \ infty} \ sum _ {i = 0}^{n} {\ frac {(- 1)^{i}} {i!}} = E^{-1} \ kb. 0.367879 \ ldots.}$

Ez annak a valószínűsége, hogy nagyszámú objektum véletlenszerűen kiválasztott permutációja zavar. A valószínűség rendkívül gyorsan konvergál ehhez a határhoz, ahogy n növekszik, ezért! n jelentése a legközelebbi egész, hogy n ! / e . A fenti féllogaritmikus grafikon azt mutatja, hogy a zavar gráf elmarad a permutációs grafikon egy majdnem állandó értéket.

Erről a számításról és a fenti korlátról további információk találhatók a véletlenszerű permutációk statisztikáiról szóló cikkben .

Aszimptotikus terjeszkedés a Bell számok tekintetében

Aszimptotikus bővítés száma elváltozások szempontjából Bell számok jelentése a következő:

${\ displaystyle! n = {\ frac {n!} {e}}+\ sum _ {k = 1}^{m} \ left (-1 \ right)^{n+k-1} {\ frac { B_ {k}} {n^{k}}}+O \ bal ({\ frac {1} {n^{m+1}}} \ jobb),}$

ahol bármilyen fix pozitív egész szám van, és a -es Bell számot jelöli . Ezenkívül a nagy O -term implikált állandó nem haladja meg . ${\ displaystyle m}$${\ displaystyle B_ {k}}$${\ displaystyle k}$${\ displaystyle B_ {m+1}}$

Általánosítások

A probleme des találkozók során megkérdezi, hány permutációk egy mérete- n halmaz pontosan k fix pont.

A rendellenességek a korlátozott permutációk szélesebb körének példái. Például a ménage probléma azt kérdezi, hogy ha n ellenkező nemű párok ülnek férfi-nő-férfi-nő -... egy asztal körül, hányféleképpen lehet őket leültetni, hogy senki ne üljön a párja mellé?

Formálisan, adott halmazok A és S , és néhány készletek U és V a surjections A → S , gyakran szeretnék tudni, hogy a párok száma a függvények ( f ,  g ), hogy f van U és g van V és az összes a -ban A , f ( a ) ≠ g ( a ); más szavakkal, ahol minden f és g esetében létezik S range elmozdulása úgy, hogy f ( a ) = φ ( g ( a )).

Egy másik általánosítás a következő probléma:

Hány anagramma van egy adott szó rögzített betű nélkül?

Például egy csak két különböző betűből álló szóra, mondjuk n A és m B betűre, a válasz természetesen 1 vagy 0, aszerint, hogy n = m vagy sem, az egyetlen módja annak, hogy anagrammát képezzünk anélkül fix betűk cseréje az összes a és B , ami akkor lehetséges, ha, és csak akkor, ha n = m . Általánosságban elmondható, hogy az n ₁ betűvel rendelkező X ₁ , n ₂ betűs X ₂ , ..., n _r X _r betűs szó esetén kiderül (a befogadási-kizárási képlet megfelelő használata után ), hogy a válasz a forma:

${\ displaystyle \ int _ {0}^{\ infty} P_ {n_ {1}} (x) P_ {n_ {2}} (x) \ cdots P_ {n_ {r}} (x) e^{- x} \, dx,}$

egy bizonyos szekvencia polinomok P _n , ahol P _n foka n . De a fenti válasz esetén r = 2 ad ortogonalitásának kapcsolatban, ahonnan a P _n „s az Laguerre polinomok ( akár a jele, hogy az könnyen eldönthető).

${\ displaystyle \ int _ {0}^{\ infty} (t-1)^{z} e^{-t} dt}$ a komplex síkban.

Különösen a klasszikus zavarok miatt

${\ displaystyle! n = \ int _ {0}^{\ infty} (x-1)^{n} e^{-x} dx.}$

Számítási komplexitás

Az NP-teljességgel megállapítható, hogy egy adott permutációs csoport (amelyet az adott generációs permutációk halmaza ír le) tartalmaz-e valamilyen rendellenességet.

Hivatkozások

Külső linkek

• Baez, John (2003). - Tévedjünk el! (PDF) .
• Bogart, Kenneth P .; Doyle, Peter G. (1985). "A ménage probléma nem szexista megoldása" .
• Dickau, Robert M. "Derangement diagrams" . Matematikai ábrák a Mathematica segítségével .
• Hassani, Mehdi. "Rendellenességek és alkalmazások" . Journal of Integer Sequence (JIS), 6. kötet, 1. szám, 2003.1.2.
• Weisstein, Eric W . "Rendetlenség" . MathWorld - Wolfram webes forrás.