Combinaisons

On utilise les combinaisons lorsqu’on choisit un nombre donné d’objets dans un ensemble, et que l’ordre dans lequel on les choisit n’a pas d’importance. Un exemple typique est le « loto 6 sur 49 » : dans une urne, il y a 49 numéros et l’on en tire 6, sans se soucier de l’ordre du tirage.

Démonstration de la formule

Roue de la fortune

Prenons un ensemble M, par exemple M = {a ; b ; c ; d ; e}. Une combinaison de k éléments est alors un sous-ensemble K ⊂ M qui contient exactement k éléments. Comme K est un ensemble, l’ordre n’a évidemment pas d’importance. Ainsi, une combinaison de 3 éléments de M pourrait être {a ; b ; d} ou {b ; c ; d}.

La différence avec les arrangements est que, pour ceux-ci, l’ordre comptait : (a ; b ; e) et (e ; b ; a) sont deux arrangements différents, mais la même combinaison, puisque (a ; b ; e) et (e ; b ; a) contiennent les mêmes éléments. Pour les combinaisons, leur ordre ne nous intéresse pas.

On peut néanmoins utiliser les arrangements pour obtenir la formule du nombre de combinaisons différentes. On sait que le nombre d’arrangements de k éléments parmi un ensemble de n éléments est exactement

$\frac{n!}{(n - k)!} .$

Si l’on comptait tous les arrangements de 3 éléments de l’ensemble M = {a ; b ; c ; d ; e}, on obtiendrait $\frac{5!}{2!} = 60$ arrangements différents. Mais on y trouverait aussi, pour chaque triplet, toutes ses permutations. Par exemple, on aurait le triplet abc, mais aussi acb, bac, bca, cab et cba. Cela fait six arrangements différents, mais une seule combinaison, puisqu’ils ont tous les mêmes éléments.

Combien de permutations différentes possède un triplet donné ? Exactement 3!. Autrement dit, il existe exactement 3! fois plus d’arrangements de 3 éléments que de combinaisons de 3 éléments. Au lieu de compter une seule combinaison, on compte 3! arrangements, un pour chaque permutation du triplet. Ainsi, si l’on divise le nombre d’arrangements par 3!, on obtient le nombre de combinaisons.

Généralisons ce raisonnement : le nombre de combinaisons de k éléments d’un ensemble de n éléments est égal à

$(\binom{n}{k}) = \frac{\frac{n!}{(n - k)!}}{k!},$

c’est-à-dire le nombre d’arrangements divisé par k!, qui est le nombre de permutations de chaque k-uplet. On simplifie la formule :

$(\binom{n}{k}) = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Exemple : le nombre de combinaisons de 2 éléments de l’ensemble {a ; b ; c} est

$(\binom{3}{2}) = \frac{3!}{1! \cdot 2!} = 3$

et ce sont les combinaisons {a ; b}, {a ; c} et {b ; c}.

Pour les combinaisons de 3 éléments de l’ensemble initial M = {a ; b ; c ; d ; e}, on obtient

$(\binom{5}{3}) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

et ce sont les combinaisons suivantes : {a ; b ; c}, {a ; b ; d}, {a ; b ; e}, {a ; c ; d}, {a ; c ; e}, {a ; d ; e}, {b ; c ; d}, {b ; c ; e}, {b ; d ; e}, {c ; d ; e}.

Coefficient binomial

Ce nombre se note à l’aide du coefficient binomial (dans des manuels plus anciens, on trouve aussi la notation $C_{n}^{k}$ ), de la forme

$(\binom{n}{k})$

C’est une sorte de fraction sans barre (que l’on écrit tout de même par habitude), mais avec des parenthèses, qui ne sont pas facultatives : elles doivent figurer. On le lit « k parmi n ». Sa valeur est le nombre de combinaisons calculé plus haut :

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Ainsi, si l’on a un ensemble de 5 éléments et que l’on en choisit 4, leur nombre total est

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Relations de base

Pour le coefficient binomial et n ∈ ℕ^*, on a :

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Pour n, k ∈ ℕ et k ≤ n, on a :

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

Et pour n, k ∈ ℕ et k < n, on a :

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Calculatrice

La calculatrice suivante calcule le coefficient binomial $(\binom{n}{k})$ .

Exercices corrigés

Commençons par le « loto 6 sur 49 » évoqué plus haut. On tire 6 boules d’une urne qui en contient 49. Combien de tirages différents peut-on obtenir ?

Tout d’abord : l’ordre des numéros compte-t-il ? Non, on ne parie que sur les numéros, pas sur leur ordre. On utilise donc les combinaisons. Il y a 49 boules et l’on en tire 6, on obtient le coefficient binomial

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13 983 816$

Il existe donc au total 13 983 816 tirages possibles. Ce qui donne, soit dit en passant, une probabilité de gagner avec un seul pari de 1/13 983 816, soit 0,00000715112 %.
Louis, grand séducteur, se trouve au milieu d’un bal de village où il y a 13 jeunes femmes qui l’intéressent. Louis sait qu’il peut, au cours de la soirée, faire le bonheur de 4 femmes différentes. Parmi combien de quatuors différents Louis peut-il choisir ?

C’est à nouveau un exemple simple de combinaisons : l’ordre n’a pas d’importance, Louis sera tout aussi bon avec la première qu’avec la dernière. On obtient donc un ensemble de 13 femmes, parmi lesquelles on en choisit à chaque fois 4. Cela donne le coefficient binomial

$(\binom{13}{4}) = 715.$
Tu as un groupe de cinquante personnes, moitié hommes, moitié femmes. Combien existe-t-il de trios différents qui ne soient pas composés de personnes d’un seul sexe (c’est-à-dire qu’il ne doit pas y avoir trois hommes ou trois femmes dans le trio) ?

C’est un peu plus compliqué. Si l’on exclut les trios composés de personnes d’un seul sexe, il reste deux possibilités pour composer le trio : deux hommes et une femme, ou un homme et deux femmes. Le nombre de combinaisons du premier cas (deux hommes et une femme) est le même que celui du second. Il suffit donc de calculer le nombre de combinaisons du premier cas et de le multiplier par deux. C’est à nouveau facile. On détermine le nombre de combinaisons de paires d’hommes, soit 2 parmi 25, et on le multiplie par le nombre de combinaisons d’une femme (soit 25, voir les relations de base ci-dessus, et plus précisément la deuxième ligne). On multiplie ce résultat par deux et l’on obtient le résultat final.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
Dans une boîte, il y a 15 articles, dont 4 sont défectueux. De combien de façons peut-on choisir 6 articles de sorte que :
- aucun ne soit défectueux ? On choisit 6 articles parmi les 15 − 4 = 11 articles non défectueux. On obtient ainsi le coefficient binomial
  
  $(\binom{11}{6}) = 462.$
- un seul soit défectueux ? On choisit alors un ensemble qui contient 5 articles fonctionnels et 1 défectueux. Il y a 11 articles fonctionnels et 4 défectueux. On applique le principe multiplicatif et l’on obtient le résultat :
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- au plus un soit défectueux ? On utilise les résultats précédents. Il y a 462 façons de choisir exactement 6 articles fonctionnels, et 1848 façons de choisir 5 articles fonctionnels et 1 défectueux. On applique donc le principe additif : on additionne ces résultats et l’on obtient ce que l’on cherche, c’est-à-dire au plus un article défectueux (soit aucun, soit exactement un). Le résultat est donc : 462 + 1848 = 2310.

Chapitres: Dénombrement, Arrangements, Permutations, Combinaisons, K-uplets avec répétition, Combinaisons avec répétition, Combien existe-t-il de codes PIN différents ?

« Précédent: Permutations

Suivant: K-uplets avec répétition »