Permutation vs kombination: Hvad er forskellen mellem permutationsformlen og kombinationsformlen?

Her er den korte version.

Lad os tage ringende klokker i en kirke som et eksempel.

En permutation er en ordning af klokkerne. Du finder ud af den bedste rækkefølge for at ringe dem ind.

En kombination er valget af klokker. Du vælger klokkerne til at ringe. Hvis du har for mange klokker, skal du først vælge dem og derefter tænke på at bestille dem.

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

Måden at bestille rvarer ud af ner først at vælge rvarer ud af nog derefter bestille rvarerne ( r!)

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

Men vil du vide, hvordan man kan huske dette for evigt?

Jeg er en stor fan af de første principper. For at forstå et problem skal du komme til kernen i det og ræsonnere derfra.

At ikke gøre dette er normalt kilden til forvirring: hvis jeg ikke forstår, hvordan tingene fungerer, ved jeg ikke, hvor begreberne skal hænges. Min mentale ramme er ikke komplet, så jeg beslutter at bare huske det.

Som du kan forestille dig, er dette ikke ideelt. Så fra tid til anden forkæler jeg mig selv med en øvelse med at udlede ting fra kilden og opbygge intuition til, hvordan ting fungerer.

Denne gang bygger vi intuition til permutationer og kombinationer.

Ved du f.eks., Hvorfor formlen for en kombination er (n C r)? Hvor kom dette fra? Og hvorfor bruges fakta her?

Lad os begynde ved kilden. Fakta, permutationer og kombinationer blev født af matematikere, der spillede sammen, ligesom hvordan Steve Jobs og Steve Wozniak grundlagde Apple, der spillede sammen i deres garage.

Ligesom hvordan Apple blev et fuldt ud rentabelt selskab, det enkle faktorium !, blev atomet for et helt felt i matematik: kombinatorik.

Glem alt, lad os begynde at tænke fra bunden op.

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

Har du spekuleret på, hvordan klokkerne ringes i kirker? Der er en maskine, der "ringer" dem i rækkefølge. Vi skiftede til maskiner, fordi klokkerne er for store. Der er også masser af klokker.

Hvordan fandt folk ud af den bedste rækkefølge at ringe dem til? Hvad hvis de ville tænde for tingene? Hvordan kunne de finde den bedste lyd? Hvert klokketårn havde op til 16 klokker!

Du kunne ikke ændre, hvor hurtigt du kunne ringe en klokke - maskinerne ringede kun en klokke hvert sekund. Det eneste du kunne gøre var at ændre rækkefølgen af ​​klokkerne. Så denne udfordring handlede om at finde ud af den bedste orden.

Kunne vi undervejs også finde ud af alle mulige ordrer? Vi vil vide alle mulige ordrer for at finde ud af, om det er værd at prøve dem alle.

Fabian Stedman, der var ringeklokke, tog denne udfordring op.

Han startede med 2 klokker. Hvad er de forskellige ordrer, han kunne ringe disse klokker i? [1]

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.

Start derefter med den anden klokke,

2, 1 og 3.

2, 3 og 1.

Start derefter med den tredje klokke,

3, 1 og 2.

3, 2 og 1.

I alt 6.

Han indså derefter, at dette lignede to klokker!

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

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

Okay, han fortsatte. Han nåede derefter 5 klokker.

Dette var, da han indså, at det er vanskeligt at gøre tingene i hånden. Du har kun så meget tid på dagen, du er nødt til at ringe klokker, du kan ikke sidde fast med at trække alle mulige klokker ud. Var der en måde at finde ud af hurtigt?

Han vendte tilbage til sin indsigt.

Hvis han havde 5 klokker, og han fikset den første klokke, var alt, hvad han skulle gøre, at finde ud af, hvordan han bestilte 4 klokker.

Til 4 klokker? Hvis han havde 4 klokker, og han fik fikset den første klokke, var alt, hvad han skulle gøre, at finde ud af, hvordan han bestilte 3 klokker.

Og han vidste, hvordan man gjorde dette!

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 ser mønsteret, ikke?

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

Det gjorde han også. Selvom det tog ham meget længere tid, da ingen i nærheden af ​​ham allerede havde opdaget dette. [2]

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

Denne bestillingsformel, i 1808, blev kendt som den faktiske.

Vi tænker på den faktuelle notation som basen, men ideen eksisterede længe før den havde et navn. Det var først, da den franske matematiker Christian Kramp bemærkede, at den blev brugt nogle få steder, at han kaldte det fabriksarealet.

Denne ordning af klokker kaldes en permutation.

En permutation er en ordre på varer.

Når jeg lærer noget, tror jeg, det hjælper at se på ting fra alle forskellige vinkler for at styrke forståelsen.

Hvad hvis vi forsøgte at udlede formlen ovenfor direkte uden at forsøge at reducere problemet til et mindre antal klokker?

Vi har 5 mellemrum, ikke?

Hvor mange måder kan vi vælge den første klokke? 5, fordi det er antallet af klokker, vi har.

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

Den tredje klokke? 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åledes har vi vores første generelle formel.

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

Permutationen

Nu står vi over for et andet problem. Kongen beordrede, at der blev lavet nye klokker til hver kirke. Nogle er pæne, andre er okay, andre får dig til at blive døv. Men alle er unikke. Hver gør 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 den bedste bestilling ud af 8 klokker, som de dygtige klokkeproducenter lavede.

Ved hjælp af ovenstående logik kan vi fortsætte.

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

For den anden klokke kan vi vælge en af ​​de resterende 7 klokker ... og så videre.

Til sidst får vi 8 * 7 * 6 * 5 * 4mulige ordrer på 8 klokker fordelt på 5 mellemrum.

Hvis du er fortrolig med formelversionen af ​​(n P r), som er n! / (n-r)!, skal du ikke bekymre dig, vi udleder det også hurtigt nok!

En dårlig måde at udlede det på er at gange tælleren og nævneren med 3! i vores eksempel ovenfor -

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

Men dette hjælper os ikke med at forstå, hvorfor denne formel fungerer. Lad os tage et kig på valg af ting eller kombinationen, inden vi kommer derhen.

Kombinationen

Nu hvor vi ved, hvordan vi bestiller ting, kan vi finde ud af, hvordan vi vælger ting!

Lad os overveje det samme problem. Der er en klokketårn med 5 klokker, og du har 8 klokker. Men lige nu vil du ikke finde ud af rækkefølgen af ​​klokker (husk det er, hvad 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. Faktisk deler vi problemet op i dele: Først finder vi ud af, hvilke klokker vi skal vælge. Dernæst finder vi ud af, hvordan man bestiller de valgte klokker.

Hvordan vælger du klokkerne? Dette er "kombinationen" fra permutationer og kombinationer.

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

Da vi ved, hvordan vi bestiller klokker, skal vi bruge disse oplysninger til at finde ud af, hvordan vi vælger klokker. Lyder umuligt? Vent til du ser den smukke matematik involveret.

Lad os forestille os, at alle klokkerne er i en linje.

Før vi finder alle måder at vælge klokkerne på, skal vi fokusere på en måde at vælge klokker på.

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

Vi sætter klokkerne i en linje og vælger de første 5. Dette er en måde at vælge klokkerne på.

Bemærk, at selvom vi skifter position for de første 5 klokker, ændres valget ikke. De er stadig den samme måde at vælge 5 unikke klokker på.

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

Nu, det smukke matematik-trick - for denne ene måde at vælge de 5 klokker på, hvad bestiller alt 8 klokker, hvor vi vælger nøjagtigt disse 5 klokker? Fra billedet ovenfor er det alle rækkefølgen af ​​de 5 klokker ( 5!) og alle rækkefølgen af ​​de resterende tre klokker ( 3!).

Således har vi ( 5! * 3!) ordrer på 8 klokker for hver eneste måde at vælge 5 klokker på.

Hvad er de samlede mulige ordrer på 8 klokker? 8!.

Husk, for hvert valg af de første 5 klokker har vi ( 5! * 3!) ordrer på 8 klokker, der giver det samme valg.

Derefter, hvis vi multiplicerer antallet af måder at vælge de første 5 klokker med alle de mulige ordninger af et valg, skal vi få det samlede antal ordrer.

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:

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

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

Nu kan vi generalisere dette. Hvis vi har N-ting, og vi vil vælge R af dem, betyder det, at vi tegner en linje ved R.

Hvilket betyder, at de resterende varer vil være N-R. Så for et valg af Rvarer har vi R! * (N-R)!ordrer, der giver de samme Rvarer.

RVi har N! / (R! * (N-R)!)muligheder for alle måder at vælge emner på .

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

I daglig tale udtrykkes (n C r) også n choose r, hvilket hjælper med at styrke ideen om, at kombinationer er til valg af varer.

Permutationen - genbesøgt

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

Det er vores job nu at finde den perfekte melodi ved at finde ud af antallet af ordrer.

Men dette er den lette bit. Vi ved allerede, hvordan vi bestiller 5 varer. Det er 5!, og vi er færdige.

Så for at permutere (bestille) 5 varer ud af 8, skal vi først vælge 5 varer og derefter bestille de 5 varer.

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 vi er kommet i fuld cirkel til vores originale formel, afledt korrekt.

Antallet af måder at bestille rvarer ud af ner(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 ordrer, mens kombinationer er valg.

For at bestille N-elementer fandt vi to intuitive måder at finde ud af svaret på. Begge fører til svaret N!.

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

Og intuitionen til at vælge Rfra Ner at finde ud af alle rækkefølger ( N!) og dividere med ordrer, hvor den første Rog den sidste N-Rforbliver den samme ( R!og (N-R)!).

Og det er alt der er til permutationer og kombinationer.

Hver avanceret permutation og kombination bruger dette som en base. Kombination med udskiftning? Samme idé. Permutation med identiske genstande? Samme idé, kun antallet af ordrer ændres, da nogle varer er identiske.

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

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

Slutnoter

  1. Sådan forestiller jeg mig, at han fandt ud af tingene. Tag det ikke som en lektion i historien.
  2. Indianerne havde i det 12. århundrede 400 år før ham.