Combinaison

qui, en utilisant la notation factorielle , peut être exprimé de manière compacte comme

chaque fois que . Cette formule peut être déduite du fait que chaque k -combinaison d'un ensemble S de n éléments a des permutations telles que ou . L'ensemble de toutes les k -combinaisons d'un ensemble S est souvent noté .

Une combinaison est une sélection de n éléments pris k à la fois, répétition . Pour désigner les combinaisons avec répétition, on utilise souvent les termes k -combinaison avec répétition, k - multiensemble [ ou k -sélection . Si, dans l'exemple précédent, il était possible d'avoir deux fruits de chaque espèce, il y aurait trois autres sélections de deux éléments : une avec deux pommes, une avec deux oranges et une avec deux poires.

Bien que l'ensemble des trois fruits soit suffisamment petit pour permettre d'établir une liste complète des combinaisons, cette méthode devient impraticable lorsque la taille de l'ensemble augmente. Par exemple, une main de poker peut être décrite comme une combinaison de 5 cartes ( k = 5) tirées d'un jeu de 52 cartes ( n = 52). Les 5 cartes de la main sont toutes différentes, et leur ordre n'a pas d'importance. Il existe 2 598 960 combinaisons possibles, et la probabilité de tirer une main quelconque au hasard est de 1/2 598 960.

Le nombre de k -combinaisons d'un ensemble S de n éléments est souvent noté k dans les ouvrages de combinatoire élémentaire , ou par une variante telle que k = k, k = k , k = k , k = k , ou encore k = k (cette dernière forme est standard en français, roumain, russe et chinois). Ce même nombre apparaît cependant dans de nombreux autres contextes mathématiques, où il est noté k (souvent lu « n parmi k ») ; notamment, il figure comme coefficient dans la formule binomiale k = k, d'où son nom de coefficient binomial. On peut définir k = k pour tout entier naturel k par la relation k = k + k.

d'où il ressort clairement que

et plus encore

pour .n" $nk>n$n

Pour montrer que ces coefficients comptent les k -combinaisons de S , on peut d'abord considérer une collection de n variables distinctes X _s étiquetées par les éléments s de S , et étendre le produit sur tous les éléments de S :

Il comporte 2n ^termes distincts correspondant à tous les sous-ensembles de S , chaque sous-ensemble donnant le produit des variables correspondantes X_{_s} . En posant maintenant tous les X _{_s} égaux à la variable non étiquetée X , de sorte que le produit devienne

pour 0 < k < n , ce qui découle de triangle de Pascal .

Pour déterminer un coefficient binomial individuel, il est plus pratique d'utiliser la formule

Le numérateur donne le nombre de k -permutations de n , c'est-à-dire de séquences de k éléments distincts de S , tandis que le dénominateur donne le nombre de telles k -permutations qui donnent la même k -combinaison lorsque l'ordre est ignoré.

Lorsque k dépasse n /2, la formule ci-dessus contient des facteurs communs au numérateur et au dénominateur, et leur simplification donne la relation suivante :

pour 0 ≤ k ≤ n . Ceci exprime une symétrie qui est évidente à partir de la formule binomiale, et peut également être comprise en termes de k -combinaisons en prenant le complément d'une telle combinaison, qui est une

où n ! désigne la factorielle de n . Elle est obtenue à partir de la formule précédente en multipliant le dénominateur et le numérateur par 0\\\displaystyle {\binom {n-1}{k}}{\frac {n}{nk}}&\quad { ext{si }}k0\end{cases}}.

Avec les cas de base , ceux-ci permettent le calcul successif respectivement de tous les nombres de combinaisons du même ensemble (une ligne du triangle de Pascal), de k -combinaisons d'ensembles de tailles croissantes et de combinaisons avec un complément de taille fixe

On peut aussi utiliser la formule en termes de factorielles et annuler les facteurs du numérateur par des parties des facteurs du dénominateur, après quoi seule la multiplication des facteurs restants est nécessaire :

Un autre calcul alternatif, équivalent au premier, est basé sur l'écriture

ce qui donne

L'évaluation de cette expression, entière . En effet, chaque division produit un coefficient binomial, ce qui évite tout reste.

L'utilisation de la formule symétrique en termes de factorielles sans effectuer de simplifications donne un calcul assez long :