Combinaisons avec répétition
Partie A - Étude d'un exemple
On souhaite ranger 4 boules identiques dans 3 casiers.
Voici un exemple de rangement possible :
Rangement de 4 boules dans 3 casiers
On cherche à déterminer le nombre de rangements possibles. Pour cela on modélise chaque rangement à l'aide d'une suite de caractères $ \star $ et | de la manière suivante :
- chaque boule est représenté par un caractère $ \star $
- les caractères | sont utilisés comme séparateurs entre les différents casiers.
Par exemple, le rangement précédent (trois boules dans le premier casier, aucune dans le second et une dans le troisième) sera représenté par la suite de caractères :
$ \star \star \star $ | | $ \star $
Il faut alors 6 caractères ( 4 $ \star $ et 2 | ) pour représenter un rangement.
À l'aide de cette modélisation, déterminer le nombre de façons de ranger 4 boules identiques dans 3 casiers.
Partie B - Étude du cas général
On dispose, cette fois de $ p $ boules et de $ n $ casiers.
On représentera chacun des rangement possible par une suite de caractères $ \star $ et | comme indiqué dans la partie A.
- Combien de caractères $ \star $ et | seront nécessaires pour modéliser un rangement ?
- De combien de manières peut-on ranger $ p $ boules dans $ n $ casiers ?
Partie C - Applications
$ x, y $ et $ z $ étant trois entiers naturels, combien l'équation :
$ x + y + z = 6 $admet-elle de solutions ?
- On dispose de bonbons de trois parfums différents : caramels, chocolats, pralinés.
On souhaite réaliser des sachets de 10 bonbons.
Combien de sortes de sachets peut-on réaliser ?
Corrigé
Partie A - Étude d'un exemple
La suite de caractères utilisée pour modéliser un rangement utilise 4 caractères $ \star $ (qui correspondent aux 4 boules) et 2 caractères séparateurs | (le nombre de séparateurs est égal au nombre de casiers moins un).
On utilise donc, au total, 6 caractères pour représenter un rangement de 4 boules dans 3 casiers.
Chaque suite de caractères ainsi formée représente un rangement et chaque rangement peut être modélisé par une telle représentation (on dit qu'il y a « bijection » entre les rangements et leurs représentations).
Le nombre de rangements possibles est donc égal au nombre de représentations comportant 4 $ \star $ parmi 6 caractères.
Ce nombre est donc :
Remarque : On peut également raisonner sur la position des caractères | ; on trouve le même résultat $ \begin{pmatrix} 6 \\ 2 \end{pmatrix} = 15. $
Partie B - Étude du cas général
Avec un raisonnement identique à celui de la partie A., on constate alors que chaque rangement peut être représenté par une suite de caractères comprenant $ p $ étoiles et $ n - 1 $ séparateurs (soit au total $ n + p - 1 $ caractères).
Le nombre de ces suites est alors :
Partie C - Applications
Si l'on écrit 6 sous la forme 1+1+1+1+1+1, on remarque que résoudre l'équation $ x+ y + z = 6 $ dans $ \mathbb{N} ^3 $ revient à regrouper les termes 1 dans la somme 1+1+1+1+1+1 en trois groupes;
par exemple :6 = (1+1+1) + (1+1) + (1)
donnera 6 = 3 + 2 + 1 et la solution (3; 2; 1)
et
6 = (1+1+1+1) + (1+1) + ()
donnera 6 = 4 + 2 + 0 et la solution (4; 2; 0).
On est donc ramené au problèmes qui consiste à placer 6 objets (les nombres 1) dans 3 casiers (l'intérieur des parenthèses).
D'après la partie B., ce nombre est :
$ N = \begin{pmatrix} 6+3 - 1 \\ 6 \end{pmatrix} = \begin{pmatrix} 8 \\ 6 \end{pmatrix} = 28 $.
Remarque : sur le modèle de l'exercice Somme des chiffres et dénombrement, on peut écrire un programme en Python pour lister ces 28 solutions qui sont :
(0; 0; 6); (0; 1; 5); (0; 2; 4); (0; 3; 3); (0; 4; 2); (0; 5; 1); (0; 6; 0); (1; 0; 5); (1; 1; 4); (1; 2; 3); (1; 3; 2); (1; 4; 1); (1; 5; 0); (2; 0; 4); (2; 1; 3); (2; 2; 2); (2; 3; 1); (2; 4; 0); (3; 0; 3); (3; 1; 2); (3; 2; 1); (3; 3; 0); (4; 0; 2); (4; 1; 1); (4; 2; 0); (5; 0; 1); (5; 1; 0); (6; 0; 0)Si l'on note $ x $ le nombre de caramels, $ y $ le nombre de chocolats et $ z $ le nombre de pralinés, le nombre de sachets de 10 bonbons que l'on peut réaliser est égal au nombre de solutions dans $ \mathbb{N} ^3 $ de l'équation :
$ x + y + z = 10 $D'après la partie B., ce nombre est :
$ N = \begin{pmatrix} 10+3 - 1 \\ 10 \end{pmatrix} = \begin{pmatrix} 12 \\ 10 \end{pmatrix} = 66 $.