Combinaison

Un article de Wikivisual, l'encyclopédie libre.

Pour les articles homonymes, voir Combinaison (homonymie). Image:Disambig.svg

En mathématiques, lorsque nous choisissons k objets parmi n objets discernables (numérotés de 1 à n) et que l’ordre dans lequel les objets sont placés (ou énumérés) n’a pas d’importance, nous pouvons les représenter par un ensemble à k éléments. Par exemple, quand nous tirons simultanément plusieurs cartes dans un jeu de cartes, nous obtenons une main et la place des cartes dans la main n’importe pas ; ou au jeu du loto, le tirage final ne dépend pas de l’ordre d’apparition des boules obtenues.

Soient E un ensemble fini de cardinal n et k un entier naturel. Les combinaisons de cet ensemble sont ses sous-ensembles (ou ses parties). Une k-combinaison de E (ou k-combinaison sans répétition de E, ou encore combinaison sans répétition de n éléments pris k à k) est une partie à k éléments de E.

Nous notons <math>\mathcal P_k(E)</math> l’ensemble des k-combinaisons de E.

L’ensemble <math>\mathcal P_k(E)</math> des combinaisons à k éléments de E, est fini et son cardinal se note traditionnellement en France <math>C_n^k</math>, mais de plus en plus <math>{n \choose k},</math> comme dans les autres pays, et <math>C_n^k=\frac{A_n^k}{k!}</math>, où <math>A_n^k</math> est le nombre de k-arrangements de E.
Si k≤n alors

<math>C_n^k=\frac{n(n-1)\ldots (n-k+1)}{k!}</math>

qui peut aussi s'écrire si k≤n alors

Démonstration :

Si k=0 alors il n’y a qu’une seule partie à 0 élément, l’ensemble vide, donc <math>\mathcal P_0(E)=\{\emptyset\}</math>. Mais <math>A_n^0=1</math> et 0!=1 d’où l’égalité.
Si k>n alors il n’existe pas de partie à k éléments dans un ensemble à n éléments, donc <math>\mathcal P_k(E)=\emptyset</math> et comme <math>A_n^k=0</math>, la formule est vérifiée.
Si 1≤k≤n alors nous définissons sur l’ensemble des arrangements sans répétitions de E (ou des k-listes distinctes de E) une relation d’équivalence :

Deux arrangements sont équivalents, s’il existe une permutation à k éléments qui envoie l’un sur l’autre.
Deux arrangements sont alors équivalents si et seulement s’ils correspondent à la même partie à k éléments de E. Une classe d’équivalence est alors une combinaison et il y a autant de classes que de combinaisons. Mais chaque classe contient k! arrangements qui sont en relation ; d’après la réciproque du lemme des bergers il y a donc <math>\frac{A_n^k}{k !}</math> classes ou combinaisons.