Combinatoire et dénombrement

Les principes fondamentaux du dénombrement

Le dénombrement est l'art de compter le nombre d'éléments d'un ensemble fini. Il repose sur deux principes fondamentaux :

1. Le principe additif : Si une tâche peut être accomplie de $n_1$ manières différentes OU de $n_2$ manières différentes (et que ces manières sont mutuellement exclusives), alors le nombre total de manières d'accomplir la tâche est $n_1 + n_2$.

2. Le principe multiplicatif : Si une tâche est composée de $k$ étapes successives, et que la première étape peut être accomplie de $n_1$ manières, la deuxième de $n_2$ manières, ..., et la $k$-ième de $n_k$ manières, alors le nombre total de manières d'accomplir la tâche est $n_1 \times n_2 \times \dots \times n_k$. Ce principe s'applique lorsque les choix sont indépendants et successifs.

Méthode
Identifier la nature de la tâche à dénombrer : s'agit-il de choix mutuellement exclusifs (principe additif) ou de choix successifs et indépendants (principe multiplicatif) ?
Décomposer la tâche en sous-tâches ou en cas distincts.
Appliquer le principe additif si les sous-tâches sont des alternatives (OU).
Appliquer le principe multiplicatif si les sous-tâches sont des étapes consécutives (ET).

Exemple
Un restaurant propose un menu du jour composé d'une entrée, d'un plat et d'un dessert. Il y a 3 choix d'entrées, 4 choix de plats et 2 choix de desserts. De combien de façons différentes un client peut-il composer son menu du jour ?

Corrigé pas à pas
La composition du menu est une tâche qui se décompose en trois étapes successives et indépendantes :
1. Choisir une entrée : 3 possibilités.
2. Choisir un plat : 4 possibilités.
3. Choisir un dessert : 2 possibilités.

Puisque ces choix sont successifs et indépendants, nous appliquons le principe multiplicatif.
Le nombre total de menus différents est $3 \times 4 \times 2 = 24$. Un client peut composer son menu de 24 façons différentes.

Erreurs fréquentes
Confondre le principe additif et le principe multiplicatif : le principe additif s'applique pour des choix 'OU', le principe multiplicatif pour des choix 'ET' successifs.
Oublier de considérer toutes les étapes ou tous les cas possibles lors de la décomposition de la tâche.

Arrangements et Permutations

Ces concepts s'appliquent lorsque l'ordre des éléments est important.

1. Arrangement avec répétition : Un arrangement avec répétition de $k$ éléments parmi $n$ est une suite ordonnée de $k$ éléments choisis parmi $n$ éléments distincts, où un même élément peut être choisi plusieurs fois. Le nombre d'arrangements avec répétition est $n^k$.

2. Arrangement sans répétition : Un arrangement sans répétition de $k$ éléments parmi $n$ est une suite ordonnée de $k$ éléments distincts choisis parmi $n$ éléments distincts. Le nombre d'arrangements sans répétition est noté $A_n^k$ et est égal à $\frac{n!}{(n-k)!}$, où $n!$ (factorielle de $n$) est le produit de tous les entiers de 1 à $n$ ($n! = n \times (n-1) \times \dots \times 1$), avec $0! = 1$.

3. Permutation : Une permutation de $n$ éléments distincts est un arrangement sans répétition de $n$ éléments choisis parmi $n$. C'est donc une manière d'ordonner ces $n$ éléments. Le nombre de permutations de $n$ éléments est $P_n = n!$. C'est un cas particulier de l'arrangement sans répétition où $k=n$.

Méthode
Identifier l'ensemble d'éléments disponibles ($n$).
Déterminer le nombre d'éléments à choisir ($k$).
Évaluer si l'ordre des éléments est important. Si oui, il s'agit d'un arrangement ou d'une permutation.
Évaluer si la répétition des éléments est autorisée. Si oui, c'est un arrangement avec répétition ($n^k$). Si non, c'est un arrangement sans répétition ($A_n^k$).
Si $k=n$ et qu'il n'y a pas de répétition, il s'agit d'une permutation ($n!$).

Exemple
a) Combien de mots de 3 lettres peut-on former avec les lettres A, B, C, D, E si les répétitions sont autorisées ?
b) Combien de podiums (1er, 2ème, 3ème) sont possibles pour une course de 8 chevaux, en supposant qu'il n'y a pas d'ex-aequo ?

Corrigé pas à pas
a) Il s'agit de choisir 3 lettres parmi 5, l'ordre compte (ABC est différent de BCA) et les répétitions sont autorisées (AAA est un mot possible). C'est un arrangement avec répétition.
$n = 5$ (nombre de lettres disponibles : A, B, C, D, E)
$k = 3$ (nombre de lettres dans le mot)
Le nombre de mots est $n^k = 5^3 = 125$.

b) Il s'agit de choisir 3 chevaux parmi 8 pour former un podium. L'ordre compte (être 1er est différent d'être 2ème) et les répétitions ne sont pas autorisées (un cheval ne peut pas être à la fois 1er et 2ème). C'est un arrangement sans répétition.
$n = 8$ (nombre de chevaux)
$k = 3$ (nombre de places sur le podium)
Le nombre de podiums est $A_8^3 = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \times 7 \times 6 = 336$. Il y a 336 podiums possibles.

Erreurs fréquentes
Oublier que l'ordre est un critère discriminant majeur entre arrangements/permutations et combinaisons.
Ne pas distinguer entre arrangements avec et sans répétition, ce qui conduit à des calculs erronés.
Confondre $n$ et $k$ dans les formules.

Combinaisons

Une combinaison est un choix d'éléments où l'ordre n'a pas d'importance.

Combinaison sans répétition : Une combinaison sans répétition de $k$ éléments parmi $n$ est un sous-ensemble de $k$ éléments distincts choisis parmi $n$ éléments distincts, où l'ordre des éléments n'importe pas. Le nombre de combinaisons sans répétition est noté $\binom{n}{k}$ (lu 'k parmi n') et est égal à $\frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}$.

Remarque : Les combinaisons avec répétition existent mais ne sont généralement pas au programme de Terminale en France.

Méthode
Identifier l'ensemble d'éléments disponibles ($n$).
Déterminer le nombre d'éléments à choisir ($k$).
Évaluer si l'ordre des éléments est important. Si l'ordre n'a PAS d'importance, il s'agit d'une combinaison.
Évaluer si la répétition des éléments est autorisée. Dans le cadre du programme de Terminale, les combinaisons sont toujours sans répétition.
Appliquer la formule du coefficient binomial : $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.

Exemple
Un comité de 3 personnes doit être formé à partir d'un groupe de 10 personnes. Combien de comités différents peuvent être formés ?

Corrigé pas à pas
Il s'agit de choisir 3 personnes parmi 10. L'ordre dans lequel les personnes sont choisies pour le comité n'a pas d'importance (le comité {Alice, Bob, Carole} est le même que {Bob, Alice, Carole}). Il n'y a pas non plus de répétition (une personne ne peut pas être choisie plusieurs fois pour le même comité).
C'est donc une combinaison sans répétition.
$n = 10$ (nombre total de personnes)
$k = 3$ (nombre de personnes à choisir pour le comité)

Le nombre de comités différents est $\binom{10}{3} = \frac{10!}{3!(10-3)!} = \frac{10!}{3!7!} = \frac{10 \times 9 \times 8 \times 7!}{ (3 \times 2 \times 1) \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 10 \times 3 \times 4 = 120$. Il y a 120 comités différents possibles.

Erreurs fréquentes
Confondre combinaisons et arrangements : la distinction clé est l'importance de l'ordre. Si l'ordre compte, c'est un arrangement ; si l'ordre ne compte pas, c'est une combinaison.
Erreurs de calcul de la factorielle ou du coefficient binomial.

Distinguer arrangement, permutation et combinaison

1. Étape 1 : Analyser la situation. Lisez attentivement l'énoncé et identifiez ce qui doit être compté.
2. Étape 2 : L'ordre est-il important ?
   • Si OUI (par exemple, un classement, un code, une suite de lettres), il s'agit d'un arrangement ou d'une permutation.
   • Si NON (par exemple, un groupe de personnes, une main de cartes, un sous-ensemble), il s'agit d'une combinaison.
3. Étape 3 : La répétition est-elle autorisée ? (Applicable si l'ordre est important)
   • Si OUI (par exemple, tirage avec remise, chiffres d'un code où les chiffres peuvent se répéter), c'est un arrangement avec répétition ($n^k$).
   • Si NON (par exemple, tirage sans remise, personnes distinctes), c'est un arrangement sans répétition ($A_n^k$).
4. Étape 4 : Le nombre d'éléments choisis est-il égal au nombre total d'éléments disponibles ? (Applicable si l'ordre est important et la répétition non autorisée)
   • Si OUI ($k=n$), c'est une permutation ($n!$).
   • Si NON ($k<n$), c'est un arrangement sans répétition ($A_n^k$).
5. Étape 5 : Appliquer la formule appropriée.

Exemple
Dans un jeu de 52 cartes, on tire 3 cartes successivement et sans remise. Combien de tirages différents y a-t-il si :
a) On note l'ordre des cartes.
b) On ne note pas l'ordre des cartes.

Corrigé pas à pas
Dans les deux cas, $n=52$ (nombre total de cartes) et $k=3$ (nombre de cartes tirées). Les tirages sont sans remise, donc sans répétition.

a) L'ordre des cartes est noté. Cela signifie que (As de pique, Roi de cœur, Dame de carreau) est différent de (Roi de cœur, As de pique, Dame de carreau). Puisque l'ordre compte et qu'il n'y a pas de répétition, il s'agit d'un arrangement sans répétition.
Nombre de tirages : $A_{52}^3 = \frac{52!}{(52-3)!} = \frac{52!}{49!} = 52 \times 51 \times 50 = 132600$.

b) L'ordre des cartes n'est pas noté. Cela signifie que le groupe de cartes (As de pique, Roi de cœur, Dame de carreau) est considéré comme identique, quel que soit l'ordre dans lequel elles ont été tirées. Puisque l'ordre ne compte pas et qu'il n'y a pas de répétition, il s'agit d'une combinaison sans répétition.
Nombre de tirages : $\binom{52}{3} = \frac{52!}{3!(52-3)!} = \frac{52!}{3!49!} = \frac{52 \times 51 \times 50}{3 \times 2 \times 1} = 52 \times 17 \times 25 = 22100$.

Calculer un coefficient binomial $\binom{n}{k}$

1. Étape 1 : Identifier $n$ et $k$. $n$ est le nombre total d'éléments disponibles, et $k$ est le nombre d'éléments choisis. Assurez-vous que $0 \le k \le n$.
2. Étape 2 : Appliquer la formule. La formule du coefficient binomial est $\binom{n}{k} = \frac{n!}{k!(n-k)!}$.
3. Étape 3 : Simplifier les factorielles. Développez les factorielles et simplifiez les termes communs pour faciliter le calcul. Rappelez-vous que $n! = n \times (n-1)!$.

Exemple
Calculez $\binom{7}{3}$.

Corrigé pas à pas
Nous avons $n=7$ et $k=3$.

Étape 1 : Identifier $n$ et $k$.
$n=7$, $k=3$.

Étape 2 : Appliquer la formule.
$\binom{7}{3} = \frac{7!}{3!(7-3)!} = \frac{7!}{3!4!}$

Étape 3 : Simplifier les factorielles.
$\frac{7!}{3!4!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (4 \times 3 \times 2 \times 1)}$
Nous pouvons simplifier le $4!$ au numérateur et au dénominateur :
$\frac{7 \times 6 \times 5 \times 4!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1}$

Effectuons le calcul :
$\frac{7 \times 6 \times 5}{3 \times 2 \times 1} = \frac{210}{6} = 35$.

Donc, $\binom{7}{3} = 35$.

Principes fondamentaux

• Principe additif (OU) : $N = n_1 + n_2 + \dots + n_k$
• Principe multiplicatif (ET) : $N = n_1 \times n_2 \times \dots \times n_k$

Factorielle

• $n! = n \times (n-1) \times \dots \times 1$
• $0! = 1$

Arrangements (l'ordre compte)

• Avec répétition : $n^k$
• Sans répétition : $A_n^k = \frac{n!}{(n-k)!}$

Permutations (cas particulier d'arrangement sans répétition où $k=n$)

• $P_n = n!$

Combinaisons (l'ordre ne compte pas)

• Sans répétition : $\binom{n}{k} = \frac{n!}{k!(n-k)!}$

Propriétés des coefficients binomiaux

• $\binom{n}{k} = \binom{n}{n-k}$
• $\binom{n}{0} = 1$
• $\binom{n}{n} = 1$
• $\binom{n}{1} = n$
• $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$ (Formule de Pascal)