Combinaison

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 carte, 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 $\mathcal P_k(E)$ l’ensemble des k-combinaisons de E.

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

(si k≤n alors $C_n^k=\frac{n(n-1)\ldots (n-k+1)}{k!}$ ).

Démonstration :

Si k=0 alors il n’y a qu’une seule partie à 0 élément, l’ensemble vide, donc $\mathcal P_0(E)=\{\emptyset\}$ . Mais $A_n^0=1$ 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 $\mathcal P_k(E)=\emptyset$ et comme $A_n^k=0$ , 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 $\frac{A_n^k}{k !}$ classes ou combinaisons.

Combinaison

Voyez aussi

See also: Combinaison, Arrangement, Arrangement avec répétition, Coefficient binomial, Combinaison avec répétition, Combinatoire, Lemme des bergers, Mathématiques, Permutation, Permutation avec répétition