Combinaison (mathématiques)

Combinaison (mathématiques): Pour les articles homonymes, voir 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. Les combinaisons servent donc, entre autres, en combinatoire. 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.

Sommaire

1 Définition mathématique

1.1 Définition

1.2 Démonstration

2 Calcul du nombre de combinaisons

3 Énumération des combinaisons

4 Notes

5 Voir aussi

5.1 Liens internes

Définition mathématique

Définition

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). 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 ${n \choose k}$ (lu « k parmi n » ) ou $C_n^k\,$ (lu « combinaison de k parmi n »), la première notation étant préconisée par la norme ISO 31-11, et $C_n^k=\tfrac{A_n^k}{k!}$ , où $A_n^k$ est le nombre de $k$ -arrangements de $E$ .

Avec la formule pour $A_n^k$ on obtient $C_n^k=\frac{n(n-1)\ldots (n-k+1)}{k!}$ , qui pour $k \leq n$ peut aussi s'écrire : $C_n^k=\frac{n!}{k!(n-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)=\{\varnothing\}$ . 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)=\varnothing$ et comme $A_n^k=0$ , la formule est vérifiée.

Si $1 \leq k \leq 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 $\tfrac{A_n^k}{k !}$ classes ou combinaisons.

Calcul du nombre de combinaisons

Un algorithme efficace^[1] pour calculer le nombre de combinaisons de k éléments parmi n, utilise les identités suivantes (0 ≤ k ≤ n) :

$\binom n k = \binom n{n-k}$ , $\binom{n+1}{k+1} = \frac{(n+1)}{(k+1)}\binom n k$ et $\binom n 0 = 1$

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 :

$\binom n k = \frac{(n-k+1)}{1}\cdot\frac{(n-k+2)}{2}\cdot \cdots \cdot \frac{n}{k}$

À 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).

Le calcul peut s'effectuer par une simple boucle itérative (boucle for).

Exemple en pratique d'un calcul de combinaisons :

$\binom 5 4 = \frac{5!}{4!\times (5-4)!} = \frac{5\times 4\times 3\times 2\times 1}{4\times 3\times 2\times 1\times (5-4)!}=\frac{5}{1!}=5$

On voit que la division des factorielles de 5 et de 4 ont été directement simplifiées :

$\frac{5\times 4\times 3\times 2\times 1}{4\times 3\times 2\times 1} \mbox{ devient } 5$

Énumération des combinaisons

Soient A un ensemble à n éléments, b un objet qui n'est pas dans A, et k un entier naturel. Alors on montre facilement l'identité :

$\mathcal P_{k+1}(A\cup\{b\})=\mathcal P_{k+1}(A)\cup\left\{X\cup\{b\}\mid X\in\mathcal P_k(A)\right\}$ ( $\mathcal P_{k}(A)=\varnothing$ si k > n)

(cette identité est connue pour avoir pour conséquence directe la formule de récurrence permettant de construire le triangle de Pascal : $\tbinom{n+1}{k+1}=\tbinom{n}{k+1}+\tbinom{n}{k}$ ). Cette identité peut être exploitée pour un algorithme énumérant les combinaisons, par exemple des n premiers entiers.

Notes

↑ C'est par exemple celui utilisé par la bibliothèque de programmes de calcul arithmétique en précision arbitraire GMP, voir (en) Binomial coefficients algorithm.

Voir aussi

Liens internes

Coefficient binomial

Combinatoire

Combinaison avec répétition

Arrangement

Arrangement avec répétition

Permutation

Permutation avec répétition

Portail des mathématiques

Catégorie :
Analyse combinatoire

Contenu soumis à la licence CC-BY-SA. Source : Article Combinaison (mathématiques) de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

Combinaison (Mathématiques) — Pour les articles homonymes, voir 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 … Wikipédia en Français
Combinaison (mathematiques) — Combinaison (mathématiques) Pour les articles homonymes, voir 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… … Wikipédia en Français
Combinaison Linéaire — En mathématiques, les combinaisons linéaires sont un concept central de l algèbre linéaire et d autres domaines des mathématiques connexes. La majeure partie de cet article traite des combinaisons linéaires dans le contexte d espace vectoriel sur … Wikipédia en Français
Combinaison lineaire — Combinaison linéaire En mathématiques, les combinaisons linéaires sont un concept central de l algèbre linéaire et d autres domaines des mathématiques connexes. La majeure partie de cet article traite des combinaisons linéaires dans le contexte d … Wikipédia en Français
Combinaison Avec Répétition — Sommaire 1 Première approche 2 Une autre représentation 3 Nombre de combinaisons avec répétition 4 Une troisième dé … Wikipédia en Français
Combinaison avec repetition — Combinaison avec répétition Sommaire 1 Première approche 2 Une autre représentation 3 Nombre de combinaisons avec répétition 4 Une troisième dé … Wikipédia en Français
Mathematiques de la relativite generale — Mathématiques de la relativité générale Les mathématiques de la relativité générale se réfèrent à différentes structures et techniques mathématiques utilisées par la théorie de la relativité générale d Albert Einstein. Les principaux outils… … Wikipédia en Français
Mathématiques De La Relativité Générale — Les mathématiques de la relativité générale se réfèrent à différentes structures et techniques mathématiques utilisées par la théorie de la relativité générale d Albert Einstein. Les principaux outils utilisés dans cette théorie géométrique de la … Wikipédia en Français
Mathematiques du Sudoku — Mathématiques du Sudoku Grille de Sudoku classique … Wikipédia en Français
Mathématiques Du Sudoku — Grille de Sudoku classique … Wikipédia en Français

Mark and share
Search through all dictionaries
Translate…
Search Internet

Share the article and excerpts