Cykly a pevné body - Cycles and fixed points

16-bit Šedý kód permutace G
znásobeno s bit-reverzní permutace B

G má 2 pevné body, 1 2-cyklus a 3 4 cykly
B má 4 pevné body a 6 2 cykly
GB má 2 pevné body a 2 7 cyklů

P * (1,2,3,4)^T = (4,1,3,2)^T

Permutace čtyř prvků pomocí 1 pevný bod a 1 3-cyklus

v matematika, cykly a permutace π konečný soubor S korespondovat bijektivně do oběžné dráhy podskupiny generované π herectví na S. Tyto dráhy jsou podmnožiny z S které lze zapsat jako {C₁, ..., C_l }, takhle

π(C_i) = C_{i + 1} pro i = 1, ..., l - 1 a π(C_l) = C₁.

Odpovídající cyklus π je psáno jako ( C₁ C₂ ... C_n ); tento výraz není od té doby jedinečný C₁ lze zvolit jakýkoli prvek na oběžné dráze.

Velikost l orbity se nazývá délka odpovídajícího cyklu; když l = 1, jediný prvek na oběžné dráze se nazývá a pevný bod permutace.

Permutace je určena zadáním výrazu pro každý z jejích cyklů a jedna notace pro permutace spočívá v psaní takových výrazů jeden po druhém v určitém pořadí. Například nechte

${ displaystyle pi = { begin {pmatrix} 1 & 6 & 7 & 2 & 5 & 4 & 8 & 3 2 & 8 & 7 & 4 & 5 & 3 & 6 & 1 end {pmatrix}} = { begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 2 & 4 & 1 & 3 & 5 & 8 & 7 & 6 }$

být permutací, která mapuje 1 až 2, 6 až 8 atd. Pak lze psát

π = ( 1 2 4 3 ) ( 5 ) ( 6 8 ) (7) = (7) ( 1 2 4 3 ) ( 6 8 ) ( 5 ) = ( 4 3 1 2 ) ( 8 6 ) ( 5 ) (7) = ...

Zde 5 a 7 jsou pevné body π, od té doby π(5) = 5 a π(7) = 7. Je typické, ale není to nutné, nenapsávat cykly délky jedna do takového výrazu.^[1] Π = (1 2 4 3) (6 8) by tedy byl vhodný způsob vyjádření této permutace.

Existují různé způsoby, jak napsat permutaci jako seznam jejích cyklů, ale počet cyklů a jejich obsah je dán rozdělit z S na oběžné dráhy, a ty jsou tedy pro všechny takové výrazy stejné.

Počítání permutací podle počtu cyklů

Nepodepsaný Stirlingovo číslo prvního druhu, s(k, j) počítá počet permutací k prvky s přesně j disjunktní cykly.^[2][3]

Vlastnosti

(1) Pro každého k > 0 : s(k, k) = 1.

(2) Pro každého k > 0 : s(k, 1) = (k − 1)!.

(3) Pro každého k > j > 1, s(k, j) = s(k − 1,j − 1) + s(k − 1, j)·(k − 1)

Důvody nemovitostí

(1) Existuje jen jeden způsob, jak vytvořit permutaci k prvky s k cykly: Každý cyklus musí mít délku 1, takže každý prvek musí být pevným bodem.

(2.a) Každý cyklus délky k lze zapsat jako obměnu čísla 1 až k; existují k! těchto permutací.

(2.b) Existují k různé způsoby zápisu daného cyklu délky k, např. (1 2 4 3) = (2 4 3 1) = (4 3 1 2) = (3 1 2 4).

(2.c) Konečně: s(k, 1) = k!/k = (k − 1)!.

(3) Existují dva různé způsoby, jak vytvořit permutaci k prvky s j cykly:

(3.a) Pokud chceme prvek k jako pevný bod můžeme zvolit jeden z s(k − 1, j - 1) permutace s k - 1 prvků a j - 1 cykly a přidání prvku k jako nový cyklus délky 1.

(3.b) Pokud chceme prvek k ne jako pevný bod můžeme zvolit jeden z s(k − 1, j ) permutace s k - 1 prvků a j cykly a vložte prvek k ve stávajícím cyklu před jedním z k - 1 prvků.

Některé hodnoty

Počítání permutací podle počtu pevných bodů

Hodnota F(k, j) počítá počet permutací k prvky s přesně j pevné body. Hlavní článek o tomto tématu najdete v části obnovuje čísla.

Vlastnosti

(1) Pro každého j <0 nebo j > k : F(k, j) = 0.

(2) F(0, 0) = 1.

(3) Pro každého k > 1 a k ≥ j ≥ 0, F(k, j) = F(k − 1, j − 1) + F(k − 1, j)·(k − 1  − j) + F(k − 1, j + 1)·(j + 1)

Důvody nemovitostí

(3) Existují tři různé metody pro konstrukci permutace k prvky s j pevné body:

(3.a) Můžeme si vybrat jednu z F(k − 1, j - 1) permutace s k - 1 prvků a j - 1 pevné body a přidat prvek k jako nový pevný bod.

(3.b) Můžeme si vybrat jednu z F(k − 1, j) permutace s k - 1 prvků a j pevné body a vložte prvek k v existujícím cyklu délky> 1 před jedním z (k − 1) − j elementy.

(3.c) Můžeme si vybrat jednu z F(k − 1, j + 1) permutace s k - 1 prvků a j + 1 pevné body a spojovací prvek k s jedním z j + 1 pevné body k cyklu délky 2.

Některé hodnoty

Alternativní výpočty

${ displaystyle f (k, 1) = součet _ {i = 1} ^ {k} (- 1) ^ {i + 1} {k zvolit i} i (k-i)!}$

Příklad: F(5, 1) = 5×1×4! − 10×2×3! + 10×3×2! - 5×4×1! + 1×5×0!

= 120 - 120 + 60 - 20 + 5 = 45.

${ displaystyle f (k, 0) = k! - součet _ {i = 1} ^ {k} (- 1) ^ {i + 1} {k zvolit i} (k-i)!}$

Příklad: F(5, 0) = 120 - ( 5×4! - 10×3! + 10×2! - 5×1! + 1×0! )

= 120 - ( 120 - 60 + 20 - 5 + 1 ) = 120 - 76 = 44.

Pro každého k > 1:

${ Displaystyle f (k, 0) = (k-1) (f (k-1,0) + f (k-2,0))}$

Příklad: F(5, 0) = 4 × ( 9 + 2 ) = 4 × 11 = 44

Pro každého k > 1:

${ displaystyle f (k, 0) = k! součet _ {i = 2} ^ {k} (- 1) ^ {i} / i!}$

Příklad: F(5, 0) = 120 × ( 1/2 - 1/6 + 1/24 - 1/120 )

= 120 × ( 60/120 - 20/120 + 5/120 - 1/120 ) = 120 × 44/120 = 44

${ displaystyle f (k, 0) přibližně k! / e}$

kde e je Eulerovo číslo ≈ 2.71828

Viz také

• Cyklická permutace
• Cyklická notace

Poznámky

Reference

• Brualdi, Richard A. (2010), Úvodní kombinatorika (5. vydání), Prentice-Hall, ISBN  978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN  0-521-45761-0
• Gerstein, Larry J. (1987), Diskrétní matematika a algebraické struktury, W.H. Freeman and Co., ISBN  0-7167-1804-9