Uitleg formule combinatie

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
JackMol
Vast lid
Vast lid
Berichten: 84
Lid geworden op: 06 jun 2018, 21:01

Uitleg formule combinatie

Bericht door JackMol » 10 nov 2019, 17:47

Kan iemand alstublieft uitleggen waarom de formule van de combinatie zo is?

https://wikimedia.org/api/rest_v1/media ... bfae445b47


Liefst zo makkelijk en logisch mogelijk.
Alvast bedankt

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Uitleg formule combinatie

Bericht door arie » 11 nov 2019, 11:04

De definitie:
De combinatie \({n \choose k}\) = het aantal mogelijkheden om een verzameling ("groep") van k elementen uit een verzameling van n verschillende elementen te kiezen.
De volgorde van de elementen is hierbij niet van belang, elk element mag maximaal 1 keer gekozen worden (trekking zonder terugleggen).

Oplossing:
We tellen eerst het aantal mogelijkheden om n elementen op een (geordende) rij te plaatsen.
Dit is het aantal permutaties = rangschikkingen van n elementen:
hiervoor zijn \(n! = n \cdot (n-1) \cdot ... \cdot 3 \cdot 2 \cdot 1\) verschillende mogelijkheden.
Van elk rijtje nemen we de eerste k elementen als onze keuze, de overige (n-k) elementen blijven waar ze zijn.

Voorbeeld:
Stel we hebben een verzameling van n=8 elementen: {a, b, c, d, e, f, g, h} en kiezen daaruit k=3 elementen.
Van elke permutatie van n (er zijn er in totaal 8! = 40320) kiezen we steeds de eerste 3 elementen.
Van bijvoorbeeld de permutatie
e-b-g-c-a-f-h-d
kiezen we e, b en g, de overige elementen (c, a ,f ,h en d) kiezen we niet.
We splitsen op deze manier elke permutatie dus in 2 delen: de k elementen die we kiezen voorop = de kop van de permutatie, daarna de elementen die we niet kiezen = de staart van de permutatie:
e-b-g || c-a-f-h-d

Omdat bij permutaties de volgorde WEL belangrijk is, maar bij combinaties NIET, zijn er meerdere verschillende permutaties die dezelfde combinatie leveren.
Bijvoorbeeld:
g-e-b || c-a-f-h-d
e-b-g || f-a-c-d-h
g-b-e || h-f-a-d-c
etc.
Voor elke combinatie \({n \choose k}\) hebben we precies:
\(k!\) mogelijke volgordes waarin we de elementen van de kop kunnen plaatsen
en onafhankelijk daarvan
\((n-k)!\) mogelijke volgordes waarin we de elementen van de staart kunnen plaatsen

Ofwel:
Elke combinatie \({n \choose k}\) wordt door \(k! \cdot (n-k)!\) verschillende permutaties beschreven, en dat zijn precies alle permutaties die met de gekozen k elementen beginnen.
Bovendien leveren alle combinaties bij elkaar precies alle mogelijke koppen en in totaal dus alle mogelijke permutaties.
Hierdoor is het aantal combinaties

\({n \choose k} = \frac{\text{aantal permutaties}}{\text{aantal permutaties per combinatie}} = \frac{n!}{k! \cdot (n-k)!}\)


Wordt het hiermee wat duidelijker?

Plaats reactie