Permutationer

Vad är det som är svårt att förstå? Är det skillnaden? Om du har siffrorna 0 - 9, och ska välja tre siffror, kan du antingen permutera eller kombinera siffrorna. Både permutationer och kombinationer är urval av olika grupper. Skillnaden är att en permutation är ett urval där ordningen spelar roll. Tänk ett kodlås: 4, 2, 1 är inte samma sak som 2, 4, 1. Detta är en permutation.

Om du istället ska addera siffror för att få lagom vikt till en våg, spelar det ingen roll om du lägger på 4-vikten först eller sist. 4 + 2 +1 = 2 + 4 + 1. Detta är en kombination. 

Skulle du kunna förklara mer information om kombination? :) 

Absolut! Kombinationer är ett begrepp som används när ordningen av element inte spelar någon roll. Om du har tre frukter som ska ned i en fruktsallad spelar det ingen roll om bananen, kiwin eller vindruvorna körs i skålen först. Om du då ska välja bland fem olika frukter kan du beräkna antalet alternativ med hjälp av formeln för kombinationer. 

Denna formel utgår ifrån formeln om permutationer. Börja med att beräkna hur många alternativ vi har om ordningen trots allt spelar roll. Den första frukten kan vara fem olika. När du väljer den andra finns det fyra alternativ kvar, och när du väljer den sista finns det tre frukter kvar att välja. Det ger oss att antalet permutationer är $5\cdot 4\cdot 3$. För att förenkla hur detta skrivs, kan vi skriva $\frac{5!}{2!}$. (Skriv ut hela beräkningen om detta känns oklart).

Men! Ordningen spelade ju ingen roll? Då måste vi dividera bort alla upprepningar. Vi hade tre frukter, och dessa kan permuteras på 3! sätt. Alla dessa sex permutationer är identiska från ett kombonatoriskt perspektiv. Permutationerna är kanske (apelsin, ananas, kiwi) vs. (ananas, kiwi, apelsin). Därför dividerar vi med 3!, för att rensa bort dessa duplikationer. Då får vi $\frac{5!}{3!\cdot 2!}$. Den allmänna formeln är just detta. $\frac{n!}{k!\cdot (n-k)!}$. Börjar det klarna lite? 

Men! Ordningen spelade ju ingen roll? Då måste vi dividera bort alla upprepningar.

Den här biten förstår jag inte riktigt. :(

Vi börjar med att beräkna hur många alternativ vi har om vi tar hänsyn till ordningen. Då får vi ut ett visst antal alternativ. Dock hade vi bestämt innan att ordningen inte spelar någon roll (eftersom apelsin, päron är samma som päron, apelsin). Då måste vi försöka bli av med de alternativ som är upprepningar. 

Om vi har fyra utvalda objekt, kan det första objektet väljas på fyra sätt, det andra objektet kan väljas på tre, osv. Om vi tar hänsyn till ordningen, är dessa alternativ olika. Då är päron, apelsin, kiwi, carambola; och apelsin, päron, carambola, kiwi; helt olika alternativ, trots att de ingående elementen är identiska. Därför dividerar vi med 4!, (eller i detta fall 3!, eftersom vi skulle välja tre frukter). Varje kombination kommer att "bestå av" 3! olika permutationer. 

Är du med på att man kan välja ut 3 frukter av 5 på 5!/2! olika sätt?

Säg att vi har valt frukterna ananas, banan, clementin. Bland de 5!/2! olika sätten att välja 3 frukter av 5 har vi med kombinationen ABC inte bara en, utan 6 ggr: ABC,ACB, BAC, BCA, CAB och CBA. Om vi vill att alla dessa sätt skall räknas som samma behöver vi alltså dela med 3!, precis som Smutstvätt skrev.

Nu förstår jag, tack! :)