Prérequis
Aucun prérequis.
Résumé
Bon nombre de problèmes de combinatoire consistent à dénombrer les façons d'effectuer une certaine tâche. On pourra ainsi se demander de combien de manières il est possible de placer des convives autour d'une table ou encore combien il existe de tirages différents au Lotto. Il existe pour ce faire plusieurs formules s'appliquant à différents cas. Nous présentons dans ce chapitre toutes les formules de permutations, combinaisons et arrangements, ainsi que des exemples d'utilisation de celles-ci.
Ce chapitre a été
écrit par N. Radu et
mis en ligne le 8 décembre 2014.
1. Permutations
Sans répétition
Le nombre de permutations d'un ensemble $\{a_1, \ldots, a_n\}$ de $n$ objets distincts est simplement le nombre de façons de ranger ces $n$ objets, c'est-à-dire de les ordonner.
Exemples concrets :
- On possède $6$ livres que l'on désire ranger sur une étagère. De combien de manières peut-on procéder ?
- Combien le mot MATHS possède-t-il d'anagrammes (ceux-ci ne doivent pas forcément être des mots de la langue française) ?
Formule (permutations sans répétition)
Le nombre de permutations de $n$ objets distincts est donné par
$$P_n = n!$$
Note : la notation $n!$ désigne le produit $n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1$, il s'agit de la factorielle de $n$. En particulier, on définit $0! = 1$ (car il s'agit du produit d'aucun terme).
Démonstration
Étant donnés $n$ objets $\{a_1, \ldots, a_n\}$, on a $n$ choix de placement pour le premier objet $a_1$. Une fois celui-ci placé, il reste $(n-1)$ positions possibles pour le deuxième objet $a_2$. Ainsi de suite, jusqu'au dernier objet pour lequel il reste une seule position. En multipliant ces nombres, on a finalement $n \cdot (n-1) \cdot \ldots \cdot 1 = n!$ façons de ranger les $n$ objets.
Solutions des exemples :
- On a donc $6! = 720$ manières de ranger nos $6$ livres sur une étagère.
- On a $5$ lettres différentes, qui sont les $5$ objets, et on se demande de combien de façons on peut les permuter. Il y a $5! = 120$ permutations, dont celle redonnant le mot MATHS, donc ce mot possède $119$ anagrammes.
Avec répétitions
Le même problème se pose lorsque certains objets sont identiques. On a cette fois $n$ objets, dont $r_1$ sont de type $1$, $r_2$ sont de type $2$, ..., et $r_k$ sont de type $k$ (avec $r_1 + \ldots + r_k = n$). À nouveau, on se demande de combien de manières on peut ranger ces $n$ objets, mais on considère cette fois que deux objets du même type sont identiques (ainsi, inverser deux objets du même type ne change pas le rangement).
Exemples concrets :
- Jacques a $6$ enfants et $6$ balles : une balle bleue, deux balles rouges et trois balles vertes. De combien de manières peut-il donner une balle à chaque enfant ?
- Combien le mot MAMAN possède-t-il d'anagrammes ?
Formule (permutations avec répétitions)
Le nombre de permutations de $n$ objets dont $r_1$ sont de type $1$, ..., $r_k$ sont de type $k$, est donné par
$$P(n; r_1, \ldots, r_k) = \frac{n!}{r_1! \cdot \ldots \cdot r_k!}.$$
Démonstration
On considère d'abord les $n$ objets comme étant distincts. Il y a alors, comme vu précédemment, $n!$ façons de les ranger. Si maintenant nous désirons ne plus distinguer des objets du même type, alors il y a parmi les $n!$ rangements certains rangements équivalents (c'est-à-dire qui sont identiques du point de vue des types). Plus précisément, étant donné un rangement des $n$ objets, on peut permuter les $r_1$ objets de type $1$, les $r_2$ objets de type $2$, ... et les $r_k$ objets de type $k$ et on retombera toujours sur un rangement équivalent. Il y a $r_1!\cdot \ldots \cdot r_k!$ façons d'effectuer ces permutations, ce qui signifie que l'on a des groupes de $r_1!\cdot \ldots \cdot r_k!$ rangements équivalents. Lorsqu'on ne distingue plus les objets du même type, on n'a donc plus $n!$ rangements mais bien
$$\frac{n!}{r_1! \cdot \ldots \cdot r_k!}.$$
Solutions des exemples :
- Jacques a $n = 6$ balles, $r_1 = 1$ de type "bleue", $r_2 = 2$ de type "rouge" et $r_3 = 3$ de type "verte". On souhaite ranger ces $6$ balles (pour les donner aux $6$ enfants), sans distinguer celles ayant le même type. Le nombre de façons de procéder est donc égal à
$$\frac{6!}{3! \cdot 2! \cdot 1!} = \frac{720}{6\cdot 2 \cdot 1} = 60.$$
- Les objets sont à nouveau les lettres, mais on a deux lettres du type M, deux lettres du type A et une lettre du type N, et il y a donc
$$\frac{5!}{2! \cdot 2! \cdot 1!} = \frac{120}{2 \cdot 2 \cdot 1} = 30$$ permutations. Le mot MAMAN possède donc $29$ anagrammes.
Conséquence
Il existe un corollaire immédiat au dernier résultat. En effet, par définition nous savons que le nombre de permutations de $n$ objets (distincts ou non) est toujours un nombre entier. On en déduit donc que le nombre
$$\frac{n!}{r_1!\cdot \ldots \cdot r_k!}$$ est toujours un nombre entier lorsque $r_1 + \ldots + r_k = n$. Cela n'est en fait a priori pas évident ! Certes, on sait que chaque $r_i !$ divise $n!$ puisque $r_i \leq n$, mais il semble beaucoup moins aisé de démontrer que le produit $r_1! \cdot \ldots \cdot r_k!$ divise toujours $n!$. Cela n'est en fait pas facile sans utiliser le fait que cette expression représente un nombre combinatoire entier.
2. Arrangements
Sans répétition
Supposons maintenant être en présence de $n$ objets distincts $\{a_1, \ldots, a_n\}$. Nous nous demandons cette fois-ci de combien de manière on peut prendre $k$ objets parmi ceux-ci et les ranger. Cela revient à se demander de combien de façons différentes on peut choisir $k$ objets parmi les $n$, l'ordre des choix ayant une importance. On parle du nombre d'arrangements de $k$ objets parmi $n$.
Exemples concrets :
- On possède $6$ livres et une étagère pouvant accueillir $4$ livres. De combien de manières peut-on remplir l'étagère (l'ordre des livres ayant son importance) ?
- Combien existe-t-il de nombres à exactement $3$ chiffres distincts, tous non-nuls ?
Formule (arrangements sans répétition)
Le nombre d'arrangements de $k$ objets parmi $n$ (avec $0 \leq k \leq n$) est donné par
$$A^k_n = \frac{n!}{(n-k)!}.$$
Démonstration
Tout comme pour les permutations, on a d'abord $n$ façons de choisir le premier objet, puis $(n-1)$ façons de choisir le deuxième objet, ... et $(n-k+1)$ façons de choisir le $k^\text{ème}$ objet. On a donc $\displaystyle n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}$ façons de choisir $k$ objets parmi $n$ (l'ordre des choix ayant de l'importance).
Solutions des exemples :
- On a $n = 6$ et $k = 4$. le nombre de façons de remplir l'étagère est donc égal à
$$\frac{6!}{(6-4)!} = \frac{720}{2} = 360.$$
- Pour construire un nombre à trois chiffres distincts non-nuls, on a $9$ chiffres disponibles, et on désire en choisir $3$ et les ordonner pour construire le nombre. Il y a donc autant de tels nombres que d'arrangements de $3$ objets parmi $9$, c'est-à-dire
$$\frac{9!}{(9-3)!} = 9\cdot 8 \cdot 7 = 504.$$
Avec répétitions
Les arrangements avec répétitions ne désignent pas le même phénomène que les permutations avec répétitions. Ici, les $n$ objets que nous considérerons seront toujours distincts, mais on pourra cette fois choisir plusieurs fois le même objet dans notre arrangement (d'où le terme
répétition). Cette situation n'a donc plus réellement de sens avec les livres sur une étagère, à moins que l'on dispose de chaque livre en une infinité d'exemplaires (et qu'on peut donc mettre plusieurs exemplaires du même livre sur notre étagère).
Exemples concrets :
- Dix balles numérotées de $1$ à $10$ sont placées dans une urne. À quatre reprises, on pioche une balle, note son numéro et remet la balle dans l'urne. Combien de résultats différents peut-on obtenir après ce processus (l'ordre des numéros notés ayant son importance) ?
- On dispose de $2$ sortes de bonbon, chacune en grande quantité. De combien de manières peut-on donner un bonbon à chaque élève d'une classe de $20$ étudiants ?
Formule (arrangements avec répétitions)
Le nombre d'arrangements avec répétitions de $k$ objets parmi $n$ est donné par
$$B_n^k = n^k.$$
Démonstration
On doit effectuer $k$ choix, et pour chacun de ceux-ci, on a $n$ possibilités. Le nombre de façons d'effectuer ces choix est donc simplement $n \cdot \ldots \cdot n = n^k$.
Solutions des exemples :
- On a dix balles, d'où $n = 10$, et on effectue quatre tirages, d'où $k = 4$. On a donc $10^4 = 10000$ résultats possibles.
- Il y a ici $n = 2$ objets, un objet représentant une sorte de bonbon. On choisit, à $k = 20$ reprises, une des deux sortes. Il y a donc $2^{20}$ manières de distribuer des bonbons aux élèves.
3. Combinaisons
Les combinaisons ressemblent fortement aux arrangements, la seule différence étant que l'ordre des choix n'a maintenant plus d'importance.
Sans répétition
On a $n$ objets distincts et on désire en choisir $k$. Le nombre de combinaisons de $k$ objets parmi $n$ est le nombre de tels choix possibles, l'ordre n'ayant pas d'importance. Par là, on veut dire que c'est l'ensemble des objets choisis qui importe, et qu'on ne prête pas attention à l'ordre dans lequel on effectue les $k$ choix.
Exemples concrets :
- Huit élèves ont décidé de présenter des exposés au reste de la classe. Il y aura un exposé par jour, et chaque exposé est présenté par exactement trois élèves. Combien d'exposé y aura-t-il, au maximum, si deux exposés différents ne peuvent jamais être présentés par les trois mêmes étudiants ?
- Au bowling, il y a $10$ quilles à faire tomber. Pour rendre le jeu plus attrayant, on décide de peindre $4$ des quilles en bleu et les $6$ autres en rouge. Combien de situations différentes pourra-t-on observer lorsque les quilles seront replacées ?
Formule (combinaisons sans répétition)
Le nombre de combinaisons de $k$ objets parmi $n$ (avec $0 \leq k \leq n$) est donné par
$$C_n^k = \frac{n!}{k! \cdot (n-k)!}.$$
Note : Il s'agit de la notation francophone, mais certains privilégient parfois la notation anglophone $\displaystyle{n \choose k}$, où l'ordre de $k$ et $n$ est inversé !
Démonstration
Pour démontrer cette formule, on peut se rendre compte qu'il est possible de compter le nombre d'arrangements (où l'ordre compte) de $k$ objets parmi $n$ en passant par le nombre de combinaisons. En effet, choisir $k$ objets parmi $n$, l'ordre étant important, revient à d'abord les choisir sans tenir compte de l'ordre puis à les ordonner. Une fois qu'ils sont choisis, il y a bien sûr $k!$ façons de les ordonner, ce qui signifie que $A^k_n = C^k_n \cdot k!$ et nous donne directement la formule
$$C_n^k = \frac{A^k_n}{k!} = \frac{n!}{k! \cdot (n-k)!}.$$
Solutions des exemples :
- Le nombre maximal d'exposés est égal au nombre de façons de choisir $3$ élèves parmi $8$, c'est-à-dire
$$\frac{8!}{3! \cdot (8-3)!} = \frac{8\cdot7\cdot6}{3!} = 56.$$
- Au moment de placer les dix quilles, on a $10$ emplacements et on doit simplement décider où on va placer les $4$ quilles bleues. On doit donc choisir $4$ emplacements parmi $10$, ce qui laisse
$$\frac{10!}{4!\cdot (10-4)!} = \frac{10\cdot 9\cdot 8\cdot 7}{4!} = 210$$ possibilités.
Avec répétitions
Encore une fois, on peut avoir la même situation où les répétitions sont permises. On peut donc choisir plusieurs fois le même élément (mais l'ordre n'a toujours pas d'importance).
Exemples concrets :
- On désire acheter un bouquet de $12$ fleurs. Chez le fleuriste, il y a des fleurs rouges, jaunes et bleues. Combien de bouquets différents est-il possible de composer ?
- Combien existe-t-il de triplets $(x, y, z) \in \mathbb{N}^3$ tels que $x+y+z = 100$ ?
Formule (combinaisons avec répétitions)
Le nombre de combinaisons avec répétitions de $k$ objets parmi $n$ est donné par
$$D_n^k = C_{n+k-1}^{k} = \frac{(n+k-1)!}{k! \cdot (n-1)!}.$$
Démonstration
Pour comprendre cette formule, il faut voir les choses un peu autrement. Choisir $k$ objets parmi $n$, avec répétitions possibles, revient à décider combien d'objets du premier type nous allons prendre (disons $x_1$), combien du deuxième type (disons $x_2$), ... et combien du $n^\text{ème}$ type (disons $x_n$). Ces nombres doivent évidemment vérifier $x_1 + \ldots + x_n = k$.
À un tel choix de $x_1, \ldots, x_n$, on peut associer une suite de symboles "o" et "|" comme suit : on écrit $x_1$ symboles "o", puis une barre de séparation "|", puis $x_2$ symboles "o", une barre de séparation, et ainsi de suite jusque $x_n$ symboles "o". Par exemple, pour $n = 4$ et $k = 7$, on peut écrire
$$\text{oo|o|ooo|o} \quad \text{pour} \quad (x_1,x_2,x_3,x_4) = (2,1,3,1),$$ $$\text{|ooooo||oo} \quad \text{pour} \quad (x_1,x_2,x_3,x_4) = (0,5,0,2).$$ Dans une telle suite, il y aura toujours $x_1+\ldots+x_n = k$ symboles "o" et $n-1$ symboles de séparation "|". Bien sûr, à partir d'une suite de symboles vérifiant ces conditions, on peut aisément retrouver les valeurs de $x_1, \ldots, x_n$ (en comptant les "o" entre les "|"). Cela signifie qu'il y a autant de combinaisons que de telles suites de symboles, et trouver le nombre de combinaisons revient juste à compter le nombre de suites de $n+k-1$ symboles : $k$ symboles "o" et $n-1$ symboles "|". Or, cela revient simplement à choisir à quels endroits on place les $k$ symboles "o", et il y a $C^{k}_{n+k-1}$ tels choix possibles (formule pour les combinaisons sans répétitions).
Solutions des exemples :
- Il y a trois types d'objets : les fleurs rouges, les fleurs jaunes et les fleurs bleues. On doit en choisir $12$, il y a donc
$$D^{12}_3 = \frac{(3+12-1)!}{12! \cdot (3-1)!} = \frac{14 \cdot 13}{2} = 91$$ bouquets différents possibles.
- La démonstration précédente devrait donner l'intuition qu'il s'agit d'une combinaison avec répétitions. En effet, on peut se dire que l'on a trois types d'objets : ceux du type $X$, ceux du type $Y$ et ceux du type $Z$. On doit en choisir $100$ (on peut évidemment en prendre plusieurs du même type) et le nombre $x$ sera donné par le nombre d'éléments du type $X$ choisis, $y$ par le nombre d'éléments du type $Y$ et $z$ par ceux du type $Z$. Le nombre de triplets $(x,y,z) \in \mathbb{N}^3$ tels que $x+y+z = 100$ est donc donné par
$$D^{100}_3 = \frac{(3+100-1)!}{100! \cdot (3-1)!} = \frac{102 \cdot 101}{2!} = 5151.$$
4. Récapitulatif
Voici un petit récapitulatif des différentes formules combinatoires présentées dans les sections précédentes.
$$\begin{array}{|c|c|c|l|}
\hline
\textbf{Nom} & \textbf{Notation} & \textbf{Formule} & \qquad \qquad \qquad \qquad \qquad \textbf{Utilisation} \\[2mm]
\hline
\text{Permutations} & P_n & n! & \text{Nombre de permutations de $n$ objets distincts.} \\[2mm]
\hline
\text{Permutations avec répétitions} & \ P(n; r_1, \ldots, r_k) \ & \frac{n!}{r_1! \cdot \ldots \cdot r_k!} & \text{Nombre de permutations de $n$ objets non distincts.} \\[2mm]
\hline
\text{Arrangements} & A^k_n & \frac{n!}{(n-k)!} & \begin{array}{l} \text{Nombre de façons de choisir $k$ objets parmi $n$, l'ordre des choix} \\ \text{ayant de l'importance.} \end{array} \\[2mm]
\hline
\text{Arrangements avec répétitions} & B^k_n & n^k & \begin{array}{l} \text{Nombre de façons de choisir $k$ objets (éventuellement plusieurs} \\ \text{fois le même) parmi $n$, l'ordre des choix ayant de l'importance.}\end{array}\\[2mm]
\hline
\text{Combinaisons} & C^k_n & \frac{n!}{k! \cdot (n-k)!} & \begin{array}{l} \text{Nombre de façons de choisir $k$ objets parmi $n$, l'ordre des choix} \\ \text{n'étant pas important.} \end{array}\\[2mm]
\hline
\ \text{Combinaisons avec répétitions} \ & D^k_n = C^k_{n+k-1} & \ \frac{(n+k-1)!}{k! \cdot (n-1)!} \ &\ \begin{array}{l} \text{Nombre de façons de choisir $k$ objets (éventuellement plusieurs} \\ \text{fois le même) parmi $n$, l'ordre des choix n'étant pas important.} \end{array} \ \\[2mm]
\hline
\end{array}$$