Permutaties en combinaties, de verschillende manieren waarop objecten uit een set kunnen worden geselecteerd, meestal zonder vervanging, om subsets te vormen. Deze selectie van subsets wordt een permutatie genoemd als de volgorde van selectie een factor is, een combinatie als volgorde geen factor is. Door te kijken naar de verhouding tussen het aantal gewenste subsets en het aantal mogelijke subsets voor veel kansspelen in de 17e eeuw, gaven de Franse wiskundigen Blaise Pascal en Pierre de Fermat een aanzet tot de ontwikkeling van combinatoriek en kansrekening.
combinatoriek: binomiale coëfficiënten
n objecten wordt een permutatie genoemd van n dingen die tegelijk worden genomen. Het aantal permutaties is
De concepten en verschillen tussen permutaties en combinaties kunnen worden geïllustreerd door alle verschillende manieren te onderzoeken waarop een paar objecten kan worden geselecteerd uit vijf te onderscheiden objecten - zoals de letters A, B, C, D en E. Als beide de geselecteerde letters en de volgorde van selectie worden overwogen, dan zijn de volgende 20 resultaten mogelijk:
Elk van deze 20 verschillende mogelijke selecties wordt een permutatie genoemd. Ze worden in het bijzonder de permutaties van vijf objecten genoemd, twee per keer, en het aantal van dergelijke permutaties wordt aangegeven door het symbool 5 P 2, lees "5 permute 2." In het algemeen, als er n voorwerpen verkrijgbaar uit te kiezen en permutaties (P) dienen te worden gevormd via k van de voorwerpen tegelijk, is het aantal verschillende permutaties mogelijk aangeduid door het symbool n P k. Een formule voor de evaluatie is n P k = n! / (N - k)! De uitdrukking n! - lees "n faculteit" - geeft aan dat alle opeenvolgende positieve gehele getallen van 1 tot en met n samen vermenigvuldigd moeten worden, en 0! is gedefinieerd als gelijk aan 1. Met deze formule is het aantal permutaties van vijf genomen objecten bijvoorbeeld twee tegelijk
(Voor k = n, n P k = n! Dus voor 5 objecten zijn er 5! = 120 arrangementen.)
Voor combinaties worden k-objecten geselecteerd uit een set van n objecten om subsets te produceren zonder volgorde. In tegenstelling tot het vorige permutatievoorbeeld met de overeenkomstige combinatie, zijn de AB- en BA-subsets niet langer verschillende selecties; door dergelijke gevallen te elimineren, blijven er slechts 10 verschillende mogelijke subsets over: AB, AC, AD, AE, BC, BD, BE, CD, CE en DE.
Het aantal van dergelijke subsets wordt aangegeven met n C k, lees "n kies k". Voor combinaties, aangezien k-objecten k! arrangementen, er zijn k! niet te onderscheiden permutaties voor elke keuze van k-objecten; vandaar de permutatieformule delen door k! geeft de volgende combinatieformule:
Dit is hetzelfde als de binomiale coëfficiënt (n, k) (zie binominale stelling). Zo is het aantal combinaties van vijf objecten twee tegelijk genomen
De formules voor n P k en n C k worden telformules genoemd, omdat ze kunnen worden gebruikt om het aantal mogelijke permutaties of combinaties in een bepaalde situatie te tellen zonder ze allemaal op te hoeven noemen.
