Permutace s lichým počtem pevných bodů Řekneme, že číslo / G {1, 2,..., n} je pevným bodem permutace a množiny čísel {1,2,..., a?}, jestliže a(i) = /. Bude nás zajímat, kolik existuje permutací a7-prvkové množiny {1,2,..., n} majících lichý počet pevných bodů. Pro každé nezáporné celé číslo n označme symbolem cn hledaný počet permutací množiny {1,2,..., n} majících lichý počet pevných bodů a označme dále symbolem dn počet permutací množiny {1,2,..., n} majících sudý počet pevných bodů. Pak ovšem platí cn + dn = n\. Najdeme nejprve rekurentní formuli pro čísla cn. Zřejmě Co = 0 a c\ = 1. Pro n ^ 2 uvažujme následujícím způsobem. Mějme libovolnou permutaci a množiny {1, 2,..., n} mající lichý počet pevných bodů. Počet takových permutací je dán číslem cn. Rozlišíme dále tři možnosti. Může se stát, že číslo n bude pevným bodem permutace a. Pak permutace a permutuje mezi sebou čísla 1, 2,..., n — 1. Tak vzniká permutace množiny {1, 2,..., n — 1} mající sudý počet pevných bodů. Počet takových permutací je dán číslem dn-i. Dále se může stát, že permutace a bude mezi sebou prohazovat číslo n a některé jiné číslo /. Pak / G {1, 2,..., n — 1} a permutace a dále permutuje mezi sebou čísla 1, 2,..., / — 1, / + 1,..., n — 1. Tak vzniká permutace množiny {1, 2,..., n — 1} — {/} mající lichý počet pevných bodů. Počet takových permutací je dán číslem cn-2-_ A konečně se může stát, že budou existovat vzájemně různá čísla i J taková, že a(i) = n a cr(n) = j. Pak i J £ {1, 2,..., n — 1}. Změňme permutaci a tak, že vypustíme číslo n a budeme žádat, aby se číslo / zobrazilo na číslo j. Tak vzniká permutace množiny {1, 2,..., n — 1} mající lichý počet pevných bodů taková, že číslo / není jejím pevným bodem. Připomeňme, že / je číslo, které se původní permutácia zobrazovalo na číslo n. Jinak je / libovolné číslo z množiny {1, 2,..., n — 1}. Pro dané číslo / pak veďme následující úvahu. Počet všech permutací množiny {1, 2,..., n — 1} majících lichý počet pevných bodů je dán číslem c„_i. Musíme ale tento počet umenšit o počet permutací množiny {1, 2,..., n — 1} majících lichý počet pevných bodů, v nichž je číslo / pevným bodem. Taková permutace pak permutuje mezi sebou čísla 1, 2,...,/ — 1, / + 1,..., n — 1 a toto zúžení dotyčné permutace má sudý počet pevných bodů. Počet takových permutací je ovšem dán číslem dn-2- Shrneme-li všechny doposud provedené úvahy, dospějeme k závěru, že pro každé n ^ 2 platí rovnost Cn = dn-! + (a7 - l)cn-2 + (a7 - 1)(cA?_1 - dn-2). Připomeňme, že pro každé n platí cn + dn = a?!, takže dn = n\ — cn. Využitím tohoto faktu v předchozí rovnosti dojdeme k rovnosti cn = (a? - 1)! - cn_i + (a? - l)cn-2 + {n- l)(cA?_i - (a? - 2)! + cn-2)-Konečně jednoduchou úpravou dospějeme k zjištění, že platí rovnost Cn = (a7 - 2)0,-1 + 2(a7 - 1)0,-2 pro všechna n ^ 2. To je hledaný rekurentní vztah pro čísla cn. Míříme nyní k využití exponenciální generující funkce pro posloupnost čísel {cn}^0. To jest uvažujeme mocninnou řadu oo A?! A7=0 K ní vezmeme ještě její derivaci oo Z výše uvedené rekurentní formule pak plyne OO OO / ~\ oo (n - 2)c"-i „n-i , n V- (n - 1)c"-2 n-l ^(n-1)! ^ (n-l)! ^ (n-l)! n=2 v ' n=2 v ' n=2 v ' oo oo oo _ C"~l n-l _ V- C"-l + 9. V C"~2 X -Z^(n_2)!X 2^(n_i)!x +2Z^(n_2)X n=2 v 7 A?=2 v 7 A?=2 v 7 oo oo oo n = x.y ^-x"-1 - y +2x. y ^xn. n=l v 7 n=l n=0 S využitím počátečních hodnot cq = 0 a Ci = 1 odtud vyplývá oo oo oo oo Cn x"-1 -1 = x- y -^l."-1 - y V7+2x- y ^v. (n^l) ^ (n-1) n=l V 7 A7=0 A7=0 a7! neboli anebo jinak takže ť(x) - 1 = x-£'(x) - £(x) + 2x-£(x) (l-x)-£'(x) = (2x-l)-£(x) + l, . 2x — 1 w . 1 Cx =---£(x) + 1-x ~v"' 1-x To je ale lineární diferenciální rovnice 1. řádu pro neznámou funkci £(x), přičemž £(0) = 0. Připomeňme z kurzu matematické analýzy, že obecným řešením lineární diferenciální rovnice 1. řádu y'(x) = f (x)y(x) + g(x) je množina funkcí y(x) = r(x)c/x ÍC + / g(x)e" ^ f{x)dxdx pro všechny reálné konstanty C. Obecným řešením výše uvedené diferenciální rovnice pro je tedy množina funkcí c + 1-x pro všechny reálné konstanty C. Přitom 2x- 1 1 -x -2 + 1 -x takže 2x- 1 1 -x c/x = - 2Ídx + J f~£/x = -2x-ln(l-x). odkud plyne 1 1 1 — x e 2x Takže obecným řešením shora uvedené diferenciální rovnice pro £(x) je množina funkcí 1 1 1 — x e 2x c + --(1-x), 1-x v ' e2xdx 1 1 2x 1 — x e 1 1 C+ / e2xdx 1 — x e 2x pro všechny reálné konstanty C. Poněvadž naše řešení (£(x) uvedené diferenciální rovnice má splňovat podmínku £(0) = 0, plyne odtud, že £(x) je tím řešením dotyčné diferenciální rovnice, které je dáno hodnotou C = — \. Vychází tak, že Roznásobením závorky a vykráčením vyjde / x 1 1 111 C(x) = - 2 1-x 2 e2x 1- x Rozvineme tuto exponenciální generující funkci posloupnosti čísel {cn}^0 do mocninné řady. Tak dostaneme n=0 /'=0 7=0 co ^ oo n f A7=0 A7=0 /C=0 i 00 i 1 00 i , n / oY I V-v" -IV-ÍV i—1 n=Q n=0 k=0 Poněvadž oo X n vychází porovnáním koeficientů u všech mocnin proměnné x v posledních dvou mocninných řadách, že platí pro všechna celá čísla n ^ 0. Můžeme si nyní položit otázku, jaká je pravděpodobnost, že náhodně zvolená permutace a množiny {1,2,..., n} bude mít lichý počet pevných bodů. Poněvadž všech permutací množiny {1, 2,..., n} je celkem n\, bude tato pravděpodobnost rovna hodnotě cn/n\. Odtud a z předchozího poznatku pak vyplývá, že tato pravděpodobnost je rovna hodnotě Můžeme si dále klást otázku, k jaké hodnotě se bude tato pravděpodobnost blížit pro n —)► oo. k=0 k=0 Je jasné, že půjde o hodnotu 1_1 f,(z2T = l_l 2 1 2 2'^ /c! 2 2 2 ' 1 e2T Pro velké hodnoty čísla n bude tedy zmíněná pravděpodobnost přibližně rovna hodnotě 0,432332358.