Egy permutációnak az előjelét hogy lehet meghatározni a ciklusfelbontásából?

Valami olyasmi rémlik, hogy felírod a létező összes párosítást balról jobbra haladva:

12 15 13 16

25 23 26

53 56

36,

majd megnézed, hogy hány esetben nem jó a sorrend. Ha páros sok esetben, akkor pozitív, ha páratlan sok esetben, akkor negatív.

Esetünkben az 53-nál van probléma, ami 1 eset, ami páratlan, így a permutáció előjele negatív lesz.

Mondjuk a konkrét példánál lehet is látni, hogy csak az 5-öst kell a 3-assal felcserélni, hogy (12356)-ot kapjunk, szóval nem véletlen.

Tudod azt, hogy

: a páros hosszú ciklusok (pl az (12)) páratlan permutációk

: a páratlan hosszú ciklusok (pl az (1)) páros permutációk

: permutációk paritása permutációk szorzásakor "összeadódik"

Ezek alapján:

: felbontod a permutációdat ciklusokra

: megszámolod a páros hosszú ciklusokat

: ha páros sok páros hosszú ciklusod van, akkor páros a permutációd, ha páratlan sok páros hosszú ciklusod van, akkor páratlan a permutációd

Az MSE How to determine the parity of a permutation by its cycle decomposition [link] kérdés alatt van egy másik válasz is:

ha n hosszú a permutációd, és c darab ciklusra esik szét, akkor

> a permutációd előjele == (−1)^(n-c).

Nyilván n és #{ptl hosszú ciklusok} paritása megegyezik, így (n-c) paritása megegyezik #{ps ciklusok} paritásával.