Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Combinaison sans répétition
Résumé
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.