Permutatie vs Combinatie: Wat is het verschil tussen de permutatieformule en de combinatieformule?

Permutatie vs Combinatie: Wat is het verschil tussen de permutatieformule en de combinatieformule?

Hier volgt de korte versie.

Laten we als voorbeeld het luiden van de klokken in een kerk nemen.

Een permutatie is een ordening van de klokken. Je zoekt uit wat de beste volgorde is om ze te luiden.

Een combinatie is de keuze van de klokken. Je kiest de klokken die je wilt luiden. Als je te veel klokken hebt, kies je ze eerst, en denkt dan na over de volgorde ervan.

Dit geeft aanleiding tot de bekende identiteit: (n P r) = (n C r) * r!

De manier om r items uit n te ordenen is om eerst r items uit n te kiezen, en dan de r items te ordenen (r! )

En, dit betekent (n P r) = n! / (n-r)! en (n C r) = n! / ( (n-r)! * r! )

Maar wil je weten hoe je dit voor altijd onthoudt?

Ik ben een groot voorstander van eerste beginselen denken. Om een probleem te begrijpen, moet je tot de kern doordringen en van daaruit verder redeneren.

Dit niet doen is meestal de bron van verwarring: als ik niet begrijp hoe dingen werken, weet ik niet waar ik de concepten moet ophangen. Mijn mentale kader is niet compleet, dus besluit ik het maar gewoon te onthouden.

Zoals je je kunt voorstellen, is dit niet ideaal. Dus, van tijd tot tijd, geef ik mezelf over aan een oefening om dingen af te leiden van de bron, en intuïtie op te bouwen voor hoe dingen werken.

Deze keer bouwen we intuïtie op voor permutaties en combinaties.

Weet je bijvoorbeeld waarom de formule voor een combinatie is (n C r)? Waar komt die vandaan? En waarom worden hier factorialen gebruikt?

Laten we bij de bron beginnen. Factorialen, permutaties en combinaties zijn ontstaan uit samen spelende wiskundigen, net zoals Steve Jobs en Steve Wozniak samen in hun garage Apple oprichtten.

Net zoals Apple een volwaardig winstgevend bedrijf werd, werd de eenvoudige factor, !, het atoom van een heel gebied van de wiskunde: combinatoriek.

Vergeet alles, laten we van onderaf beginnen te denken.

De eerste bekende interessante use case kwam van Kerken in de 17e eeuw.

Heb je je afgevraagd hoe de klokken in kerken worden geluid? Er is een machine die ze op volgorde “luidt”. We zijn op machines overgestapt omdat de klokken te groot zijn. En er zijn massa’s klokken.

Hoe ontdekten mensen de beste volgorde om ze te luiden? Wat als ze dingen wilden veranderen? Hoe konden ze het beste geluid vinden? Elke klokkentoren had tot 16 klokken! Je kon niet veranderen hoe snel je een klok kon luiden – de machines luidden slechts één klok per seconde. Het enige wat je kon doen was de volgorde van de klokken veranderen. Dus, deze uitdaging ging over het uitzoeken van de beste volgorde.

Zouden we, onderweg, ook alle mogelijke volgordes kunnen achterhalen? We willen alle mogelijke volgordes weten om uit te zoeken of het de moeite waard is ze allemaal te proberen.

Een klokkenluider, Fabian Stedman, ging deze uitdaging aan.

Hij begon met 2 klokken. Wat zijn de verschillende volgordes waarin hij deze klokken kon luiden?

1 en 2.
of
2 en 1.

Dit was logisch. Er was geen andere manier.

Hoe zit het met 3 klokken?

1, 2, en 3.
1, 3, en 2.

Start dan met de tweede bel,

2, 1, en 3.
2, 3, en 1.

Start dan met de derde bel,

3, 1, en 2.
3, 2, en 1.

Totaal, 6.

Hij realiseerde zich toen dat dit erg leek op twee klokken!

Als hij de eerste bel vastzette, dan was het aantal manieren om de overige twee klokken te ordenen altijd twee.

Op hoeveel manieren kon hij de eerste bel vastzetten? Elk van de drie klokken kon de enige zijn!

Oké, hij ging verder. Toen bereikte hij 5 klokken.

Dit is wanneer hij zich realiseerde dat dingen met de hand doen onhandig is. Je hebt maar zoveel tijd op een dag, je moet klokken luiden, je kunt niet alle mogelijke klokken blijven uittekenen. Was er een manier om dit snel uit te zoeken?

Hij ging terug naar zijn inzicht.

Als hij 5 klokken had, en hij repareerde de eerste klok, hoefde hij alleen maar uit te zoeken hoe hij 4 klokken kon bestellen.

Voor 4 klokken? Nou, als hij 4 klokken had en hij had de eerste gerepareerd, hoefde hij alleen maar 3 klokken te bestellen.

En hij wist hoe hij dat moest doen!

Dus, bestelling van 5 klokken = 5 * bestelling van 4 klokken.

Ordering van 4 klokken = 4 * bestelling van 3 klokken

Ordering van 3 klokken = 3 * bestelling van 2 klokken.

… Je ziet het patroon, nietwaar?

Leuk weetje: Dit is de sleutel tot een programmeertechniek die recursie heet.

Hij deed het ook. Hoewel hij er veel langer over deed, want niemand in zijn omgeving had dit al ontdekt.

Hij kwam er dus achter dat de ordening van 5 klokken = 5 * 4 * 3 * 2 * 1.

Deze ordeningsformule kwam in 1808 bekend te staan als de factorial.

Wij denken aan de factorialnotatie als de basis, maar het idee bestond al lang voordat het een naam had. Pas toen de Franse wiskundige Christian Kramp merkte dat het op een paar plaatsen werd gebruikt, gaf hij het de naam factorieel.

De ordening van klokken wordt een permutatie genoemd.

Een permutatie is een ordening van items.

Wanneer je iets leert, helpt het volgens mij om de dingen van alle kanten te bekijken, zodat je ze beter begrijpt.

Wat als we de bovenstaande formule rechtstreeks zouden afleiden, zonder te proberen het probleem terug te brengen tot een kleiner aantal klokken?
We hebben 5 ruimtes, toch?

Op hoeveel manieren kunnen we de eerste bel kiezen? 5, want dat is het aantal klokken dat we hebben.

De tweede bel? Wel, we hebben één klok opgebruikt toen we hem op de eerste positie plaatsten, dus we hebben nog vier klokken over.

De derde klok? Nou, we hebben de eerste twee gekozen, dus we hebben nog maar 3 bellen over om uit te kiezen.

De vierde bel? Er zijn nog maar 2 klokken over, dus 2 opties.
De vijfde bel? Nog maar 1 over, dus 1 optie.

En daar hebben we het dan, het totaal aantal volgordes is 5 * 4 * 3 * 2 * 1

Dus hebben we onze eerste algemene formule.

Het aantal manieren om N artikelen te bestellen is N!

Nu staan we voor een ander probleem. De koning heeft voor elke kerk nieuwe klokken laten maken. Sommige zijn mooi, sommige zijn oké, van sommige word je doof. Maar elk klokje is uniek. Ze maken allemaal hun eigen geluid. Een oorverdovende klok omringd door mooie klokken kan majestueus klinken.

Maar, onze klokkentoren heeft nog 5 klokken, dus we moeten de beste volgorde vinden uit de 8 klokken die de bekwame klokkenmakers hebben gemaakt.

Met bovenstaande logica kunnen we verder gaan.

Voor de eerste klok kunnen we elk van de 8 klokken kiezen.

Voor de tweede klok kunnen we elk van de resterende 7 klokken kiezen… enzovoort.

Uiteindelijk krijgen we 8 * 7 * 6 * 5 * 4 mogelijke volgordes van 8 klokken op 5 velden.

Als je bekend bent met de formule-versie van (n P r), die n! / (n-r)! is, maak je dan geen zorgen, ook die leiden we snel genoeg af!

Een slechte manier om het af te leiden is om zowel de teller als de noemer met 3 te vermenigvuldigen! in ons voorbeeld hierboven –

krijgen we 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1 = 8! / 3!.

Maar dit helpt ons niet om te begrijpen waarom deze formule werkt. Laten we eerst eens kijken naar het kiezen van dingen, of de Combinatie.

De Combinatie

Nu we weten hoe we dingen kunnen ordenen, kunnen we uitzoeken hoe we dingen kunnen kiezen!

Laten we hetzelfde probleem eens bekijken. Er is een klokkentoren met 5 klokken, en jij hebt 8 klokken. Je wilt nu echter niet de volgorde van de klokken bepalen (onthoud dat dit een permutatie is).

In plaats daarvan wil je de 5 beste klokken kiezen en iemand anders met een betere muzieksmaak de volgorde laten bepalen. In feite splitsen we het probleem op in twee delen: Eerst zoeken we uit welke klokken we moeten kiezen. Vervolgens zoeken we uit hoe we de gekozen klokken ordenen.

Hoe kies je de klokken? Dit is de “combinatie” uit permutaties en combinatie.

De combinatie is een selectie. Je bent selectief. U kiest 5 klokken uit 8 die uw ambachtslieden hebben gemaakt.

Nu we weten hoe we klokken moeten bestellen, gaan we deze informatie gebruiken om uit te zoeken hoe we klokken moeten kiezen. Klinkt onmogelijk? Wacht maar tot u ziet hoe mooi de wiskunde is.

Stellen we ons voor dat alle klokken op een rij staan.

Voordat we alle manieren vinden om de klokken te kiezen, concentreren we ons op één manier om klokken te kiezen.

Eén manier is om willekeurig 5 klokken te kiezen. Dit helpt ons niet om het probleem op te lossen, dus laten we een andere manier proberen.

We zetten de klokken op een rij, en kiezen de eerste 5. Dit is één manier om de klokken te kiezen.

Merk op dat, zelfs als we de eerste 5 klokken van plaats verwisselen, de keuze niet verandert. Ze zijn nog steeds dezelfde manier om 5 unieke klokken te kiezen.

Dit geldt ook voor de laatste drie klokken.

Nu de mooie wiskundige truc – voor deze ene manier om de 5 klokken te kiezen, wat zijn alle ordeningen van 8 klokken waarbij we precies deze 5 klokken kiezen? Volgens de afbeelding hierboven zijn dat alle volgordes van de 5 klokken (5!) en alle volgordes van de overige drie klokken (3!).

Dus, voor elke manier om 5 klokken te kiezen, hebben we (5! * 3!) volgordes van 8 klokken.

Wat zijn de totaal mogelijke volgordes van 8 klokken? 8!.

Bedenk dat we voor elke keuze van de eerste 5 klokken (5! * 3!) volgordes van 8 klokken hebben die dezelfde keuze geven.

Wanneer we dan het aantal manieren om de eerste 5 klokken te kiezen vermenigvuldigen met alle mogelijke volgordes van één keuze, moeten we het totaal aantal volgordes krijgen.

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

Dus,

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

In wiskunde wordt dat:

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

Lo en zie, we hebben een intuïtieve verklaring gevonden voor hoe we 5 dingen uit 8 kunnen kiezen.

Nu kunnen we dit veralgemenen. Als we N dingen hebben, en we willen er R van kiezen, betekent dit dat we een lijn trekken bij R.

Wat betekent dat de resterende items N-R zullen zijn. Dus, voor één keuze van R items, hebben we R! * (N-R)! volgordes die dezelfde R items geven.

Voor alle manieren om R items te kiezen, hebben we N! / (R! * (N-R)!) mogelijkheden.

Het aantal manieren om r items te kiezen uit n is (n C r) = n! / (r! * (n-r)!)

In de volksmond wordt (n C r) ook uitgesproken als n choose r, wat helpt om het idee te staven dat combinaties bedoeld zijn om items te kiezen.

De permutatie – herzien

Met de combinatie klaar en afgestoft, laten we terugkomen op deel 2 van onze taak. Onze vriend koos de beste 5 klokken door alle mogelijke combinaties van 5 klokken uit te zoeken.

Het is nu onze taak om de perfecte melodie te vinden door het aantal volgordes uit te zoeken.

Maar, dit is het makkelijke gedeelte. We weten al hoe we 5 items moeten bestellen. Het is 5!, en we zijn klaar.

Dus, om 5 items uit 8 te permuteren (ordenen), kiezen we eerst 5 items, en dan ordenen we de 5 items.

In andere woorden,

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

En als we de formule uitbreiden, (8 P 5) = (8! / ( 5! * 3!)) * 5!

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

En, we zijn weer terug bij onze oorspronkelijke formule, op de juiste manier afgeleid.

Het aantal manieren om r items te ordenen uit n is (n P r) = n! / (n-r)!

Verschil tussen permutatie en combinatie

Ik hoop dat dit het verschil tussen permutaties en combinaties glashelder maakt.

Permutaties zijn ordeningen, terwijl combinaties keuzes zijn.

Om N elementen te ordenen, hebben we twee intuïtieve manieren gevonden om het antwoord te achterhalen. Beide leiden tot het antwoord, N!.

Om 5 van de 8 elementen te permuteren, moet je eerst de 5 elementen kiezen, en ze dan ordenen. Je kiest met (8 C 5), dan orden je de 5 met 5!.

En de intuïtie voor het kiezen van R uit N is het uitzoeken van alle ordeningen (N!) en delen door ordeningen waarbij de eerste R en de laatste N-R hetzelfde blijven (R! en (N-R)!).

En, dat is alles wat er is aan permutaties en combinaties.

Elke geavanceerde permutatie en combinatie gebruikt dit als basis. Combinatie met vervanging? Zelfde idee. Permutatie met identieke items? Zelfde idee, alleen het aantal volgordes verandert, omdat sommige items identiek zijn.

Als je geïnteresseerd bent, kunnen we in een ander voorbeeld ingaan op de complexe gevallen. Laat het me weten op Twitter.

Kijk voor meer berichten op mijn blog, en word lid van de wekelijkse mailinglijst.

Eindnoten

1. Dit is hoe ik me voorstel dat hij het heeft uitgevogeld. Zie het niet als een les in geschiedenis.
2. De Indianen hadden, in de 12e eeuw, 400 jaar voor hem.