Combinatoire

Définition

La combinatoire est l'art de dénombrer des possibilités.

Principes multiplicatif et additif

Ces principes sont à la base de tout dénombrement.

Principe multiplicatif

Soit une personne qui possède :

deux pantalons $ {\color{ForestGreen}P_1} $ et $ {\color{ForestGreen}P_2} $
trois chemises $ {\color{RubineRed}C_1} $, $ {\color{RubineRed}C_2} $ et $ {\color{RubineRed}C_3} $
deux vestes $ {\color{NavyBlue}V_1} $ et $ {\color{NavyBlue}V_2} $

Un arbre de choix permet de visualiser les manières dont elle peut s'habiller.

Chaque chemin de la gauche vers la droite représente une manière de s'habiller (soit 12 manières).

On remarque que le nombre total de chemins est le produit des nombres de choix à chaque étape du parcours : $ {\color{ForestGreen}2} \times {\color{RubineRed}3} \times {\color{NavyBlue}2} = 12 $.

C'est le principe multiplicatif :

\[ \fbox{$ \text{Nombre de possibilité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 précédent : le pantalon $ P_1 $ ne va pas du tout avec la chemise $ C_3 $.

La symétrie de l'arbre est brisée.

Il ne reste que 10 manières de s'habiller :

On retrouve ce résultat en faisant une distinction de cas :

on a $ 1 \times 2 \times 2 = 4 $ possibilités pour le pantalon $ P_1 $
on a $ 1 \times 3 \times 2 = 6 $ possibilités pour le pantalon $ P_2 $

Au total ça fait $ 4 + 6 = 10 $ possibilités.

C'est le principe additif (ou la distinction de cas) :

\[ \fbox{$ \text{Nombre de possibilités} = m_1 + m_2 + \cdots + m_r $} \]

Avec :

$ r $ le nombre de cas à distinguer
$ m_k $ le nombre de possibilités au $ k $-ième cas
- $ m_k $ peut être déterminé par le principe multiplicatif

Permutations, arrangements et combinaisons

Ces opérations permettent d'obtenir différentes configurations de $ k $ objets parmi un ensemble de $ n $ objets.

Les Anglo-Saxons se limitent à deux termes : permutations et combinations.

Le logigramme ci-dessous montre qu'une permutation est un cas spécial d'arrangement :

Permutations et factorielle

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
…
à la fin, pour la place 6, il reste une seule personne

Le nombre de possibilités est $ 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 $ (principe multiplicatif).

Cette opération s'abrège $ 6! $ et se prononce factorielle de $ 6 $.

La notation $ n! $ (factorielle de $ n $) a été introduite par le mathématicien alsacien Christian Kramp en 1808 :

Je me sers de la notation trés simple n! pour désigner le produit de nombres décroissans depuis n jusqu'à l'unité, savoir n(n - 1)(n - 2) ... 3.2.1. L'emploi continuel de l'analyse combinatoire que je fais dans la plupart de mes démonstrations, a rendu cette notation indispensable.

Le nombre de permutations de $ n $ objets représente toutes les façons de ranger ces objets :

\[ \fbox{$ P_n = n! = n \times (n−1) \times \cdots \times 2 \times 1 $} \]

Par convention $ \fbox{$ 0! = 1 $} $.

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 avec répétitions

Combien de mots à $ 3 $ lettres peut-on former avec un alphabet de $ 2 $ lettres ?

Pour chaque lettre du mot on dispose de $ 2 $ choix, donc $ 2 \times 2 \times 2 = 2^3 $ mots :

Les arrangements possibles pour $ k $ objets (ici 3 lettres) d'un ensemble de $ n $ objets (ici A et B) sont :

\[ \fbox{$ \bar{A}_{n}^k = \underbrace{ n \times n \times \cdots \times n}_{k \ \text{fois}} = n^k $} \]

On peut choisir plusieurs fois le même objet, d'où la similitude avec un tirage avec remise.

Arrangements partiels sans répétitions

De combien de façons 6 personnes peuvent-elles s'assoir sur un banc de 4 places quand deux personnes doivent rester debout ?

Le nombre de possibilités est $ 6 \times 5 \times 4 \times 3 = 360 $ (principe multiplicatif).

Le nombre d'arrangements de $ k $ objets parmi $ n $ objets est le coefficient d'arrangements noté $ A_n^k $ :

\[ \fbox{$ A_n^k = \underbrace{ n \times (n -1) \times \cdots \times (n - k + 1)}_{k \ \text{fois}} $} \]

Une autre façon de l'exprimer est de s'intéresser aux $ n - k $ objets laissés de côté.

On sait que :

$ n! $ correspond à toutes les façons d'ordonner tous les $ n $ objets
$ A_{n}^k $ correspond à toutes les façons d'ordonner les $ k $ objets qui nous intéressent
$ (n - k)! $ correspond à toutes les façons d'ordonner les $ n - k $ objets laissés de côté

Donc d'après le principe multiplicatif…

\[ A_{n}^k \times (n - k)! = n! \]

…puis on divise chaque membre de l'égalité…

\[ \frac{A_{n}^k \times (n - k)!}{(n - k)!} = \frac{n!}{(n - k)!} \]

…d'où la formule générale :

\[ \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}}{\text{Arrangements des objets laissés de côté}} = \frac{4 \times 3 \times 2 \times 1}{2 \times 1} = \frac{4!}{(4 - 2)!} \]

Combinaisons partielles sans répétitions

L'ordre ne compte pas : deux arrangements de deux lettres AB et BA ne forment qu'une seule combinaison.

On appelle coefficient binomial le nombre de combinaisons possibles de $ k $ objets parmi $ n $ objets distincts, noté :

$ C_{n}^k $ par les francophones (nombre de combinaisons de $ k $ parmi $ n $)
$ \binom{n}k $ par les anglophones ($ k $ parmi $ n $)

Son calcul est identique à celui des arrangements partiels avec une étape supplémentaire car on ne tient pas compte de l'ordre des objets choisis :

\[ \frac{ \text{Arrangements de tous les objets} } { \text{Arrangements des objets choisis} \times \text{Arrangements des objets laissés de côté} } \]

D'où la formule générale :

\[ \fbox{$ C_{n}^k = \binom{n}k = \frac{n!}{k! \times (n - k)!} $} \]

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 \]

Autre manière d'expliquer :

on sait qu'il y a $ A_{n}^k = \frac{n!}{(n - k)!} $ manières d'arranger $ k $ objets parmi $ n $
une fois les $ k $ objets obtenus, il y a $ k! $ manières de les ranger
il y a donc $ \frac{A_{n}^k}{k!} $ de tirer $ k $ objets parmi $ n $ sans les ranger
$ C_{n}^k = \frac{A_{n}^k}{k!} = \frac{1}{k!} \times \frac{n!}{(n - k)!} $

Combinaisons partielles avec répé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é :

Choix	Possibilités	Opérations	Composition du panier
1	A B C D E	On choisit B	B
2	A B C D E B	B est remis à la fin, on choisit B à nouveau	B, B
3	A B C D E B B	B est remis à la fin, on choisit A	B, B, A
4	A B C D E B B A	A est remis à la fin, on choisit D	B, B, A, D

On se retrouve avec $ k - 1 $ fruits supplémentaires parmi lesquels choisir au 4ème choix.

Le nombre final de possibilités de choix est donc $ n + k - 1 $ :

\[ \underbrace{ \underbrace{ \cancel{A} \ \cancel{B} \ C \ \cancel{D} \ E }_{ n } \ \underbrace{ \cancel{B} \ B \ A }_{ k - 1 } }_{ n + k - 1 } \]

Maintenant, il faut supprimer les possibilités redondantes, car BBAD et ADBB sont une seule combinaison.

Pour cela, on représente les $ n + k - 1 $ possibilités comme des points sur une ligne, ici $ 5 + 4 - 1 = 8 $ :

........

On transforme $ n - 1 $ points en barres verticales, ici $ 5 - 1 = 4 $ :

.|..||.|

Ces barres représentent des "séparateurs" entre chaque type de fruit (1 fruit A, 2 fruits B et 1 fruit D) :

 . |.. |   | . |
 A | B | C | D | E

Notre problème se transforme en un problème de points et de barres verticales : combien de combinaisons de ces deux objets peut-on avoir ?

Cela revient à chercher le nombre de combinaisons partielles sans répétitions pour $ k = 4 $ (points) et $ n = 8 $ (points + barres verticales) :

\[ \frac{n!}{k! \times (n - k)!} = \frac{{\color{ForestGreen}8!}}{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 partielles sans répétitions :

\[\begin{align} \frac{{\color{ForestGreen}n}!}{k! \times ({\color{ForestGreen}n} - k)!} &= \frac{({\color{ForestGreen}n + k - 1})!}{k! \times ({\color{ForestGreen}n + k - 1} - k)!} \\ &= \frac{(n + k - 1)!}{k! \times (n - 1)!} \\ &= \frac{(8)!}{4! \times 4!} \\ &= 70 \\ \end{align}\]

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)!} $} \]

Sources

Précédent Suites géométriques Tous ⏎