Combinaison sans répétition

Les combinaisons sont un concept de mathématiques, plus précisément de combinatoire, décrivant les différentes façons de choisir un nombre donné d'objets dans un ensemble de taille donnée, lorsque les objets sont discernables et que l'on ne se soucie pas de l'ordre dans lequel les objets sont placés ou énumérés. Le nom complet, bien que peu usité est combinaison sans répétition de n éléments pris k à k. Autrement dit, les combinaisons de taille k d'un ensemble E de cardinal n sont les sous-ensembles de E qui ont pour taille k. Contrairement aux arrangements, les combinaisons s'intéressent uniquement aux éléments choisis parmi l'ensemble, et non à l'ordre dans lequel ils sont tirés. Un exemple est la main obtenue en tirant simultanément k cartes dans un jeu de n cartes. De même, au jeu du loto, le tirage de 6 numéros parmi 49 ne fait pas référence à l'ordre de tirage des boules, mais au tirage final vu comme un ensemble non ordonné de 6 numéros. Les combinaisons sont utilisées, entre autres, en dénombrement et en probabilités. Soit E un ensemble fini de cardinal n et k un entier naturel. Les combinaisons de cet ensemble sont ses sous-ensembles (ou ses parties). On note l’ensemble des k-combinaisons de E. L’ensemble est fini et son cardinal est le coefficient binomial , aussi noté . On a : où est le nombre de k-arrangements de E et k! est la factorielle de k. Avec la formule pour , on obtient , qui pour k ≤ n peut aussi s'écrire : Un algorithme efficace pour calculer le nombre de combinaisons de k éléments parmi n, utilise les identités suivantes (0 ≤ k ≤ n) : et La première permet de réduire le nombre d'opérations à effectuer en se ramenant à k ≤ n/2. Les deux suivantes permettent de montrer que : À chaque étape de calcul on effectue d'abord la multiplication puis la division pour obtenir un nombre entier (c'est un coefficient binomial), c'est-à-dire que l'on peut employer la division entière. Les calculs intermédiaires restent d'un ordre de grandeur voisin du résultat final (ce ne serait pas le cas si par exemple on utilisait la première formule et la fonction factorielle).