Combinatoire
Définition
L'analyse combinatoire (ou dénombrement) est l'art de dénombrer des possibilités.
Principes multiplicatif et additif
Ces principes sont à la base de tout dénombrement.
Principe multiplicatif
Soit une personne qui possède :
- deux pantalons \( {\color{ForestGreen}P_1} \) et \( {\color{ForestGreen}P_2} \)
- trois chemises \( {\color{crimson}C_1} \), \( {\color{crimson}C_2} \) et \( {\color{crimson}C_3} \)
- deux vestes \( {\color{navy}V_1} \) et \( {\color{navy}V_2} \)
Un arbre de choix permet de visualiser les manières dont elle peut s'habiller.
Chaque chemin de la gauche vers la droite représente une manière de s'habiller (soit 12 manières).
On remarque que le nombre total de chemins est le produit des nombres de choix à chaque étape du parcours : \( {\color{ForestGreen}2} \times {\color{crimson}3} \times {\color{navy}2} = 12 \).
C'est le principe multiplicatif :
\[ \fbox{$ \text{Nombre de possibilités} = n_1 \times n_2 \times \cdots \times n_p $} \]
Avec :
- \( p \) le nombre d'étapes
- \( n_1 \) le nombre de choix à l'étape 1
- \( n_2 \) le nombre de choix à l'étape 2
- \( n_p \) le nombre de choix à l'étape \( p \)
Principe additif (ou distinction de cas)
On applique une restriction à l'exemple précédent : le pantalon \( P_1 \) ne va pas du tout avec la chemise \( C_3 \).
La symétrie de l'arbre est brisée.
Il ne reste que 10 manières de s'habiller :
On retrouve ce résultat en faisant une distinction de cas :
- on a \( 1 \times 2 \times 2 = 4 \) possibilités pour le pantalon \( P_1 \)
- on a \( 1 \times 3 \times 2 = 6 \) possibilités pour le pantalon \( P_2 \)
Au total ça fait \( 4 + 6 = 10 \) possibilités.
C'est le principe additif (ou la distinction de cas) :
\[ \fbox{$ \text{Nombre de possibilités} = m_1 + m_2 + \cdots + m_r $} \]
Avec :
- \( r \) le nombre de cas
- \( m_1 \) le nombre de possibilités du cas 1
- \( m_2 \) le nombre de possibilités du cas 2
- \( m_r \) le nombre de possibilités du \( r \)-ième cas
Arrangements, permutations et combinaisons
Ces méthodes permettent de déterminer de combien de façons on peut disposer des objets dans différentes configurations.
La différence réside dans la prise en compte de l'ordre :
| Arrangements / Permutations | Combinaisons |
|---|---|
| L'ordre est important | L'ordre n'est pas important |
| \( AB ≠ BA \) | \( AB = BA \) |
Les Anglo-Saxons se limitent à deux termes (permutations and combinations).
Dans les formules :
- \( n \) désigne l'ensemble complet des objets
- \( k \) désigne le nombre d'objets à choisir
Arrangements avec répétitions
Combien de mots à \( 3 \) lettres peut-on former avec les lettres A et B ?
- pour chaque lettre du mot à former on dispose de \( 2 \) choix : A ou B
- donc \( 2 \times 2 \times 2 = 2^3 \) mots
Dans un arrangement avec répétition :
- \( k ≥ n \)
- un objet peut être choisi plusieurs fois (avec répétition)
- d'où la similitude avec un tirage avec remise
\[ \fbox{$ \bar{A}_{n}^k = \underbrace{ n \times n \times \cdots \times n}_{k \ \text{fois}\relax} = n^k $} \]
- \( \bar{A}_n^k \) est le coefficient d'arrangements
- la barre sur le \( A \) est une convention qui signifie avec répétitions
Arrangements / Permutations sans répétitions
De combien de façons 6 personnes peuvent-elles s'assoir sur un banc de 6 places ?
- on choisit une des 6 personnes pour la place 1
- on choisit une des 5 personnes restantes pour la place 2
- …
- à la fin il reste une seule personne pour la place 6
Le nombre de possibilités est \( 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 \).
Cette opération :
- s'abrège \( 6! \) et se prononce factorielle de \( 6 \)
- la notation \( n! \) (factorielle de \( n \)) a été introduite par le mathématicien alsacien Christian Kramp en 1808
\[ \fbox{$ n! = P_n = n \times (n−1) \times \cdots \times 2 \times 1 $} \]
Par convention \( \fbox{$ 0! = 1 $} \) :
\[\begin{aligned} n! &= n \times (n−1) \times (n−2) \times \cdots \times 2 \times 1 \\ \\ {\color{DarkGoldenrod}(n-1)!} &= (n−1) \times (n−2) \times \cdots \times 2 \times 1 \\ \\ \frac{n!}{n} &= \frac{\cancel{n} \times (n−1) \times (n−2) \times \cdots \times 2 \times 1}{\cancel{n}\relax} \\ &= (n−1) \times (n−2) \times \cdots \times 2 \times 1 \\ &= {\color{DarkGoldenrod}(n-1)!}\\ \\ \frac{n!}{n} &= (n-1)! \\ \frac{1!}{1} &= (1-1)! \\ 1 &= 0! \\ \end{aligned}\]
Pratiquement tout ce qui concerne les arrangements et les combinaisons est basé sur la factorielle.
Visualisation : combien de mots à \( 3 \) lettres peut-on former avec les lettres A, B, C sans les répéter ?
\[ 3 \times 2 \times 1 = 3! = 6 \]
Arrangements partiels sans répétitions
De combien de façons 6 personnes peuvent-elles s'assoir sur un banc de 4 places quand deux personnes doivent rester debout ?
- on sait trouver les façons d'arranger toutes les personnes : \( 6! \)
- mais on doit s'arrêter à 4 personnes
- il y a une astuce pour faire ce calcul plus facilement : on divise par les personnes laissées de côté : \( 2! \)
\[ \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{2 \times 1} = 6 \times 5 \times 4 \times 3 \]
Plus généralement :
- touver le nombre de façons d'arranger tous les objets
- diviser par le nombre de façons d'ordonner les objets laissés de côté
\[ \fbox{$ A_{n}^k = \frac{n!}{(n - k)!} $} \]
Visualisation : de combien de façons peut-on ordonner 2 lettres d'un ensemble de 4 lettres A, B, C et D ?
\[ \frac{\text{Arrangements de tous les objets}\relax}{\text{Arrangements des objets laissés de côté}\relax} = \frac{4 \times 3 \times 2 \times 1}{2 \times 1} = 12 \]
Combinaisons sans répétitions
L'ordre ne compte pas, \( AB \) et \( BA \) ne forment qu'une seule combinaison :
- on sait trouver les arrangements de \( k \) objets parmi \( n \) avec \( A_{n}^k \)
- on sait trouver toutes les manières de ranger \( k \) objets avec \( k! \)
- il suffit donc de calculer les arrangements sans ordre \( \frac{A_{n}^k}{k!} \)
\[ \fbox{$ C_{n}^k = \frac{A_{n}^k}{k!} = \frac{1}{k!} \times \frac{n!}{(n - k)!} = \frac{n!}{k! \times (n - k)!} $} \]
\( C_{n}^k \) est le coefficient binomial noté \( \binom{n}k \) par les anglophones.
Visualisation : de combien de façons peut-on choisir 3 lettres d'un ensemble de 4 lettres A, B, C et D ?
\[ \frac{4!}{3! \times (4 - 3)!} = \frac{4 \times 3 \times 2 \times 1}{3 \times 2 \times 1} = 4 \]
Combinaisons avec répétitions
Soit 5 fruits (\( n = 5 \)) différents notés A, B, C, D et E.
De combien de façons peut-on composer un panier de 4 fruits (\( k = 4 \)) en remettant à chaque fois le fruit tiré dans le panier ?
Détail d'une première possibilité :
| Tirage | Choix | Opérations | Composition du panier |
|---|---|---|---|
| 1 | A B C D E | On choisit B | B |
| 2 | A |
B est remis à la fin, on choisit B à nouveau | B, B |
| 3 | A |
B est remis à la fin, on choisit A | B, B, A |
| 4 | A est remis à la fin, on choisit D | B, B, A, D |
Remettre à chaque fois le fruit tiré dans le panier ajoute \( k - 1 \) choix possibles :
\[ \underbrace{ \underbrace{ A \ B \ C \ D \ E }_{ n } \ \underbrace{ B \ B \ A }_{ k - 1 \ \text{duplications} } }_{ n + k - 1 } \]
Le nombre final de choix possibles est donc \( n + k - 1 \).
Ensuite, puisque l'ordre ne compte pas, il faut supprimer les possibilités redondantes telles que BBAD et ADBB qui sont une seule combinaison.
Pour cela on représente chaque fruit tiré par un X :
XXXX
Puis on ajoute des séparateurs | pour répartir les X par type de fruit :
X | XX | | X |
A | B | C | D | E
Cette disposition représente un panier de :
- 1 fruit A
- 2 fruit B
- 0 fruit C
- 1 fruit D
- 0 fruit E
Toutes les façons de disposer les X et les | représentent toutes les façons de composer un panier.
Les compter revient à chercher le nombre de combinaisons sans répétitions pour \( k = 4 \) (X) et \( n = 8 \) (X + |) :
\[ \frac{n!}{k! \times (n - k)!} = \frac{\relax{\color{ForestGreen}8!}\relax}{4! \times 4!} = 70 \]
On remarque que \( {\color{ForestGreen}8!} \) au numérateur correspond aux nombres de possibilités \( n + k - 1 \).
On peut donc remplacer \( n \) par \( n + k - 1 \) dans la formule des combinaisons sans répétitions :
\[\begin{aligned} \frac{\relax{\color{ForestGreen}n}!}{k! \times ({\color{DarkGoldenrod}n} - k)!} &= \frac{({\color{ForestGreen}n + k - 1})!}{k! \times ({\color{DarkGoldenrod}n + k - 1} - k)!} \\ &= \frac{(n + k - 1)!}{k! \times (n - 1)!} \\ \end{aligned}\]
D'où la formule générale permettant de trouver le résultat directement :
\[ \fbox{$ \bar{C}_{n}^k = \binom{n + k - 1}k = \frac{(n + k - 1)!}{k! \times (n - 1)!} $} \]
Récapitulatif
Joint