Vad är permutationscykler?

Hej. Jag håller på med ett litet arbete om permutationscykler i Matte Diskret där jag ska förklara vad de är och lite hur man räknar med dem, men det tycks inte finnas någon större mängd information på internet.

Det vore jätteschysst om någon kunde förklara lite kortfattat vad de är, hur man räknar, vad de används till osv.

Tack i förhand.

Till att börja med: vet du vad en permutation är?

En variation när det gäller att sortera olika element på olika sätt. Jag vet också typ vad en permutationcykel är; en permutation som har samma ordning men förskjuts typ. ABCD-BCDA-CDAB osv... Men en mer matematisk definition och lite mer ingående vore bra att ha. Och vad man ska använda det till.

Det där är en cyklisk permutation och är i och för sig en permutationscykel, men även icke-cykliska permutationer har permutationscykler.

Betrakta permutationen (4 1 3 2 6 5).

Vi gör en vandring av hur element har flyttats runt: Elementet på position 1 i permutationen kommer från position 4 i originalet. Elementet på position 4 har ersatts av elementet som var på position 2. Och slutligen, elementet på position 2 kommer från position 1. Nu har vi gått runt ett varv: 1 → 4 → 2 → 1, vilket vi skriver (1 4 2). Ekvivalenta sätt att skriva är förstås (4 2 1) och (2 1 4). På samma sätt finner man två andra permutationscykler: (3) och (5 6). Permutationen (4 1 3 2 6 5) innehåller alltså tre permutationscykler: (1 4 2), (3) och (5 6).

Så det är alltså skillnad på cykliska permutationer och permutationscykler.

Du nämner originalet, skulle det då vara (1 2 3 4 5 6), alltså i storleksordning? Varför isåfall?

Ja.


Det kan vara lämpligt att skilja mellan två saker:

• en uppradning av element, t.ex. [A B C D E F]
• omflyttning av element, t.ex. [A B C D E F] → [D A C B F E]

Det är omflyttningen som man normalt syftar på när man i matematiken talar om permutationer.

Omflyttningen [A B C D E F] → [D A C B F E] betecknar vi med (4 1 3 2 6 5) eftersom elementet i position 1 i "resultatet" (D) kommer från position 4 i "originalet" o.s.v.

Omflyttningen/permutationen är en funktion:
(4 1 3 2 6 5) [A B C D E F] = [D A C B F E]
Jämför detta med f(3) = 5.

Funktioner kan sättas samman, vilket därmed även permutationer kan:
(3 6 2 1 4 5) (4 1 3 2 6 5) [A B C D E F] = (3 6 2 1 4 5) [D A C B F E] = [C E A B F] = (3 5 1 2 6) [A B C D E F]
Alltså,
(3 6 2 1 4 5) (4 1 3 2 6 5) = (3 5 1 2 6)

Okej men det hänger jag med på nu tror jag.

Hur kommer det sig att du tog D här? Borde det inte ha blivit [C E A D B F]?
Jag fick lite texter kopierade av min mentor på det här ämnet och där stod det också om att man kunde sätta samman permutationer.
Då beräknade de dem på ett lite annorlunda sätt.

P=(4 3 1 2)
Q=(2 3 4 1)
PQ=(Q(P(1)) Q(P(2)) Q(P(3)) Q(P(4)))

Då borde man få (3 6 2 1 4 5)(4 1 3 2 6 5) = (1 3 2 6 5 4) eller har jag fått det om bakfoten?

En annan fråga. I dessa papper står det att (3 2 4 1 5) är en cykel (1,3,4) men att (3 5 4 1 2) inte är en cykel. Men är inte de andra exemplet två cykler (1,3,4)(2,5) på samma sätt som det första exemplet är tre cykler (1,3,4)(2)(5)?

Misstag av mig... Ibland är det bra att som lärare göra fel. Det får eleverna att fundera själva (när det är en elev som verkligen vill tänka och förstå).


De sätter alltså PQ = Q o P, medan jag sätter PQ = P o Q. [Med o menar jag komposition: (f o g)(x) = f(g(x)).]

Jag vet inte om det finns någon särskild konvention när det gäller permutationer, men när det gäller matriser sätter man AB = A o B.

Det spelar ingen roll vilket val man gör, bara man klargör sitt val och håller sig till ett.


Helt korrekt.

Observera att vår beteckning för en cykel, t.ex. (1,3,4), kan ses som ett förkortat skrivsätt för en permutation, i det här fallet (3 2 4 1 5), som kan delas in i två delar - en som inte flyttar på element, (* 2 * * 5), och en som flyttar element cykliskt, (3 * 4 1 *).

Cyklernas roll i permutationer kan nog jämföras med primtalens roll i naturliga tal.

Jag insåg nu att 1-cykler såsom (2) och (5) är ganska meningslösa att skriva. Båda står ju för permutationen (1 2 3 4 5), enhetselementet bland permutationer.

Tack så hemskt mycket för all hjälpen. Föredraget är imorgon och tack vare dig och lite sidor från en annan bok har jag tillräckligt bra koll för att kunna förvirra en grupp treor.

Tack igen, jag blir fortfarande förvånad över hur hjälpsamma människor kan vara!