Permutacions i combinacions, les diverses maneres en què es poden seleccionar objectes d'un conjunt, generalment sense substitució, per formar subconjunts. Aquesta selecció de subconjunts s'anomena permutació quan l'ordre de selecció és un factor, una combinació quan l'ordre no és un factor. Tenint en compte la relació entre el nombre de subconjunts desitjats i el nombre de tots els subconjunts possibles per a molts jocs d'atzar al segle XVII, els matemàtics francesos Blaise Pascal i Pierre de Fermat van impulsar el desenvolupament de la combinatòria i la teoria de probabilitats.
combinatori: coeficients binomials
n objectes s'anomena permutació de n coses preses a la vegada. El nombre de permutacions és
Els conceptes i diferències entre permutacions i combinacions es poden il·lustrar mitjançant l'examen de totes les maneres diferents de seleccionar un parell d'objectes entre cinc objectes distingibles, com ara les lletres A, B, C, D i E. Si ambdues es consideren les lletres seleccionades i l’ordre de selecció, a continuació són possibles els 20 resultats següents:
Cadascuna d’aquestes 20 seleccions possibles diferents s’anomena permutació. En particular, s'anomenen permutacions de cinc objectes presos dos a la vegada, i el nombre d'aquestes permutacions possibles es denota amb el símbol 5 P 2, es llegeix "5 permute 2." En general, si hi ha n d'objectes disponibles per seleccionar, i les permutacions (P) s'han de formar mitjançant k dels objectes alhora, el nombre de permutacions diferents és indicat pel símbol n P k. Una fórmula per a la seva avaluació és n P k = n! / (N - k)! L’expressió n! —Legeix “n factorial” - indica que s’han de multiplicar tots els nombres enters positius consecutius d’1 a i inclosos n, i 0! es defineix per igual a 1. Per exemple, utilitzant aquesta fórmula, el nombre de permutacions de cinc objectes presos dos a la vegada és
(Per a k = n, n P k = n! Així, per a 5 objectes hi ha 5! = 120 arranjaments.)
Per a combinacions, k objectes són seleccionats entre un conjunt de n objectes per produir subconjunts sense ordenar. Contrastant l'exemple de permutació anterior amb la combinació corresponent, els subconjunts AB i BA ja no són seleccions diferents; eliminant aquests casos només queden 10 subconjunts diferents: AB, AC, AD, AE, BC, BD, BE, CD, CE i DE.
El nombre d'aquests subconjunts es denota per n C k, llegiu "n escolliu k". Per a combinacions, ja que k objectes tenen k! arranjaments, hi ha k! permutacions no distingibles per a cada elecció d'objectes k; per tant, dividiu la fórmula de permutació per k! proporciona la següent fórmula de combinació:
Això és el mateix que el coeficient binomial (n, k) (vegeu el teorema de binomi). Per exemple, el nombre de combinacions de cinc objectes presos dos a la vegada és
Les fórmules de n P k i n C k s’anomenen fórmules de recompte ja que es poden utilitzar per comptar el nombre de permutacions o combinacions possibles en una situació determinada sense haver d’enumerar-les totes.
