Combinatie (wiskunde)

Combinatie is een begrip, dat veel in de wiskunde voorkomt en dat goed met een deelverzameling kan worden vergeleken. Een combinatie is een greep van een bepaald aantal elementen uit een verzameling waar de kardinaliteit van is gegeven. Daarbij wordt ieder element hoogstens eenmaal gekozen, de elementen worden niet teruggelegd en er wordt niet op de volgorde van de elementen gelet, hun volgorde is niet van belang.

Het aantal combinaties van ${\displaystyle k}$ elementen uit een verzameling van ${\displaystyle n}$ elementen wordt genoteerd als de binomiaalcoëfficiënt ${\displaystyle {\tbinom {n}{k}}}$, spreek uit als ${\displaystyle n}$ over ${\displaystyle k}$ of als ${\displaystyle n}$ boven ${\displaystyle k}$. De binomiaalcoëfficiënt komt voor als coëfficiënt in het binomium van Newton en dankt daaraan zijn naam. Een binomiaalcoëfficiënt kan worden berekend met de formule

${\displaystyle {\binom {n}{k}}={\frac {n!}{k!\cdot (n-k)!}}={\frac {n(n-1)\ldots (n-k+2)(n-k+1)}{k!}}={\frac {1}{k!}}\prod _{i=0}^{k-1}(n-i)}$

Het uitroepteken in de formule hierboven staat voor het berekenen van de faculteit.

Het begrip kent ook uitbreidingen, waarbij in plaats van de natuurlijke getallen ${\displaystyle n}$ en ${\displaystyle k}$ het rechterdeel van de formule geldt voor een complex of reëel getal ${\displaystyle z}$ in plaats van het natuurlijk getal ${\displaystyle n,}$ maar waarbij ${\displaystyle k}$ wel een natuurlijk getal blijft. Die uitbreiding kent toepassingen in reeksen van complexe getallen.

Als andere notatie voor ${\displaystyle {\tbinom {n}{k}}}$ komen onder meer voor:

${\displaystyle C(n,k),C\,_{k}^{n},C_{n}^{k}}$ en ${\displaystyle C_{n,k}}$

waarin de ${\displaystyle C}$ staat voor het Engelse woord combination of choice. Op sommige grafische rekenmachines staat ${\displaystyle {\text{nCk}}}$ of ${\displaystyle {\text{nCr}}}$.

Afleiding 

Het aantal mogelijkheden om een geordende keuze te maken van ${\displaystyle k}$ verschillende elementen uit een totaal van ${\displaystyle n}$ elementen is een variatie en wordt gegeven door ${\displaystyle {\frac {n!}{(n-k)!}}}$.

Bij een combinatie is, in tegenstelling tot bij een variatie, de volgorde niet van belang: het aantal mogelijkheden uit de variatie wordt daarom nog gedeeld door het aantal mogelijkheden om de ${\displaystyle k}$ getrokken elementen te rangschikken, de permutaties van ${\displaystyle k}$. Dit aantal mogelijkheden is gelijk aan k-faculteit, geschreven als ${\displaystyle k!}$. Hieruit volgt de formule ${\displaystyle {\frac {n!}{k!\cdot (n-k)!}}}$.

Voorbeelden

Deelverzamelingen

Het aantal deelverzamelingen met ${\displaystyle k}$ elementen in een verzameling met ${\displaystyle n}$ elementen is gelijk aan ${\displaystyle {\binom {n}{k}}}$.

Netwerk

Binnen een maasnetwerk met tien knooppunten wordt ieder knooppunt met alle andere knooppunten verbonden. Het aantal verbindingen is dus gelijk aan het aantal combinaties van twee elementen uit een verzameling van tien elementen. Dit aantal is 45:

${\displaystyle {\binom {10}{2}}={\frac {10!}{2!\cdot (10-2)!}}={\frac {10\cdot 9}{2\cdot 1}}=45}$

Commissie

Bij het samenstellen van een commissie van drie personen wordt een keuze gemaakt uit acht kandidaten. Indien geen rekening wordt gehouden met functies zoals voorzitter, penningmeester, is de volgorde van de te kiezen leden niet van belang. Er is dus sprake van een combinatie. Er zijn dan ${\displaystyle {\tbinom {8}{3}}={\tfrac {8!}{3!\cdot (8-3)!}}={\tfrac {8!}{6!}}=56}$ mogelijkheden om de commissie samen te stellen. Als de functie binnen de commissie wél van belang is, is er sprake van een variatie.

Combinatie met herhaling

Illustratie

Wat hierboven staat zijn combinaties zonder herhaling. Combinaties met herhaling zijn daarop terug te voeren. Bij keuze van ${\displaystyle k}$ elementen van ${\displaystyle n}$ verschillende types met herhaling bedraagt het aantal mogelijkheden:

${\displaystyle {{(n+k-1)!} \over {k!(n-1)!}}={{n+k-1} \choose {k}}={{n+k-1} \choose {n-1}}}$

Voorbeeld

Er zijn dezelfde karweitjes die worden door tien personen moeten opgeknapt, ${\displaystyle k=3}$ en ${\displaystyle n=10}$. De karweitjes kunnen door drie verschillende personen worden gedaan, maar iemand kan ook twee of drie karweitjes doen. Elke mogelijkheid is een herhalingscombinatie, daarvan zijn er:

${\displaystyle {\frac {(10+3-1)!}{3!(10-1)!}}=220}$

namelijk:

${\displaystyle {\tbinom {10}{1}}=10}$ met steeds 3 keer dezelfde persoon: 000, 111, ..., 999;

${\displaystyle {\tbinom {10}{1}}{\tbinom {9}{1}}=90}$ met 2 keer dezelfde persoon en 1 andere: 001, 002, ...998;

${\displaystyle {\tbinom {10}{3}}=120}$ met 3 verschillende personen: 012, 013, 014, ..., 789.

Websites

• MathWorld. Combination.