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.$$