Permutation vs. kombination: Hvad er forskellen mellem Permutationsformlen og Kombinationsformlen?

Permutation vs. kombination: Hvad er forskellen mellem Permutationsformlen og Kombinationsformlen?

Her er den korte version.

Lad os tage ringning af klokker i en kirke som et eksempel.

En permutation er en rækkefølge af klokkerne. Du finder ud af, hvilken rækkefølge det er bedst at ringe med dem i.

En kombination er valget af klokker. Du vælger de klokker, der skal ringes med. Hvis du har for mange klokker, vælger du først dem, og så tænker du på at ordne dem.

Dette giver anledning til den velkendte identitet: (n P r) = (n C r) * r!

Måden at bestille r genstande ud af n er først at vælge r genstande ud af n og derefter bestille de r genstande (r! )

Og det betyder (n P r) = n! / (n-r)! og (n C r) = n! / ( (n-r)! * r! )

Men vil du vide, hvordan du kan huske det for evigt?

Jeg er en stor tilhænger af førsteprincippetænkning. For at forstå et problem skal man gå ind til kernen af det og ræsonnere derfra.

Det er normalt kilden til forvirring, hvis man ikke gør dette: Hvis jeg ikke forstår, hvordan tingene fungerer, ved jeg ikke, hvor jeg skal hænge begreberne op. Min mentale ramme er ikke komplet, så jeg beslutter mig for bare at huske det.

Som du kan forestille dig, er dette ikke ideelt. Så fra tid til anden giver jeg mig selv hen i en øvelse, hvor jeg udleder ting fra kilden og opbygger en intuition for, hvordan tingene fungerer.

Denne gang opbygger vi intuition for permutationer og kombinationer.

Ved du for eksempel, hvorfor formlen for en kombination er (n C r)? Hvor kommer det fra? Og hvorfor bruges faktorialer her?

Lad os begynde ved kilden. Faktorier, permutationer og kombinationer blev født af matematikere, der legede sammen, ligesom Steve Jobs og Steve Wozniak grundlagde Apple ved at lege sammen i deres garage.

Sådan som Apple blev en fuldgyldig profitabel virksomhed, blev den simple faktoriel, !, til atomet for et helt område af matematikken: kombinatorikken.

Glem alt, lad os begynde at tænke nedefra og op.

Den første kendte interessante use case kom fra kirker i det 17. århundrede.

Har du undret dig over, hvordan klokkerne ringer i kirkerne? Der er en maskine, der “ringer” dem i rækkefølge. Vi er gået over til maskiner, fordi klokkerne er for store. Desuden er der masser af klokker.

Hvordan fandt folk ud af, hvilken rækkefølge det var bedst at ringe dem i? Hvad hvis de ønskede at bytte om på tingene? Hvordan kunne de finde den bedste lyd? Hvert klokketårn havde op til 16 klokker!

Man kunne ikke ændre, hvor hurtigt man kunne ringe med en klokke – maskinerne ringede kun med en klokke hvert sekund. Det eneste, man kunne gøre, var at ændre rækkefølgen af klokkerne. Så denne udfordring handlede om at finde ud af den bedste rækkefølge.

Kunne vi undervejs også finde ud af alle de mulige rækkefølger? Vi vil gerne kende alle mulige rækkefølger for at finde ud af, om det er værd at prøve dem alle.

En klokkespiller, Fabian Stedman, tog denne udfordring op.

Han startede med 2 klokker. Hvilke forskellige rækkefølger kunne han ringe med disse klokker i?

1 og 2.
eller
2 og 1.

Dette gav mening. Der var ingen anden måde.

Hvad med 3 klokker?

1, 2 og 3.
1, 3 og 2.

Derpå startende med den anden klokke,

2, 1 og 3.
2, 3 og 1.

Derpå startende med den tredje klokke,

3, 1 og 2.
3, 2 og 1.

Total, 6.

Derpå indså han, at det lignede meget to klokker!

Hvis han ordnede den første klokke, så var antallet af måder at bestille de resterende to klokker på altid to.

Hvor mange måder kunne han ordne den første klokke på? Enhver af de tre klokker kunne være den rigtige!

Okay, gik han videre. Så nåede han frem til 5 klokker.

Det var her, han indså, at det er uhåndterligt at gøre tingene i hånden. Man har kun så meget tid på dagen, man skal ringe med klokker, man kan ikke sidde og tegne alle mulige klokker ud. Var der en måde at finde ud af det hurtigt?

Han vendte tilbage til sin indsigt.

Hvis han havde 5 klokker, og han ordnede den første klokke, skulle han bare finde ud af, hvordan han kunne bestille 4 klokker.

For 4 klokker? Tja, hvis han havde 4 klokker, og han reparerede den første klokke, skulle han blot finde ud af at bestille 3 klokker.

Og han vidste, hvordan han skulle gøre det!

Så, bestilling af 5 klokker = 5 * bestilling af 4 klokker.

Bestilling af 4 klokker = 4 * bestilling af 3 klokker

Bestilling af 3 klokker = 3 * bestilling af 2 klokker.

… Du kan se mønsteret, ikke sandt?

Sjov kendsgerning: Dette er nøglen til en programmeringsteknik kaldet rekursion.

Det gjorde han også. Selv om det tog ham meget længere tid, da ingen i hans nærhed allerede havde opdaget dette.

Så fandt han ud af, at rækkefølgen af 5 klokker = 5 * 4 * 3 * 2 * 1.

Denne rækkefølgeformel blev i 1808 kendt som faktorial.

Vi tænker på faktorialnotationen som basen, men ideen eksisterede længe før den fik et navn. Det var først da den franske matematiker Christian Kramp bemærkede, at den blev brugt nogle få steder, at han gav den navnet faktorial.

Denne orden af klokker kaldes en permutation.

En permutation er en rækkefølge af elementer.

Når man lærer noget, tror jeg, at det hjælper at se på tingene fra alle forskellige vinkler for at størkne forståelsen.

Hvad nu hvis vi prøvede at udlede formlen ovenfor direkte, uden at forsøge at reducere problemet til et mindre antal klokker?
Vi har 5 pladser, ikke?

Hvor mange måder kan vi vælge den første klokke på? 5, for det er det antal klokker, vi har.

Den anden klokke? Tja, vi brugte en klokke, da vi placerede den i den første position, så vi har 4 klokker tilbage.

Den tredje klokke? Tja, vi har valgt de to første, så der er kun 3 klokker tilbage at vælge imellem.

Den fjerde klokke? Kun 2 klokker tilbage, så 2 muligheder.
Den femte klokke? Kun 1 tilbage, så 1 mulighed.

Og der har vi det, det samlede antal bestillinger er 5 * 4 * 3 * 2 * 1

Sådan har vi vores første generelle formel.

Antallet af måder at bestille N varer på er N!

Nu står vi over for et andet problem. Kongen beordrede, at der skulle laves nye klokker til alle kirker. Nogle er flotte, nogle er okay, nogle gør dig døv. Men hver eneste er unik. Hver giver sin egen lyd. En øredøvende klokke omgivet af pæne klokker kan lyde majestætisk.

Men vores klokketårn rummer stadig 5 klokker, så vi skal finde ud af, hvordan vi bedst bestiller ud af de 8 klokker, som de dygtige klokkemagere har lavet.

Med ovenstående logik kan vi fortsætte.

Til den første klokke kan vi vælge en hvilken som helst af de 8 klokker.

Til den anden klokke kan vi vælge en hvilken som helst af de resterende 7 klokker … og så videre.

I sidste ende får vi 8 * 7 * 6 * 5 * 4 mulige rækkefølger af 8 klokker i 5 rum.

Hvis du er bekendt med formelversionen af (n P r), som er n! / (n-r)!, så bare rolig, den skal vi også snart udlede!

En dårlig måde at udlede den på er at gange både tæller og nævner med 3! i vores eksempel ovenfor –

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

Men det hjælper os ikke til at forstå, hvorfor denne formel virker. Før vi kommer dertil, skal vi se på at vælge ting, eller kombinationen.

Kombinationen

Nu da vi ved, hvordan man ordner ting, kan vi finde ud af, hvordan man vælger ting!

Lad os se på det samme problem. Der er et klokketårn med 5 klokker, og du har 8 klokker. Men lige nu ønsker du ikke at finde ud af rækkefølgen af klokkerne (husk, at det er det, som en permutation er).

I stedet ønsker du at vælge de 5 bedste klokker, og lade en anden med bedre musiksmag finde ud af rækkefølgen. I realiteten bryder vi problemet ned i to dele: Først finder vi ud af, hvilke klokker vi skal vælge. Dernæst finder vi ud af, hvordan vi skal ordne de valgte klokker.

Hvordan vælger man klokkerne? Det er “kombinationen” fra permutationer og kombinationer.

Kombinationen er et valg. Du foretager et valg. Du vælger 5 klokker ud af de 8 klokker, som dine håndværkere har lavet.

Da vi ved, hvordan man bestiller klokker, vil vi bruge denne information til at finde ud af, hvordan man vælger klokker. Lyder det umuligt? Vent, til du ser den smukke matematik, der er involveret.

Lad os forestille os, at alle klokkerne står på en række.

Hvor vi finder alle måder at vælge klokkerne på, skal vi fokusere på én måde at vælge klokker på.

En måde er at vælge 5 tilfældigt. Det hjælper os ikke meget med at løse opgaven, så lad os prøve en anden måde.

Vi stiller klokkerne på en række og vælger de 5 første. Dette er en måde at vælge klokkerne på.

Bemærk, at selv om vi skifter placering af de 5 første klokker, ændrer valget sig ikke, selv om vi skifter placering af de 5 første klokker. De er stadig den samme ene måde at vælge 5 unikke klokker på.

Dette gælder også for de sidste tre klokker.

Nu kommer det smukke matematiske trick – for denne ene måde at vælge de 5 klokker på, hvad er så alle de rækkefølger af 8 klokker, hvor vi vælger præcis disse 5 klokker? Ud fra billedet ovenfor er det alle ordningerne af de 5 klokker (5!) og alle ordningerne af de resterende tre klokker (3!).

Så for hver enkelt måde at vælge 5 klokker på, har vi (5! * 3!) ordninger af 8 klokker.

Hvad er de samlede mulige ordninger af 8 klokker? 8!.

Husk, for hvert valg af de første 5 klokker har vi (5! * 3!) rækkefølger af 8 klokker, som giver det samme valg.

Derpå, hvis vi ganger antallet af måder at vælge de første 5 klokker på med alle mulige rækkefølger af et valg, bør vi få det samlede antal rækkefølger.

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 bliver det til:

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

Se, vi har fundet en intuitiv forklaring på, hvordan man kan vælge 5 ting ud af 8.

Nu kan vi generalisere dette. Hvis vi har N ting, og vi ønsker at vælge R af dem, betyder det, at vi trækker en streg ved R.

Hvilket betyder, at de resterende ting vil være N-R. Så for et valg af R genstande har vi R! * (N-R)! rækkefølger, der giver de samme R genstande.

For alle måder at vælge R genstande på, har vi N! / (R! * (N-R)!) muligheder.

Antallet af måder at vælge r genstande ud af n er (n C r) = n! / (r! * (n-r)!)

I daglig tale udtales (n C r) også n choose r, hvilket er med til at cementere ideen om, at kombinationer er til at vælge genstande.

Permutationen – genoptaget

Med kombinationen færdig og støvet, lad os komme tilbage til del 2 af vores opgave. Vores kære ven valgte de bedste 5 klokker ved at regne alle mulige kombinationer af 5 klokker ud.

Det er nu vores opgave at finde den perfekte melodi ved at regne antallet af bestillinger ud.

Men, det er den nemme del. Vi ved allerede, hvordan man bestiller 5 ting. Det er 5!, og vi er færdige.

Så for at permutere (bestille) 5 elementer ud af 8, vælger vi først 5 elementer og bestiller derefter de 5 elementer.

Med andre ord,

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

Og hvis vi udvider formlen, (8 P 5) = (8! / ( 5! * 3!)) * 5!

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

Og så er cirklen sluttet til vores oprindelige formel, afledt på korrekt vis.

Antallet af måder at bestille r elementer ud af n er (n P r) = n! / (n-r)!

forskel mellem permutation og kombination

Jeg håber, at dette gør forskellen mellem permutationer og kombinationer krystalklar.

Permutationer er bestillinger, mens kombinationer er valgmuligheder.

For at bestille N elementer har vi fundet to intuitive måder at regne svaret ud på. Begge fører til svaret, N!.

For at permutere 5 ud af 8 elementer, skal man først vælge de 5 elementer og derefter ordne dem. Du vælger ved hjælp af (8 C 5), derefter ordner du de 5 ved hjælp af 5!.

Og intuitionen for at vælge R ud af N er at regne alle ordningerne ud (N!) og dividere med ordningerne, hvor det første R og det sidste N-R forbliver det samme (R! og (N-R)!).

Og det er alt, hvad der er at hente i permutationer og kombinationer.

Alle avancerede permutationer og kombinationer bruger dette som udgangspunkt. Kombination med erstatning? Samme idé. Permutation med identiske elementer? Samme idé, kun antallet af rækkefølger ændres, da nogle elementer er identiske.

Hvis du er interesseret, kan vi gå ind i de komplekse tilfælde i et andet eksempel. Lad mig vide det på Twitter.

Se flere indlæg på min blog, og tilmeld dig den ugentlige mailingliste.

Slutnoter

1. Det er sådan, jeg forestiller mig, at han regnede tingene ud. Tag det ikke som en lektion i historie.
2. Indianerne havde, i det 12. århundrede, 400 år før ham.