Permutacije

Pokaži najprej, da se da vsako permutacijo zapisati kot produkt disjunktnih ciklov. Potem pokaži da se da vsak cikel zapisati kot produkt transpozicij (za cikel kar konkretno napiši kako se ga zapiše, ni težko). Iz tega sledi da se da vsako permutacijo zapisati kot produkt transpozicij.

Uporabi to dejstvo in dokaži, da se pri množenju permutacije s transpozicijo spremeni število inverzij permutacije. Iz tega sledi da se dajo sode permutacije
zapisati kot produkt sodo mnogo transpozicij, lihe pa kot liho.

radovedenež je 2. maj 2010 ob 19:08 izjavil:

Hvala za pomoč, vendar mi začetni del dela težave, t.j. "vsako permutacijo zapisati kot produkt disjunktnih ciklov". Na primeru je to čisto očitno, pri dokazu pa kar kompliciram, celo z orbitami. Verjetno, se da to enostavneje dokazati, kajne?

No, odvisno kako natančen dokaz hočeš. Enostaven dokaz, pa ne zelo strog, ceprav ga lahko z ustrezno indukcijo na moc mnozice tudi malo bolj strogo zapises, gre kar z grobo silo. Vzames en element mnozice, recimo a (napaka se odpravlja). Naj bo permutacija \sigma (napaka se odpravlja). Tvoris cikel (a,\sigma(a),\sigma^2(a),\sigma^3(a),\ldots (napaka se odpravlja). Pokazat je treba, da vedno prides nazaj do a (napaka se odpravlja). Tezava bi bila, ce bi se kje vmes zaciklal, vendar se ti to zaradi bijektivnosti ne more zgoditi. S tem prvim ciklom poberes
nekaj elementov mnozice (lahko samo enega, lahko vse). Zdaj nadaljujes tako, da vzames en element iz preostanka mnozice in ponovis postopek. Ker je za vsako elementov manj, se bos enkrat ustavil. Ocitno je tudi, da so cikli disjunktni in to iz enakega razloga kot to, da pri tvorjenju cikla prides nazaj do prvotnega elementa.