Poškození - Derangement

Počet možných obměn a odchylek n elementy. n! (n faktoriál) je počet n-permutace; !n (n subfaktoriál) je počet poruch - n-permutace, kde všechny n prvky mění svá počáteční místa.

Tabulka hodnot
${ displaystyle n}$	Permutace, ${ displaystyle n!}$	Derangements, ${ displaystyle! n}$	${ displaystyle { frac {! n} {n!}}}$
0	1 =1×10⁰	1 =1×10⁰	= 1
1	1 =1×10⁰	0	= 0
2	2 =2×10⁰	1 =1×10⁰	= 0.5
3	6 =6×10⁰	2 =2×10⁰	≈0.33333 33333
4	24 =2.4×10¹	9 =9×10⁰	= 0.375
5	120 =1.20×10²	44 =4.4×10¹	≈0.36666 66667
6	720 =7.20×10²	265 =2.65×10²	≈0.36805 55556
7	5 040 ≈5.04×10³	1 854 ≈1.85×10³	≈0.36785 71429
8	40 320 ≈4.03×10⁴	14 833 ≈1.48×10⁴	≈0.36788 19444
9	362 880 ≈3.63×10⁵	133 496 ≈1.33×10⁵	≈0.36787 91887
10	3 628 800 ≈3.63×10⁶	1 334 961 ≈1.33×10⁶	≈0.36787 94643
11	39 916 800 ≈3.99×10⁷	14 684 570 ≈1.47×10⁷	≈0.36787 94392
12	479 001 600 ≈4.79×10⁸	176 214 841 ≈1.76×10⁸	≈0.36787 94413
13	6 227 020 800 ≈6.23×10⁹	2 290 792 932 ≈2.29×10⁹	≈0.36787 94412
14	87 178 291 200 ≈8.72×10¹⁰	32 071 101 049 ≈3.21×10¹⁰	≈0.36787 94412
15	1 307 674 368 000 ≈1.31×10¹²	481 066 515 734 ≈4.81×10¹¹	≈0.36787 94412
16	20 922 789 888 000 ≈2.09×10¹³	7 697 064 251 745 ≈7.70×10¹²	≈0.36787 94412
17	355 687 428 096 000 ≈3.56×10¹⁴	130 850 092 279 664 ≈1.31×10¹⁴	≈0.36787 94412
18	6 402 373 705 728 000 ≈6.40×10¹⁵	2 355 301 661 033 953 ≈2.36×10¹⁵	≈0.36787 94412
19	121 645 100 408 832 000 ≈1.22×10¹⁷	44 750 731 559 645 106 ≈4.48×10¹⁶	≈0.36787 94412
20	2 432 902 008 176 640 000 ≈2.43×10¹⁸	895 014 631 192 902 121 ≈8.95×10¹⁷	≈0.36787 94412
21	51 090 942 171 709 440 000 ≈5.11×10¹⁹	18 795 307 255 050 944 540 ≈1.88×10¹⁹	≈0.36787 94412
22	1 124 000 727 777 607 680 000 ≈1.12×10²¹	413 496 759 611 120 779 881 ≈4.13×10²⁰	≈0.36787 94412
23	25 852 016 738 884 976 640 000 ≈2.59×10²²	9 510 425 471 055 777 937 262 ≈9.51×10²¹	≈0.36787 94412
24	620 448 401 733 239 439 360 000 ≈6.20×10²³	228 250 211 305 338 670 494 289 ≈2.28×10²³	≈0.36787 94412
25	15 511 210 043 330 985 984 000 000 ≈1.55×10²⁵	5 706 255 282 633 466 762 357 224 ≈5.71×10²⁴	≈0.36787 94412
26	403 291 461 126 605 635 584 000 000 ≈4.03×10²⁶	148 362 637 348 470 135 821 287 825 ≈1.48×10²⁶	≈0.36787 94412
27	10 888 869 450 418 352 160 768 000 000 ≈1.09×10²⁸	4 005 791 208 408 693 667 174 771 274 ≈4.01×10²⁷	≈0.36787 94412
28	304 888 344 611 713 860 501 504 000 000 ≈3.05×10²⁹	112 162 153 835 443 422 680 893 595 673 ≈1.12×10²⁹	≈0.36787 94412
29	8 841 761 993 739 701 954 543 616 000 000 ≈8.84×10³⁰	3 252 702 461 227 859 257 745 914 274 516 ≈3.25×10³⁰	≈0.36787 94412
30	265 252 859 812 191 058 636 308 480 000 000 ≈2.65×10³²	97 581 073 836 835 777 732 377 428 235 481 ≈9.76×10³¹	≈0.36787 94412

v kombinační matematika, a vykolejení je permutace prvků a soubor, takže se žádný prvek neobjeví na své původní pozici. Jinými slovy, odchylka je permutace, která nemá žádné pevné body.

Počet odchylek sady velikosti n je známý jako dílčí faktor z n nebo n-th číslo poruchy nebo n-th de Montmort číslo. Mezi poznámky k běžně používaným podfaktoriálům patří!n, D_n, d_nnebo n¡.^[1]^[2]

Jeden to může ukázat!n se rovná nejbližšímu celému číslu n!/E, kde n! označuje faktoriál z n a E je Eulerovo číslo.

Problém počítání odchylek poprvé zvážil Pierre Raymond de Montmort^[3] v roce 1708; vyřešil to v roce 1713, stejně jako to udělal Nicholas Bernoulli přibližně ve stejnou dobu.

Příklad

Zvýrazněno je 9 odchylek (z 24 permutací)

Předpokládejme, že profesor dal test 4 studentům - A, B, C a D - a chce je nechat hodnotit navzájem testy. Žádný student by samozřejmě neměl hodnotit vlastní test. Kolik způsobů, jak mohl profesor předat testy zpět studentům ke klasifikaci, aby žádný student nedostal zpět svůj vlastní test? Mimo 24 možných permutací (4!) Za předání testů zpět,

abeceda,	ABDC,	ACBD,	ACDB,	ADBC,	ADCB,
BACD,	BADC,	BCAD,	BCDA,	BDAC,	BDCA,
KABINAD,	CADB,	CBAD,	CBDA,	CDAB,	CDBA,
DABC,	DACB,	DBAC,	Dpřed naším letopočtemA,	DCAB,	DCBA.

existuje pouze 9 odchylek (zobrazených modrou kurzívou výše). V každé další permutaci této čtyřčlenné sady získá alespoň jeden student zpět svůj vlastní test (zobrazeno tučně červeně).

Další verze problému vyvstává, když žádáme o řadu způsobů n lze vkládat dopisy, z nichž každý je adresován jiné osobě n předem adresované obálky, aby se ve správně adresované obálce neobjevilo žádné písmeno.

Počítání odchylek

Počítání odchylek sady odpovídá částce známé jako problém s kloboukem,^[4] ve kterém se zvažuje počet způsobů, jakými n klobouky (zavolej jim h₁ přes h_n) lze vrátit na n lidé (P₁ přes P_n) tak, aby se žádný klobouk nedostal zpět ke svému majiteli.

Každá osoba může obdržet kterýkoli z těchto dokumentů n - 1 klobouk, který není jejich vlastní. Volejte jakýkoli klobouk P₁ přijímá h_i a zvažte h_iVlastník: P_i přijímá buď P₁klobouk, h₁nebo nějaké jiné. Podle toho se problém rozděluje do dvou možných případů:

P_i dostává jiný klobouk než h₁. Tento případ je ekvivalentní řešení problému s n - 1 osoba a n - 1 klobouk, protože pro každý z n - kromě toho 1 člověk P₁ ze zbývajících je právě jeden klobouk n - 1 klobouky, které nemusí obdržet (pro žádné P_j kromě P_i, klobouk, který si nelze připustit h_j, zatímco pro P_i to je h₁).
P_i přijímá h₁. V tomto případě se problém zmenší na n - 2 osoby a n - 2 klobouky.

Pro každou z n - 1 klobouk P₁ může obdržet, počet způsobů, které P₂, … ,P_n mohou všichni dostávat klobouky, je součet počtů pro dva případy. To nám dává řešení problému kontroly klobouku: uvedeno algebraicky, číslo!n vyřazení an n-prvková sada je

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

,

kde! 0 = 1 a! 1 = 0. Prvních několik hodnot!n jsou:

Počet vyřazení an n- Sada prvků (sekvence A000166 v OEIS ) pro malé n
n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
!n	1	0	1	2	9	44	265	1,854	14,833	133,496	1,334,961	14,684,570	176,214,841	2,290,792,932

Existují také různé jiné (ekvivalentní) výrazy pro!n:^[5]

{ displaystyle! n = n! součet _ {i = 0} ^ {n} { frac {(-1) ^ {i}} {i!}}, quad n geq 0,}

{ displaystyle! n = left lfloor { frac {n!} {e}} right rceil = left lfloor { frac {n!} {e}} + { frac {1} {2 }} vpravo rfloor, quad n geq 1.}

(kde ${ Displaystyle left lfloor x right rceil}$ je nejbližší celočíselná funkce^[6] a ${ Displaystyle left lfloor x right rfloor}$ je funkce podlahy )

Pro jakékoli celé číslo $n \geq 1$ ,

{ displaystyle! n = { begin {cases} lfloor { frac {n!} {e}} + r_ {1} rfloor, & n { text {je zvláštní}}, quad r_ {1} in [0, { frac {1} {2}}], lfloor { frac {n!} {e}} + r_ {2} rfloor, & n { text {is even}}, quad r_ {2} in [{ frac {1} {3}}, 1]. end {cases}}}

Takže pro jakékoli celé číslo $n \geq 1$ a pro jakékoli reálné číslo $r \in [1 / 3, 1 / 2]$ ,

{ displaystyle! n = left lfloor { frac {n!} {e}} + r right rfloor, quad n geq 1, quad r in left [{ frac {1} {3}}, { frac {1} {2}} vpravo].}

Proto, jak $E = 2.71828\dots$ , $1 / E \in [1 / 3, 1 / 2]$ , pak ^[7]

{ 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,}

{ displaystyle! n = n! - součet _ {i = 1} ^ {n} {n zvolit i} cdot {! (n-i)}, quad n geq 1.}

Rovněž platí následující rovnost opakování:^[8]

{ displaystyle! n = n left (! (n-1) right) + (- 1) ^ {n}, quad n geq 1.}

Odvození principem začlenění – vyloučení

Další derivace (ekvivalentního) vzorce pro počet odchylek an n-set je následující. Pro ${ displaystyle 1 leq k leq n}$ definujeme ${ displaystyle S_ {k}}$ být souborem permutací n objekty, které opravují k-ten objekt. Jakýkoli průsečík sbírky i z těchto sad opravuje konkrétní sadu i objekty a proto obsahuje ${ displaystyle (n-i)!}$ obměny. Existují ${ displaystyle {n vybrat i}}$ takové sbírky, takže zásada začlenění - vyloučení výnosy

{ displaystyle { begin {zarovnáno} | S_ {1} cup cdots cup S_ {n} | & = sum _ {i} left | S_ {i} right | - sum _ {i < j} left | S_ {i} cap S_ {j} right | + sum _ {i

a protože odchylka je permutace, která nezanechává nic z n objekty opraveny, dostaneme

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

Mez poměru odchylky k permutaci jako n přístupy ∞

Z

{ displaystyle! n = n! součet _ {i = 0} ^ {n} { frac {(-1) ^ {i}} {i!}}}

a

{ displaystyle e ^ {x} = součet _ {i = 0} ^ { infty} {x ^ {i} přes i!}}

jeden okamžitě získá použití X = −1:

{ displaystyle lim _ {n to infty} {! n over n!} = {1 over e} přibližně 0,3679 ldots.}

Toto je limit pravděpodobnost že náhodně vybraná permutace velkého počtu objektů je odchylkou. Pravděpodobnost konverguje k této hranici extrémně rychle jako n zvyšuje, což je důvod, proč!n je nejbližší celé číslo n!/E. Výše semi-log graf ukazuje, že graf odchylky zaostává permutační graf o téměř konstantní hodnotu.

Více informací o tomto výpočtu a výše uvedeném limitu naleznete v článku na webustatistika náhodných permutací.

Zobecnění

The problème des rencontres zeptá se, kolik permutací velikostin nastavit přesně k pevné body.

Derangementy jsou příkladem širšího pole omezených permutací. Například problém ménage ptá se, jestli n páry opačného pohlaví jsou usazeny muž-žena-muž-žena -... u stolu, kolika způsoby je lze posadit, aby nikdo neseděl vedle jeho partnera?

Více formálně, dané sady A a Sa některé sady U a PROTI z surjekce A → S, často bychom chtěli znát počet párů funkcí (F, G) takové, že F je v U a G je v PROTIa pro všechny A v A, F(A) ≠ G(A); jinými slovy, kde pro každého F a G, existuje odchylka φ S takhle F(A) = φ (G(A)).

Další zobecnění je následující problém:

Kolik anagramů bez pevných písmen daného slova existuje?

Například pro slovo složené pouze ze dvou různých písmen řekněme n písmena A a m písmena B, odpověď je samozřejmě 1 nebo 0 podle toho, zda n = m nebo ne, jediný způsob, jak vytvořit přesmyčku bez pevných písmen, je vyměnit všechny A s B, což je možné právě tehdy n = m. Obecně platí, že pro slovo s n₁ písmena X₁, n₂ písmena X₂, ..., n_r písmena X_r ukázalo se (po správném použití inkluze-exkluze vzorec), že odpověď má formu:

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

pro určitou posloupnost polynomů P_n, kde P_n má titul n. Ale výše uvedená odpověď pro případ r = 2 dává vztah ortogonality, odkud P_njsou Laguerrovy polynomy (až do znamení, o kterém se snadno rozhodne).^[9]

{ displaystyle int _ {0} ^ { infty} (t-1) ^ {z} e ^ {- t} dt}

v komplexní rovině.

Zejména pro klasické poruchy

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

Výpočetní složitost

to je NP-kompletní zjistit, zda daný permutační skupina (popsáno danou sadou permutací, které ji generují) obsahuje jakékoli odchylky.^[10]

Reference

^ Název „subfaktoriál“ pochází z William Allen Whitworth; vidět Cajori, Florian (2011), Historie matematických notací: dva svazky v jednom, Cosimo, Inc., s. 77, ISBN 9781616405717.
^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Konkrétní matematika (1994), Addison – Wesley, Reading MA. ISBN 0-201-55802-5
^ de Montmort, P. R. (1708). Esej d'analyse sur les jeux de hazard. Paříž: Jacque Quillau. Seconde Edition, Revue a augmentée de plusieurs Lettres. Paříž: Jacque Quillau. 1713.
^ Scoville, Richard (1966). „Problém s kloboukem“. Americký matematický měsíčník. 73 (3): 262–265. doi:10.2307/2315337. JSTOR 2315337.
^ Hassani, M. "Derangements and Applications." J. Integer Seq. 6, No. 03.1.2, 1-8, 2003
^ Weisstein, Eric W. "Nejbližší celočíselná funkce". MathWorld.
^ Weisstein, Eric W. „Podfaktoriál“. MathWorld.
^ Viz poznámky k (sekvence A000166 v OEIS ).
^ Dokonce, S .; J. Gillis (1976). „Derangements and Laguerre polynomials“. Mathematical Proceedings of the Cambridge Philosophical Society. 79 (1): 135–143. doi:10.1017 / S0305004100052154. Citováno 27. prosince 2011.
^ Lubiw, Anna (1981), „Některé NP-úplné problémy podobné izomorfismu grafů“, SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, PAN 0605600. Babai, László (1995), „Automorfické skupiny, izomorfismus, rekonstrukce“, Handbook of combineatorics, Vol. 1, 2 (PDF), Amsterdam: Elsevier, s. 1447–1540, PAN 1373683, Překvapivý výsledek Anny Lubiw tvrdí, že následující problém je NP-úplný: Má daná permutační skupina prvek bez pevného bodu?.

externí odkazy

Baez, Johne (2003). „Pojďme se zbláznit!“ (PDF).
Bogart, Kenneth P .; Doyle, Peter G. (1985). „Nesexistické řešení problému ménage“.
Dickau, Robert M. "Schémata vyřazení". Matematické údaje pomocí Mathematica.
Hassani, Mehdi. „Derangements and Applications“. Journal of Integer Sequences (JIS), svazek 6, vydání 1, článek 03.1.2, 2003.
Weisstein, Eric W.. „Derangement“. MathWorld – webový zdroj Wolfram.

[1] Název „subfaktoriál“ pochází z William Allen Whitworth; vidět Cajori, Florian (2011), Historie matematických notací: dva svazky v jednom, Cosimo, Inc., s. 77, ISBN 9781616405717.

[2] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Konkrétní matematika (1994), Addison – Wesley, Reading MA. ISBN 0-201-55802-5

[3] Montmort, P. R. (1708). Esej d'analyse sur les jeux de hazard. Paříž: Jacque Quillau. Seconde Edition, Revue a augmentée de plusieurs Lettres. Paříž: Jacque Quillau. 1713.

[4] Scoville, Richard (1966). „Problém s kloboukem“. Americký matematický měsíčník. 73 (3): 262–265. doi:10.2307/2315337. JSTOR 2315337.

[5] Hassani, M. "Derangements and Applications." J. Integer Seq. 6, No. 03.1.2, 1-8, 2003

[Mathworld-NearestIntegerFunction-6] Weisstein, Eric W. "Nejbližší celočíselná funkce". MathWorld.

[Mathworld-Subfactorial-7] Weisstein, Eric W. „Podfaktoriál“. MathWorld.

[8] Viz poznámky k (sekvence A000166 v OEIS ).

[9] Dokonce, S .; J. Gillis (1976). „Derangements and Laguerre polynomials“. Mathematical Proceedings of the Cambridge Philosophical Society. 79 (1): 135–143. doi:10.1017 / S0305004100052154. Citováno 27. prosince 2011.

[10] Lubiw, Anna (1981), „Některé NP-úplné problémy podobné izomorfismu grafů“, SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, PAN 0605600. Babai, László (1995), „Automorfické skupiny, izomorfismus, rekonstrukce“, Handbook of combineatorics, Vol. 1, 2 (PDF), Amsterdam: Elsevier, s. 1447–1540, PAN 1373683, Překvapivý výsledek Anny Lubiw tvrdí, že následující problém je NP-úplný: Má daná permutační skupina prvek bez pevného bodu?.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]