Le nombre de k-combinaisons à partir d’un ensemble S donné de n éléments est souvent désigné dans les textes de combinatoire élémentaire par C ( n , k ) {\displaystyle C(n,k)}.
, ou par une variante telle que C k n {\displaystyle C_{k}^{n}}.
, n C k {\displaystyle {}_{n}C_{k}}}
, n C k {\displaystyle {}^{n}C_{k}}
, C n , k {\displaystyle C_{n,k}}
ou encore C n k {\displaystyle C_{n}^{k}}}
(cette dernière forme était standard dans les textes français, roumains, russes, chinois et polonais). Le même nombre apparaît cependant dans de nombreux autres contextes mathématiques, où il est désigné par ( n k ) {\displaystyle {\tbinom {n}{k}}}}.
(souvent lu comme « n choisit k ») ; il apparaît notamment comme un coefficient dans la formule binomiale, d’où son nom de coefficient binomial. On peut définir ( n k ) {\displaystyle {\tbinom {n}{k}}}
pour tous les nombres naturels k à la fois par la relation ( 1 + X ) n = ∑ k ≥ 0 ( n k ) X k , {\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}
d’où il ressort que
( n 0 ) = ( n n ) = 1 , {\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}
et en outre,
( n k ) = 0 {\displaystyle {\binom {n}{k}}=0}
pour k > n.
Pour voir que ces coefficients comptent les k-combinaisons de S, on peut d’abord considérer une collection de n variables distinctes Xs étiquetées par les éléments s de S, et développer le produit sur tous les éléments de S:
∏ s ∈ S ( 1 + X s ) ; {\displaystyle \prod _{s\in S}(1+X_{s});}
il possède 2n termes distincts correspondant à tous les sous-ensembles de S, chaque sous-ensemble donnant le produit des variables Xs correspondantes. Maintenant, en fixant tous les Xs égaux à la variable non étiquetée X, de sorte que le produit devient (1 + X)n, le terme pour chaque k-combinaison de S devient Xk, de sorte que le coefficient de cette puissance dans le résultat est égal au nombre de ces k-combinaisons.
Les coefficients binomiaux peuvent être calculés explicitement de diverses manières. Pour les obtenir tous pour les expansions jusqu’à (1 + X)n, on peut utiliser (en plus des cas de base déjà donnés) la relation de récursion
( n k ) = ( n – 1 k – 1 ) + ( n – 1 k ) , {\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}
pour 0 < k < n, qui découle de (1 + X)n = (1 + X)n – 1(1 + X) ; cela conduit à la construction du triangle de Pascal.
Pour déterminer un coefficient binomial individuel, il est plus pratique d’utiliser la formule
( n k ) = n ( n – 1 ) ( n – 2 ) ⋯ ( n – k + 1 ) k ! {\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}}
.
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 ces 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 annulation donne la relation
( n k ) = ( n n – k ) , {\displaystyle {\binom {n}{k}}}={\binom {n}{n-k}},}
pour 0 ≤ k ≤ n. Cela exprime une symétrie qui est évidente à partir de la formule binomiale, et qui peut aussi être comprise en termes de k-combinaisons en prenant le complément d’une telle combinaison, qui est une (n – k)-combinaison.
Enfin, il existe une formule qui présente cette symétrie directement, et qui a le mérite d’être facile à retenir :
( n k ) = n ! k ! ( n – k ) ! , {\displaystyle {\binom {n}{k}}={{frac {n!}{k !(n-k)!},}
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 (n – k) !)La dernière formule peut être comprise directement, en considérant les n ! permutations de tous les éléments de S. Chacune de ces permutations donne une k-combinaison en sélectionnant ses k premiers éléments. Il y a beaucoup de sélections doubles : toute permutation combinée des k premiers éléments entre eux, et des (n – k) derniers éléments entre eux produit la même combinaison ; ceci explique la division dans la formule.
Des formules ci-dessus découlent les relations entre les nombres adjacents dans le triangle de Pascal dans les trois directions :
( n k ) = { ( n k – 1 ) n – k + 1 k si k > 0 ( n – 1 k ) n n – k si k < n ( n – 1 k – 1 ) n k si n , k > 0 {\displaystyle {\binom {n}{k}}={begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\{\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }k<n\\\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}}
.
Avec les cas de base ( n 0 ) = 1 = ( n n ) {\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}.
, celles-ci permettent de calculer successivement tous les nombres de combinaisons respectivement à partir d’un 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 n – k.
Exemple de comptage de combinaisonsEdit
A titre d’exemple spécifique, on peut calculer le nombre de mains de cinq cartes possibles à partir d’un jeu standard de cinquante-deux cartes comme:
( 52 5 ) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311 875 200 120 = 2 598 960. {\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}
Alternativement, on peut utiliser la formule en termes de factorielles et annuler les facteurs du numérateur contre des parties des facteurs du dénominateur, après quoi seule la multiplication des facteurs restants est nécessaire :
( 52 5 ) = 52 ! 5 ! 47 ! = 52 × 51 × 50 × 49 × 48 × 47 ! 5 × 4 × 3 × 2 × 1 × 47 ! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = ( 26 × 2 ) × ( 17 × 3 ) × ( 10 × 5 ) × 49 × ( 12 × 4 ) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2,598,960. {\displaystyle{begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}{5\times 4\times 3\times 2\times {\cancel {1}\times {\cancel {47!}}}}}\&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3})\times (10\times {\cancel {5}})\times {5})\times 49\times (12\times {\cancel {4})}{{\cancel {5}\times {\cancel {4}\times {\cancel {3}\times {\cancel {2}}}}\&={26\times 17\times 10\times 49\times 12}\&=2{,}598{,}960.\end{alignedat}}
Un autre calcul alternatif, équivalent au premier, repose sur l’écriture
( n k ) = ( n – 0 ) 1 × ( n – 1 ) 2 × ( n – 2 ) 3 × ⋯ × ( n – ( k – 1 ) ) k , {\displaystyle }n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}\times {\frac {(n-2)}{3}\times \cdots \times {\frac {(n-(k-1))}{k},}
ce qui donne
( 52 5 ) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960}
.
Lorsque l’on évalue dans l’ordre suivant, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, cela peut être calculé en utilisant uniquement l’arithmétique des nombres entiers. La raison en est que lors de chaque division, le résultat intermédiaire produit est lui-même un coefficient binomial, de sorte qu’aucun reste ne se produit jamais.
Utiliser la formule symétrique en termes de factorielles sans effectuer de simplifications donne un calcul assez étendu :
( 52 5 ) = n ! k ! ( n – k ) ! = 52 ! 5 ! ( 52 – 5 ) ! = 52 ! 5 ! 47 ! = 80 , 658 , 175 , 170 , 943 , 878 , 571 , 660 , 636 , 856 , 403 , 766 , 975 , 289 , 505 , 440 , 883 , 277 , 824 , 000 , 000 , 000 , 000 120 × 258 , 623 , 241 , 511 , 168 , 180 , 642 , 964 , 355 , 153 , 611 , 979 , 969 , 197 , 632 , 389 , 120 , 000 , 000 , 000 = 2,598,960. {\displaystyle}{begin{aligned}{52 \choose 5}&={\frac {n!}{k !(n-k)!}}={\frac {52!}{5 !(52-5)!}}={\frac {52!}{5!47!}}&.}}\\&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\&=2{,}598{,}960.\end{aligned}}
Enumération des k-combinaisonsEdit
On peut énumérer toutes les k-combinaisons d’un ensemble S donné de n éléments dans un ordre fixe, ce qui établit une bijection d’un intervalle de ( n k ) {\displaystyle {\tbinom {n}{k}}}.
entiers avec l’ensemble de ces k-combinaisons. En supposant que S est lui-même ordonné, par exemple S = { 1, 2, …, n }, il existe deux possibilités naturelles pour ordonner ses k-combinaisons : en comparant d’abord leurs plus petits éléments (comme dans les illustrations ci-dessus) ou en comparant d’abord leurs plus grands éléments. Cette dernière option présente l’avantage que l’ajout d’un nouvel élément le plus grand à S ne modifiera pas la partie initiale de l’énumération, mais ajoutera simplement les nouvelles k-combinaisons de l’ensemble le plus grand après les précédentes. En répétant ce processus, l’énumération peut être étendue indéfiniment avec des k-combinaisons d’ensembles toujours plus grands. Si, en outre, on considère que les intervalles des entiers commencent à 0, la combinaison k à un endroit donné i de l’énumération peut être calculée facilement à partir de i, et la bijection ainsi obtenue est connue sous le nom de système de nombres combinatoires. Elle est également connue sous le nom de « rang »/ »ranking » et « unranking » en mathématiques computationnelles.
Il y a plusieurs façons d’énumérer les k combinaisons. Une façon est de visiter tous les nombres binaires inférieurs à 2n. Choisir les nombres ayant k bits non nuls, bien que cela soit très inefficace même pour un petit n (par exemple, n = 20 nécessiterait de visiter environ un million de nombres alors que le nombre maximum de combinaisons k autorisées est d’environ 186 mille pour k = 10). La position de ces bits 1 dans un tel nombre est une combinaison k spécifique de l’ensemble { 1, …, n }. Une autre méthode simple et plus rapide consiste à suivre les k numéros d’index des éléments sélectionnés, en commençant par {0 .. k-1} (basé sur zéro) ou {1 .. k} (à base de un) comme première combinaison k autorisée, puis en passant de manière répétée à la prochaine combinaison k autorisée en incrémentant le dernier numéro d’indice s’il est inférieur à n-1 (à base de zéro) ou à n (à base de un) ou le dernier numéro d’indice x qui est inférieur au numéro d’indice qui le suit moins un si un tel indice existe et en réinitialisant les numéros d’indice après x à {x+1, x+2, …}.
.