Permutace bez transpozic
Víme, že libovolnou permutaci konečné množiny lze rozložit na součin nezávislých cyklů. Cykly délky dva nazýváme transpozicemi. Zajímá nás, kolik existuje permutací konečné množiny o n prvcích, v jejichž rozkladu na součin nezávislých cyklů nefiguruje žádná transpozice.
Poněkud podrobněji řečeno, je-li dáno kladné celé číslo n, chceme určit, kolik existuje permutací a množiny {1,2,..., n} takových, že v rozkladu permutace a na součin nezávislých cyklů nefiguruje žádný cyklus délky dva, tedy žádná transpozice. Budeme chtít řešit i obecnější úlohu spočívající v tom, že pro dané celé číslo r splňující 0 ^ r ^  ^ , kde  ^ je dolní celá část čísla ^, bude naším úkolem určit, kolik existuje permutací a množiny {1,2,..., n} takových, že v rozkladu permutace a na součin nezávislých cyklů vystupuje právě r transpozic.
Označme Sn množinu všech permutací množiny {1,2,..., n}. Buď / množina všech dvouprvkových podmnožin množiny {1,2,..., n}. Pro kteroukoliv dvouprvkovou podmnožinu {ij} množiny {1,2,..., n}, to jest pro každá i J G {1, 2,..., n} splňující / 7^ j označme A(/j} množinu všech permutací a množiny {1,2,..., n} takových, že a(i) = j a a(j) = /.
Je tedy A(/j} množinou všech těch permutací a množiny {1,2,..., n}, v jejichž rozkladu na součin nezávislých cyklů vystupuje transpozice (ij). Pak permutace a množiny {1,2,..., n}, v jejichž rozkladu na součin nezávislých cyklů nefiguruje žádná transpozice, tvoří množinu
,4(0) =    H (Sn-A{ijy).
Podle principu inkluze a exkluze je tedy počet těchto permutací roven
|/\(0)| = ^(-1)
K\
KCI
n
A
VJ}
VJ}eK
Obsahuje-li přitom podmnožina KCI některé dvě dvouprvkové podmnožiny množiny {1,2,..., n}, které mají společný jeden prvek, pak ovšem máme Pl{/ j}eK A{ijy — 0- Neobsahuje-li podmnožina K C / žádné dvě dvouprvkové podmnožiny se společným prvkem, pak ovšem \K\ ^  ^ . V takovém případě permutace z množiny 0{i j}eK ^{ij} přehazují navzájem prvky i J z podmnožin {ij} G K a permutují zbývající prvky, to jest prvky množiny {1, 2,..., n} — (J K zcela libovolně. Těchto zbývajících prvků je celkem n — 2\K\, takže v tom případě máme
n
A
VJ}
VJ}eK
(n-2\K\)\
Tento počet nezávisí na podmnožině K samotné, ale jen na počtu prvků této podmnožiny K. Je tedy třeba pro každé k = 0,1, 2,..., %  určit, kolik existuje /c-prvkových podmnožin K C I obsahujících pouze navzájem disjunktní dvouprvkové podmnožiny množiny {1,2,..., n}. Pak sjednocení (J K je některá 2/c-prvková podmnožina množiny {1,2,..., n}. Tuto podmnožinu lze vybrat (2//c) způsoby. Zbývá určit, kolika způsoby lze jakoukoliv 2/c-prvkovou podmnožinu H C {1, 2,..., n} rozložit na k dvouprvkových tříd. Připomeňme, že podle poznatků o kombinatorickém významu polynomických koeficientů počet všech zobrazení f : H —>* {1, 2,..., k} takových, že pro každé £ = 1, 2,..., k je
= 2, je roven číslu (2,2^,2) = ^r-- Toto číslo je /c!-násobkem počtu všech rozkladů množiny H na dvouprvkové třídy. Počet všech takových rozkladů množiny /-/je tedy roven číslu ^T/d - Takže celkem je počet všech /c-prvkových podmnožin K C I obsahujících pouze navzájem disjunktní dvouprvkové podmnožiny množiny {1,2,..., n} roven číslu
(2/c)! a?!
2k-k\ (n-2k)\-k\-2k
Konečně využitím doposud získaných poznatků ve výše uvedeném vztahu pro počet |/4(0)| závěrem vychází
[f]
' (n-2k)\-k\-2k
\n-2k)\
k=0
Tolik je tedy celkem permutací n-prvkové množiny, v jejichž rozkladu na součin nezávislých cyklů nefiguruje žádná transpozice.
Můžeme si položit otázku, jaká je pravděpodobnost, že pro náhodně zvolenou permutaci a množiny {1,2,..., n} nastane situace, že v rozkladu permutace a na součin nezávislých cyklů nebude figurovat žádná transpozice. Poněvadž počet všech permutací množiny {1, 2,..., n} je roven číslu n\, odtud a z předchozího výsledku 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. Je jasné, že půjde o hodnotu
[5]
k
k=0
Pro velké hodnoty čísla n tedy bude dotyčná pravděpodobnost přibližně rovna hodnotě 0,60653066.
Věnujme se nakonec úloze určit, kolik existuje permutací a množiny {1,2,..., n} takových, že v rozkladu permutace a na součin nezávislých cyklů vystupuje právě r transpozic, kde r je předem dané celé číslo splňující 0 ^ r ^ [^]. Tyto permutace tvoří množinu
u (n A™n n (^-A{iJ})).
JQi   VJ}eJ VJ}ei-J
\J\ = r
Skutečně je tomu tak, poněvadž obsahuje-li podmnožina J C / nějaké dvě dvouprvkové podmnožiny množiny {1,2,..., n} se společným prvkem, pak máme již 0{i = 0, takže ve výše uvedené formuli sjednocujeme ve skutečnosti
pouze přes podmnožiny JC / obsahující právě r vzájemně disjunktních dvouprvkových podmnožin množiny {1,2,..., n}. Podle obecnější verze principu inkluze a exkluze je pak počet výše zmíněných permutací roven
A(r)\ = Y, ("I)
K\-r
KCI
nC\K\
n
A
VJ}
VJ}eK
Připomeňme ještě jednou, že obsahuje-li podmnožina KCI některé dvě dvouprvkové podmnožiny množiny {1,2,..., n} se společným prvkem, pak máme 0{i j}eK A{ijy = 0- Musíme se tedy dále starat jenom o podmnožiny K C / obsahující pouze navzájem disjunktní dvouprvkové podmnožiny množiny {1,2,..., n}. Stejně jako v předchozí úloze se pak ukáže, že pro každou takovou podmnožinu KCI máme
n
A
VJ}
(a7-2IK"!)!
A7
2
určit, kolik existuje /c-prvkových
Dále je třeba pro každé k = r, r + 1,... podmnožin KCI obsahujících pouze navzájem disjunktní dvouprvkové podmnožiny množiny {1,2,..., n}. Ale zase stejně jako v předchozí úloze dospějeme k poznatku, že počet takových /c-prvkových podmnožin K C I je roven
v y i
cislu
n\
{n-2k)\-k\-2k
Využitím obou těchto poznatků ve výše uvedeném vztahu pro počet \A(r) konečně vyjde
["]
k=r
■    [i]     /    -t\k-r I       W   / l\/c_r
= Oi y = y ^~2J
r!  ^(/r-r)!-2*     r!-2r ^ (k - r)\ '
k=r V 7 /c=r  V 7
Tolik je tedy celkem permutací n-prvkové množiny, v jejichž rozkladu na součin nezávislých cyklů vystupuje právě r transpozic.