Permutation vs. kombination: Vad är skillnaden mellan permutationsformeln och kombinationsformeln?

Permutation vs. kombination: Vad är skillnaden mellan permutationsformeln och kombinationsformeln?

Här är den korta versionen.

Låt oss ta klockringning i en kyrka som exempel.

En permutation är en ordning av klockorna. Du funderar ut den bästa ordningen att ringa dem i.

En kombination är valet av klockor. Du väljer vilka klockor som ska ringa. Om du har för många klockor skulle du först välja dem och sedan fundera på att ordna dem.

Detta ger upphov till den välkända identiteten: (n P r) = (n C r) * r!

Sättet att beställa r föremål av n är att först välja r föremål av n och sedan beställa r föremålen (r! )

Och detta innebär (n P r) = n! / (n-r)! och (n C r) = n! / ( (n-r)! * r! )

Men vill du veta hur du ska komma ihåg detta för alltid?

Jag är en stor anhängare av förstaprinciptänkande. För att förstå ett problem måste man gå till kärnan av det och resonera därifrån.

Om man inte gör detta är det oftast källan till förvirring: om jag inte förstår hur saker och ting fungerar vet jag inte var jag ska hänga upp begreppen. Min mentala ram är inte komplett, så jag bestämmer mig för att bara komma ihåg det.

Som du kan föreställa dig är detta inte idealiskt. Så då och då ger jag mig hän åt en övning där jag härleder saker från källan och bygger upp en intuition för hur saker och ting fungerar.

Den här gången bygger vi upp en intuition för permutationer och kombinationer.

Vet du till exempel varför formeln för en kombination är (n C r)? Varifrån kommer detta? Och varför används faktorier här?

Låt oss börja vid källan. Faktorer, permutationer och kombinationer föddes av matematiker som lekte tillsammans, på samma sätt som Steve Jobs och Steve Wozniak grundade Apple genom att leka tillsammans i sitt garage.

På samma sätt som Apple blev ett fullfjädrad lönsamt företag blev den enkla faktorn, !, atomen för ett helt område inom matematiken: kombinatorik.

Förglöm allt, låt oss börja tänka nerifrån och upp.

Det första kända intressanta användningsfallet kom från kyrkor på 1600-talet.

Har du undrat hur klockorna ringer i kyrkorna? Det finns en maskin som ”ringer” dem i ordning. Vi övergick till maskiner eftersom klockorna är för stora. Dessutom finns det massor av klockor.

Hur kom man fram till den bästa ordningen att ringa dem i? Vad hände om de ville byta ut saker och ting? Hur kunde de hitta det bästa ljudet? Varje klocktorn hade upp till 16 klockor!

Det gick inte att ändra hur snabbt man kunde ringa en klocka – maskinerna ringde bara en klocka varje sekund. Det enda man kunde göra var att ändra ordningen på klockorna. Så den här utmaningen handlade om att ta reda på den bästa ordningen.

Kan vi på vägen dit också ta reda på alla möjliga ordningar? Vi vill veta alla möjliga ordningsföljder för att ta reda på om det är värt att prova dem alla.

En klockspelare, Fabian Stedman, antog denna utmaning.

Han började med två klockor. Vilka olika ordningsföljder kan han ringa dessa klockor i?

1 och 2.
eller
2 och 1.

Detta var vettigt. Det fanns inget annat sätt.

Hur vore det med tre klockor?

1, 2 och 3.
1, 3 och 2.

Då börjar man med den andra klockan,

2, 1 och 3.
2, 3 och 1.

Då börjar man med den tredje klockan,

3, 1 och 2.
3, 2 och 1.

Total, 6.

Han insåg då att detta var mycket likt två klockor!

Om han fixade den första klockan var antalet sätt att beställa de återstående två klockorna alltid två.

Hur många sätt kunde han fixa den första klockan? Vilken som helst av de tre klockorna kunde vara den rätta!

Okej, fortsatte han. Han nådde sedan fem klockor.

Det var då han insåg att det är otympligt att göra saker för hand. Man har bara så mycket tid på dagen, man måste ringa klockor, man kan inte sitta och rita alla möjliga klockor. Fanns det ett sätt att räkna ut detta snabbt?

Han gick tillbaka till sin insikt.

Om han hade fem klockor och han fixade den första klockan var allt han behövde göra att räkna ut hur han skulle beställa fyra klockor.

För fyra klockor? Tja, om han hade 4 klockor och han fixade den första klockan var allt han behövde göra att räkna ut hur han skulle beställa 3 klockor.

Och han visste hur han skulle göra detta!

Så, beställning av 5 klockor = 5 * beställning av 4 klockor.

Beställning av 4 klockor = 4 * beställning av 3 klockor

Beställning av 3 klockor = 3 * beställning av 2 klockor.

… Du ser mönstret, eller hur?

Skoleffekten: Detta är nyckeln till en programmeringsteknik som kallas rekursion.

Det gjorde han också. Fast det tog honom mycket längre tid, eftersom ingen i hans närhet redan hade upptäckt detta.

Så kom han på att ordningen av 5 klockor = 5 * 4 * 3 * 2 * 1.

Denna ordningsformel kom 1808 att bli känd som faktornotationen.

Vi tänker på faktornotationen som basen, men idén fanns långt innan den fick ett namn. Det var först när den franske matematikern Christian Kramp märkte att den användes på några ställen som han gav den namnet faktorial.

Denna ordningsordning av klockor kallas för en permutation.

En permutation är en ordningsordning av objekt.

När man lär sig något tror jag att det hjälper att titta på saker och ting från alla olika vinklar, för att befästa förståelsen.

Hur vore det om vi försökte härleda formeln ovan direkt, utan att försöka reducera problemet till ett mindre antal klockor?
Vi har 5 utrymmen, eller hur?

Hur många sätt kan vi välja den första klockan? 5, eftersom det är det antal klockor vi har.

Den andra klockan? Tja, vi använde en klocka när vi placerade den i den första positionen, så vi har 4 klockor kvar.

Den tredje klockan? Tja, vi har valt de två första, så det finns bara tre klockor kvar att välja mellan.

Den fjärde klockan? Bara två klockor kvar, så två alternativ.
Den femte klockan? Endast 1 kvar, så 1 alternativ.

Och där har vi det, det totala antalet beställningar är 5 * 4 * 3 * 2 * 1

Därmed har vi vår första allmänna formel.

Antalet sätt att beställa N artiklar är N!

Nu står vi inför ett annat problem. Kungen beordrade att nya klockor skulle tillverkas till varje kyrka. En del är fina, en del är okej, en del gör dig döv. Men varje klocka är unik. Var och en ger sitt eget ljud. En öronbedövande klocka omgiven av fina klockor kan låta majestätiskt.

Men vårt klocktorn rymmer fortfarande 5 klockor, så vi måste räkna ut vilken beställning som är bäst av de 8 klockor som de skickliga klockmakarna tillverkade.

Med hjälp av ovanstående logik kan vi fortsätta.

För den första klockan kan vi välja vilken som helst av de 8 klockorna.

För den andra klockan kan vi välja vilken som helst av de återstående 7 klockorna… och så vidare.

I slutändan får vi 8 * 7 * 6 * 5 * 4 möjliga ordningar av 8 klockor i 5 utrymmen.

Om du är bekant med formelversionen av (n P r), som är n! / (n-r)!, oroa dig inte, vi kommer att härleda den också snart nog!

Ett dåligt sätt att härleda den är att multiplicera både täljaren och nämnaren med 3! i vårt exempel ovan –

får vi 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Men detta hjälper oss inte att förstå varför denna formel fungerar. Innan vi kommer dit ska vi ta en titt på att välja saker, eller kombinationen.

Kombinationen

När vi nu vet hur man ordnar saker kan vi räkna ut hur man väljer saker!

Låt oss betrakta samma problem. Det finns ett klocktorn med 5 klockor och du har 8 klockor. Men just nu vill du inte ta reda på klockornas ordning (kom ihåg att det är vad en permutation är).

Istället vill du välja de 5 bästa klockorna och låta någon annan med bättre musiksmak ta reda på ordningen. I själva verket bryter vi ner problemet i två delar: Först tar vi reda på vilka klockor vi ska välja. Därefter tar vi reda på hur vi ska ordna de valda klockorna.

Hur väljer man klockorna? Detta är ”kombinationen” från permutationer och kombinationer.

Kombinationen är ett urval. Du gör ett urval. Du väljer 5 klockor av 8 som dina hantverkare har tillverkat.

Då vi vet hur man beställer klockor, kommer vi att använda denna information för att räkna ut hur man väljer klockor. Låter det omöjligt? Vänta tills du ser den vackra matematiken som är inblandad.

Låt oss föreställa oss att alla klockor står på en rad.

För att hitta alla sätt att välja klockor, låt oss fokusera på ett sätt att välja klockor.

Ett sätt är att välja 5 slumpmässigt. Detta hjälper oss inte att lösa problemet särskilt mycket, så låt oss prova ett annat sätt.

Vi ställer klockorna på en rad och väljer de 5 första. Detta är ett sätt att välja klockorna.

Bemärk att även om vi byter position för de 5 första klockorna ändras inte valet. De är fortfarande samma enda sätt att välja 5 unika klockor.

Detta gäller även för de tre sista klockorna.

Nu kommer det vackra matematiska tricket – för detta enda sätt att välja de 5 klockorna, vilka är alla ordningsföljder av 8 klockor där vi väljer exakt dessa 5 klockor? Från bilden ovan är det alla ordningar av de 5 klockorna (5!) och alla ordningar av de återstående tre klockorna (3!).

För varje enskilt sätt att välja 5 klockor har vi alltså (5! * 3!) ordningar av 8 klockor.

Vilka är de totala möjliga ordningarna av 8 klockor? 8!.

Håll dig i minnet att för varje val av de första 5 klockorna har vi (5! * 3!) ordningar av 8 klockor som ger samma val.

Då, om vi multiplicerar antalet sätt att välja de första 5 klockorna med alla möjliga ordningar av ett val, bör vi få det totala antalet ordningar.

Ways to choose 5 bells * orderings of one choice = Total orderings

Så,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice.

I matematik blir det:

(8 C 5) = 8! / ( 5! * 3!)

Visst, vi har hittat en intuitiv förklaring till hur man väljer 5 saker av 8.

Nu kan vi generalisera detta. Om vi har N saker och vi vill välja R av dem innebär det att vi drar en linje vid R.

Vilket innebär att de återstående sakerna blir N-R. För ett val av R saker har vi alltså R! * (N-R)! ordningar som ger samma R saker.

För alla sätt att välja R saker har vi N! / (R! * (N-R)!) möjligheter.

Antalet sätt att välja r föremål av n är (n C r) = n! / (r! * (n-r)!)

I vardagligt tal uttalas (n C r) också n choose r, vilket hjälper till att befästa idén om att kombinationer är till för att välja föremål.

Permutationen – omprövad

Med kombinationen gjord och dammad, låt oss återgå till del 2 av vårt arbete. Vår käre vän valde de bästa 5 klockorna genom att räkna ut alla möjliga kombinationer av 5 klockor.

Det är vårt jobb nu att hitta den perfekta melodin genom att räkna ut antalet beställningar.

Men det här är den enkla biten. Vi vet redan hur man beställer 5 artiklar. Det är 5!, och vi är klara.

För att permutera (ordna) 5 objekt av 8 väljer vi alltså först 5 objekt, och ordnar sedan de 5 objekten.

Med andra ord,

(8 P 5) = (8 C 5) * 5!

Och om vi expanderar formeln, blir det (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

Och vi har kommit tillbaka till vår ursprungliga formel, härledd på rätt sätt.

Antalet sätt att beställa r element av n är (n P r) = n! / (n-r)!

Skillnaden mellan permutation och kombination

Jag hoppas att det här gör skillnaden mellan permutationer och kombinationer kristallklar.

Permutationer är ordningar, medan kombinationer är valmöjligheter.

För att beställa N element hittade vi två intuitiva sätt att ta reda på svaret. Båda leder till svaret N!.

För att permutera 5 av 8 element måste man först välja de 5 elementen och sedan ordna dem. Du väljer med hjälp av (8 C 5) och ordnar sedan de 5 med hjälp av 5!.

Och intuitionen för att välja R av N är att räkna ut alla ordningar (N!) och dividera med ordningar där den första R och den sista N-R förblir desamma (R! och (N-R)!).

Och det är allt som gäller för permutationer och kombinationer.

Alla avancerade permutationer och kombinationer använder detta som grund. Kombination med ersättning? Samma idé. Permutation med identiska objekt? Samma idé, bara antalet ordningar ändras, eftersom vissa objekt är identiska.

Om du är intresserad kan vi gå in på de komplexa fallen i ett annat exempel. Låt mig veta på Twitter.

Kolla in fler inlägg på min blogg och gå med i den veckovisa sändlistan.

Slutanteckningar

1. Det är så här jag föreställer mig att han räknade ut saker och ting. Ta det inte som en lektion i historia.
2. Indianerna hade, på 1100-talet, 400 år före honom.