Définition 4.2.1.
-
Une permutation d’un ensemble d’objets est un arrangement ordonné de ces objets.
-
Une \(r-\)permutation d’un ensemble d’objets est un arrangement ordonné de \(r\) objets de l’ensemble.
Section 4.2 Permutations et combinaisons
On peut remarquer que plusieurs des exemples et exercices faits à la section 4.1 font intervenir des méthodes et des expressions qui se ressemblent. Par exemple, on voit souvent apparaître des termes de la forme \(6\times 5\times4 \text{.}\)
Ces expressions sont reliées à des concepts importants en dénombrement, c’est-à-dire les permutations et les combinaisons. On remarque également que plusieurs problèmes difficiles peuvent être résolus en utilisant les mêmes méthodes. On présente donc quelques exemples typiques qu’on peut utiliser pour résoudre une grande catégorie de problèmes.
Finalement, on présente le triangle de Pascal, qui permet de calculer de manière différente le nombre de combinaisons, ainsi que le binôme de Newton, qui utilise le nombre de combinaisons afin de calculer rapidement des expressions de la forme \((x+y)^n\text{.}\)
Sous-section 4.2.1 Les permutations
On considère les deux problèmes de dénombrement suivants. Premièrement, on veut choisir trois personnes parmi un groupe de \(25\) personnes. Deuxièmement, on considère le nombre de podiums différents qu’il peut y avoir dans une course de \(25\) personnes.
Dans les deux cas, on doit choisir trois personnes parmi \(25\text{.}\) Cependant, pour le premier exemple, l’ordre dans lequel on choisit les trois personnes n’a pas d’importance, alors que pour le deuxième exemple, l’ordre est très important! Dans le premier cas, on dira que l’on compte les combinaisons, alors que dans le deuxième cas, on compte les permutations.
Étrangement, il est plus facile de compter le nombre de podiums que de compter le nombre de façons de choisir trois personnes. On commence donc par considérer le deuxième problème, et on retournera au problème de choisir trois personnes parmi \(25\) en 4.2.2 .
En utilisant le principe du produit, on voit rapidement qu’il y a \(25\times24\times23 = 13\ 800 \) podiums différents. Le concept de permutation permet de généraliser cet exemple.
Exemple 4.2.2. Une première permutation.
Soit \(E=\{a,b,c\}\text{.}\) Combien y a-t-il de permutations différentes de l’ensemble \(E\text{?}\)Réponse.
\(6\)
Solution.
Si on veut arranger (de façon ordonnée) les éléments de l’ensemble \(E\text{,}\) cela veut dire qu’on choisit un élément à la première position, un à la deuxième et finalement un à la troisième.
Lorsqu’on choisit l’élément en première position, il y a \(3\) choix possibles. Une fois l’élément fixé à la première position, il reste \(2\) choix pour l’élément à la deuxième position. Finalement, il ne reste qu’un seul choix pour la dernière position. Ainsi, par le principe du produit, il y a \(3\cdot 2\cdot 1 = 6\) permutations possible.
L’exemple précédent semble montrer qu’on peut déterminer le nombre de permutations d’un ensemble de taille finie quelconque. Pour cela, on utilise la notation ci-dessous.
Remarque 4.2.3.
Nous allons insister sur la définition alternative de \(k!\) par récurrence un peu plus tard.
Avec cette nouvelle notation, on est prêt à démontrer la proposition suivante.
Proposition 4.2.4.
Soit \(E\) un ensemble de cardinalité finie \(|E|=n\text{,}\) alors il existe \(n!\) différentes permutations de l’ensemble \(E\text{.}\)De façon similaire, on peut déterminer le nombre de \(r\)-permutations d’un ensemble \(E\) de cardinalité finie \(n\text{.}\) En effet, décrire une \(r\)-permutation est équivalent à décrire une fonction injective \(f: \{1,\dots,r\} \to E \text{.}\) On utilisera une notation particulière pour ce nombre.
Définition 4.2.5.
Le nombre de \(r-\)permutations d’un ensemble \(E\) tel que \(|E|=n\in\ \N\) est noté \(\Permutation{n}{r}\)Proposition 4.2.6.
\(\Permutation{n}{r}=\frac{n!}{(n-r)!}\text{.}\)Démonstration.
Encore une fois, il suffit de remarquer que ceci est équivalent à compter des fonctions injectives \(f:\{1,2,\dots,r\} \to E\text{.}\) Par l’exemple 2, on sait qu’il y a \(\frac{n!}{(n-r)!}\) telles fonctions.
On regarde maintenant deux problèmes typiques faisant intervenir des permutations.
Exemple 4.2.7. Des anagrammes.
Une anagramme d’une suite de lettres est une permutation de ces lettres. Lorsqu’on compte le nombre d’anagrammes possibles, on ne s’intéresse pas à savoir si la permutation est un vrai mot. Combien d’anagrammes des lettres \(ABCDEFGH\) sont telles que les lettres \(ABC\) doivent apparaître dans cet ordre en un seul bloc?Exemple 4.2.8. Le parcours d’un vendeur.
Un vendeur doit visiter huit villes différentes, l’une d’elles étant Saint-Rémi, pour son travail. Sachant qu’il doit terminer son voyage à Saint-Rémi, de combien de façons différentes peut-il visiter ces huit villes ?Sous-section 4.2.2 Les combinaisons
Tel que mentionné précédemment, il est à priori un peu plus complexe de choisir trois personnes parmi \(25\) que d’ordonner trois de ces \(25\) personnes.
Pour arriver à déterminer le nombre de choix possibles, on commence par définir le concept de combinaison. Par la suite, on utilise le lien qu’il existe entre les permutations et les combinaisons afin de déterminer le nombre de façons de choisir \(r\) objets parmi \(n\text{.}\)
Définition 4.2.9.
-
Soit \(E\) un ensemble de cardinalité finie \(|E|=n,\) une \(r-\)combinaison de \(E\) est une sélection non ordonnée de \(r\) éléments de \(E\text{.}\)
-
Le nombre de \(r\)-combinaisons d’un ensemble de cardinalité finie \(n\) est noté \(\Binomial{n}{r}\text{.}\)
-
Les expressions de la forme \(\Binomial{n}{r}\text{,}\) sont appelées les coefficients binomiaux.
Proposition 4.2.10.
Soit \(E\) un ensemble de cardinalité finie \(|E|=n,\) et soit \(r\in\, \N\) tel que \(r\leq n\text{,}\) alors \(\Binomial{n}{r}=\frac{n!}{r!(n-r)!}\text{.}\)Démonstration.
On sait que le nombre de \(r-\)permutations est \(\Permutation{n}{r}=\frac{n!}{(n-r)!}\text{.}\) Nous allons utiliser le principe du produit afin de compter \(\Permutation{n}{r}\) d’une autre façon. On peut séparer la tâche de choisir une permutation en deux étapes. Premièrement, on choisit \(r\) éléments de \(E\text{.}\) Deuxièmement, on choisit un ordre pour ces éléments (on permute ces \(r\) éléments).
Le nombre de façons de choisir les \(r\) éléments de \(E\) est \(\Binomial{n}{r}\text{.}\) Pour chaque choix de \(r\) éléments , le nombre de façons d’ordonner ceux-ci est \(r!\) (le nombre de permutations des \(r\) éléments). Ainsi, par le principe du produit, on a
\begin{equation*}
\Permutation{n}{r}=\Binomial{n}{r}\cdot r!\text{.}
\end{equation*}
On a alors
\begin{equation*}
\Binomial{n}{r}=\frac{\Permutation{n}{r}}{r!}=\frac{n!}{r!(n-r)!}\text{.}
\end{equation*}
On regarde maintenant deux exemples typiques faisant intervenir les combinaisons.
Exemple 4.2.11. Mains de poker.
Combien de mains de cinq cartes peuvent être formées à partir d’un jeu de cartes standard de \(52\) cartes?Solution.
Exemple 4.2.12. Des chaînes binaires.
Combien de chaînes binaires de longueur \(n\) contiennent exactement \(r\) caractères \(1\text{?}\)Solution.
Pour dénombrer ces chaînes, on remarque que pour choisir une telle chaîne binaire, il suffit de choisir \(r\) positions où l’on place les \(1\) parmi les \(n\) positions possibles. Il s’agit donc de compter les combinaisons de \(r\) parmi \(n\text{.}\) Il y en a \(\Binomial{n}{r}\text{.}\)
On peut également remarquer que, s’il y a exactement \(r\) caractères \(1\text{,}\) alors il y aura \(n-r\) caractères \(0\text{.}\) Ainsi, on aurait également pu choisir les \(n-r\) positions des \(0\text{.}\) Il y a donc \(\Binomial{n}{n-r}\) façons de le faire.
Ainsi, on devrait avoir que \(\Binomial{n}{r}=\Binomial{n}{n-r}\text{.}\)
Les coefficients binomiaux sont utilisés dans plusieurs branches des mathématiques. Voici quelques propriétés qu’on peut déduire facilement à l’aide de la définition et de la proposition 4.2.10.
Corollaire 4.2.13.
Soit \(n,\,r\in\,\N\) tels que \(r\leq n,\) alors \(\frac{n!}{r!(n-r)!}\) est un entier naturel.Démonstration.
Puisque la proposition 4.2.10 nous donne que \(\frac{n!}{r!(n-r)!}=\Binomial{n}{r}\text{,}\) et que \(\Binomial{n}{r}\) est un nombre de combinaisons, alors ce nombre est nécessairement un entier naturel.
Corollaire 4.2.14.
Soit \(n,\,r\in\,\N\) tels que \(r\leq n,\) alors \(\Binomial{n}{r}=\Binomial{n}{n-r}\text{.}\)Remarque 4.2.15.
Un corollaire est une proposition qui découle directement d’une autre proposition.
Sous-section 4.2.3 Le triangle de Pascal et le binôme de Newton
Les combinaisons apparaissent à plusieurs moments dans l’histoire des mathématiques. Le triangle de Pascal est un exemple où l’on peut représenter visuellement les termes \(\Binomial{n}{r}\) afin de les calculer rapidement.
Un autre exemple est lorsqu’on veut développer l’expression \((x+y)^n\text{.}\) On explore ici ces deux situations.
Sous sous-section 4.2.3.1 Le triangle de Pascal
Définition 4.2.16.
Le triangle de Pascal est une représentation des coefficients \(\Binomial{n}{r}\) dans un tableau triangulaire. On représente ici les six premières lignes.
\begin{equation*}
\begin{matrix}
\amp \amp \amp \amp \amp 1 \amp \amp \amp \amp \amp \\
\amp \amp \amp \amp 1 \amp \amp 1 \amp \amp \amp \amp \\
\amp \amp \amp 1 \amp \amp 2 \amp \amp 1 \amp \amp \amp \\
\amp \amp 1\amp \amp 3 \amp \amp 3 \amp \amp 1 \amp \amp \\
\amp 1 \amp \amp 4 \amp \amp 6 \amp \amp 4 \amp \amp 1 \amp \\
1 \amp \amp 5 \amp \amp 10 \amp \amp 10 \amp \amp 5 \amp \amp 1 \\
\end{matrix}
\end{equation*}
Le premier et le dernier nombre de chaque ligne sont des \(1\text{.}\) Les autres nombres sont obtenus successivement (ligne par ligne) en additionnant les deux nombres se trouvant au-dessus.
En termes des coefficients \(\Binomial{n}{r}\text{,}\) le triangle nous donne
\begin{equation*}
\begin{matrix}
\amp \amp \amp \amp \amp \Binomial{0}{0} \amp \amp \amp \amp \amp \\
\amp \amp \amp \amp \Binomial{1}{0} \amp \amp \Binomial{1}{1} \amp \amp \amp \amp \\
\amp \amp \amp \Binomial{2}{0} \amp \amp \Binomial{2}{1} \amp \amp \Binomial{2}{2} \amp \amp \amp \\
\amp \amp \Binomial{3}{0}\amp \amp \Binomial{3}{1} \amp \amp \Binomial{3}{2} \amp \amp \Binomial{3}{3} \amp \amp \\
\amp \Binomial{4}{0} \amp \amp \Binomial{4}{1} \amp \amp \Binomial{4}{2} \amp \amp \Binomial{4}{3} \amp \amp \Binomial{4}{4} \amp \\
\Binomial{5}{0} \amp \amp \Binomial{5}{1} \amp \amp \Binomial{5}{2} \amp \amp \Binomial{5}{3} \amp \amp \Binomial{5}{4} \amp \amp \Binomial{5}{5} \\
\end{matrix}
\end{equation*}
En fait, la construction du triangle de Pascal laisse deviner qu’on peut déterminer les coefficients \(\Binomial{n}{r}\) à l’aide de sommes, plutôt qu’à l’aide de la définition. On peut en déduire la formule de Pascal, qu’on donne à la proposition 4.2.17.
Proposition 4.2.17.
Soit \(n,\ r\in \N\) tels que \(0 \lt r \leq n\text{,}\) alors
\begin{equation*}
\Binomial{n}{r}=\Binomial{n-1}{r-1} + \Binomial{n-1}{r}.
\end{equation*}
Démonstration.
On a
\begin{align*}
\Binomial{n-1}{r-1}+\Binomial{n-1}{r} \amp = \frac{(n-1)!}{(r-1)!((n-1)-(r-1))!}+\frac{(n-1)!}{(r)!((n-1)-r)!}\\
\amp = \frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{(r)!(n-r-1)!}\\
\amp = \frac{(n-1)!(r)}{(r)(r-1)!(n-r)!}+\frac{(n-1)!(n-r)}{(r)!(n-r-1)!(n-r)}\\
\amp = \frac{(n-1)!(r)}{(r)!(n-r)!}+\frac{(n-1)!(n-r)}{(r)!(n-r)!}\\
\amp = \frac{(n-1)!(r)+(n-1)!(n-r)}{(r)!(n-r)!}\\
\amp = \frac{(n-1)!(r+n-r)}{(r)!(n-r)!}\\
\amp = \frac{(n-1)!(n)}{(r)!(n-r)!}\\
\amp = \frac{(n)!}{(r)!(n-r)!}\\
\amp = \Binomial{n}{r}
\end{align*}
Sous sous-section 4.2.3.2 Le binôme de Newton
Après avoir calculé à de nombreuses reprises des expressions comme \((x+3)^2= x^2+6x +9\) ou encore \((2x+5)^2=4x^2+20x+25\text{,}\) on peut deviner que
\begin{equation*}
(x+y)^2=x^2+2xy+y^2.
\end{equation*}
On peut voir une certaine structure dans cette expression, et on peut se demander s’il est possible de généraliser cette formule.
Par exemple, avec un peu de travail, on obtient que
\begin{equation*}
(x+y)^3 =x^3 +3x^2y + 3 xy^2 + y^3\text{.}
\end{equation*}
En comparant les expressions de \((x+y)^2\) et de \((x+y)^3\) aux lignes du triangle de Pascal, on voit que les coefficients devant les termes \(x^ny^m\) sont ceux qu’on retrouve aux lignes appropriées du triangle de Pascal. Ce résultat est vrai en général, et est énoncé à la proposition ci-dessous.
Proposition 4.2.18.
Soit \(x,\ y \in \R\) et \(n,\ r\in \N\) tels que \(0\leq r\leq n\text{,}\) alors le coefficient devant le terme \(x^{n-r} y^{r}\) de l’expression \((x+y)^n\) est donné par \(\Binomial{n}{n-r}\text{.}\)
Démonstration.
Exemple 4.2.19. Les coefficients de \((x+y)^5\).
Solution.
On devra utiliser les coefficients \(\Binomial{n}{n-r}\text{,}\) pour \(r\) allant de \(0\) à \(5\text{.}\) On peut les calculer à partir de la définition, ou bien à partir du triangle de Pascal. On obtient:
\begin{align*}
\Binomial{5}{0}\amp= 1 \\
\Binomial{5}{1}\amp= 5 \\
\Binomial{5}{2}\amp= 10 \\
\Binomial{5}{3}\amp= 10 \\
\Binomial{5}{4}\amp= 5 \\
\Binomial{5}{5}\amp= 1
\end{align*}
Ainsi, par la proposition 4.2.18, on a que
\begin{align*}
(x+y)^5 \amp=1x^5y^0+5x^4y^1+10x^3y^2+10x^2y^3+5x^1y^4+1x^0y^5\\
\amp=x^5+5x^4y+10x^3y^2+10x^2y^3+5xy^4+y^5
\end{align*}
Sous-section 4.2.4 Les permutations et combinaisons généralisées
On veut maintenant généraliser les concepts de permutations et de combinaisons. Une première généralisation est de considérer les dénombrements d’objets indiscernables. Un exemple typique sera les anagrammes de mots avec des lettres qui se répètent.
Une deuxième façon de généraliser est de considérer des permutations et des combinaisons lorsqu’on peut répéter les éléments de l’ensemble que l’on choisit.
On a déjà fait plusieurs exemples qui sont des permutations avec répétition (voir entre autres 4.1.7, 4.1.15 et 4.1.17). Le dénombrement de ces situations se fait assez facilement grâce au principe du produit.
Cependant, le dénombrement de combinaisons avec répétition est un problème plus complexe. Il faudra développer une technique plus sophistiquée.
Sous sous-section 4.2.4.1 Permutations avec des objets indiscernables
On commence par considérer l’exemple le plus simple, c’est-à-dire lorsque les objets sont séparés en deux types d’objets indiscernables. En fait, on revisite l’exemple 4.2.12, mais on adopte une stratégie différente qu’on pourra utiliser plus tard. Cette méthode permet de généraliser la formule des permutations de \(k\) types d’objets indiscernables. On peut également généraliser la méthode utilisée à l’exemple 4.2.12, mais la notation est un peu plus lourde.
Exemple 4.2.20. Des chaînes binaires.
(a)
formées de quatre caractères \(1\) et trois caractères \(0\text{?}\)Solution 1.
Une première solution est d’étiqueter les \(1\) et les \(0\) par \(1_a,\) \(1_b,\) \(1_c\) et \(1_d\text{,}\) ainsi que \(0_a,\) \(0_b\) et \(0_c\text{.}\) Le nombre de permutations de ces nouveaux caractères est \((4+3)!=7!\text{.}\)
Cependant, lorsqu’on enlève l’étiquetage, on remarque que pour chaque permutation qu’on vient de dénombrer, il y en a plusieurs autres qui sont équivalentes. Par exemple, lorsqu’on a les étiquettes, la chaîne \(1_a1_b1_c1_d0_a0_b0_c\) est initialement considérée comme différente à la chaîne \(1_b1_c1_a1_d0_b0_a0_c\text{.}\) Cependant, lorsqu’on enlève les étiquettes, les deux chaînes donnent la même, soit \(1111000\text{.}\)
Pour chaque chaîne obtenue, on en a \(4!\cdot 3!\) qui sont équivalents. Le \(4!\) provient des permutations des quatre \(1,\) alors que le \(3!\) correspond aux permutations des \(0\text{.}\)
Par le principe de la division, on a que le nombre de chaînes binaires est
\begin{equation*}
\frac{7!}{4!\cdot 3!}=\Binomial{7}{4}\text{.}
\end{equation*}
Solution 2.
Une autre solution est de voir le problème comme étant une combinaison, comme on a fait à l’exemple 4.2.12 . En effet, on peut choisir une telle chaîne binaire en choisissant les positions des \(1\text{.}\) Puisqu’il y aura \(8\) positions au total et qu’on doit choisir la position pour les quatre caractères \(1\text{.}\) Ainsi, il s’agit d’une combinaison de \(4\) objets parmi \(8\text{.}\)
(b)
formées de \(n\) caractères dont \(r\) de ces caractères sont des \(1\text{?}\)Solution 1.
On commence par compter le nombre de permutations de tous les objets en supposant qu’ils sont tous différents. Il y a alors \(n!\) permutations.
Cependant, pour chacune de ces permutations, il y a en \(n_1!\cdot n_2!\) qui sont équivalentes.
Le \(n_1!\) provient des permutations des objets de type \(1,\) alors que le \(n_2!\) correspond aux permutations des objets de type \(2\text{.}\)
Solution 2.
On veut maintenant considérer le cas où les objets sont séparés en \(k\) types d’objets indiscernables.
Proposition 4.2.21.
Le nombre de permutations différentes de \(n\) objets, où il y \(n_1\) objets indiscernables de type \(1\text{,}\) \(n_2\) objets indiscernables de type \(2\text{,}\) \(\dots,\) et \(n_k\) objets indiscernables de type \(k\) est
\begin{equation*}
\frac{n!}{n_1!n_2!\cdots n_k!}
\end{equation*}
Démonstration.
On commence par compter le nombre de permutations de tous les objets en supposant qu’ils sont tous différents. Il y a alors \(n!\) permutations.
Cependant, pour chacune de ces permutations, il y a en \(n_1!\cdot n_2!\cdots n_k!\) qui sont équivalentes.
Le \(n_1!\) provient des permutations des objets de type \(1,\) le \(n_2!\) correspond aux permutations des objets de type \(2\text{,}\) et ainsi de suite jusqu’aux \(n_k!\) permutations des objets de type \(k\text{.}\)
Par le principe de la division, on a que le nombre de permutations de nos objets est
\begin{equation*}
\frac{n!}{n_1!\cdot n_2!\cdots n_k!}\text{.}
\end{equation*}
Démonstration.
On commence par choisir les \(n_1\) positions parmi les \(n\) positions totales pour les objets de type \(1\text{.}\) Il y a \(\Binomial{n}{n_1}\) façons de le faire.
Par la suite, on choisit les \(n_2\) positions parmi les \(n-n_1\) positions restantes pour les objets de type \(2\text{.}\) Il y a \(\Binomial{n-n_1}{n_2}\) façons de le faire.
On doit maintenant choisir les \(n_3\) positions parmi les \(n-n_1-n_2\) positions restantes pour les objets de type \(3\text{.}\) Il y a \(\Binomial{n-n_1-n_2}{n_3}\) façons de le faire.
En poursuivant ainsi, jusqu’aux objets de type \(k\text{,}\) et en utilisant le principe du produit, on a que le nombre de permutations est
\begin{align*}
\amp = \Binomial{n}{n_1}\Binomial{n-n_1}{n_2}\cdots \Binomial{n-n_1-n_2-\cdots-n_{k-1}}{n_{k}}\\
\amp = \frac{n!}{(n-n_1)!n_1!}\frac{(n-n_1)!}{(n-n_1-n_2)!n_2!}\cdots \frac{(n-n_1-n_2-\cdots-n_{k-1})!}{0!n_{k}!}\\
\amp = \frac{n!}{n_1!n_2!\cdots n_k!}
\end{align*}
Sous sous-section 4.2.4.2 Permutations avec répétitions
Proposition 4.2.22.
Le nombre de \(r-\)permutations d’un ensemble \(E\) de \(n\) objets si on accepte les répétitions est \(n^r\text{.}\)
Démonstration.
Choisir une telle \(r-\)permutation est équivalent à choisir une fonction \(f: \{1,\dots,r\}\to E\text{.}\) Par l’exemple 4.1.7, on a que le nombre de \(r-\)permutations de \(n\) objets avec répétition est \(n^r\text{.}\)
Sous sous-section 4.2.4.3 Combinaisons avec répétitions
On considère l’exemple suivant. Un magasin de bagels vend quatre sortes de bagels différents: nature, sésame, pavot et bleuet. En supposant que le magasin possède plus de \(8\) bagels de chaque sorte, de combien de façons peut-on choisir \(8\) bagels. Ceci est un exemple de combinaisons avec répétition. Ici, on pourrait par exemple choisir
\begin{align*}
2 \amp \text{ bagels natures;} \amp \text{ ou bien } \amp\amp2\amp\text{ bagels natures;}\\
4 \amp \text{ bagels au sésame;} \amp \amp\amp1 \amp\text{ bagels au sésame;}\\
1 \amp \text{ bagels au pavot;} \amp \amp\amp 3\amp\text{ bagels au pavot;}\\
1 \amp \text{ bagels au bleuet;} \amp \amp\amp 2 \amp\text{ bagels au bleuet;}
\end{align*}
Remarque 4.2.23.
On pourrait aussi s’imaginer qu’on tire \(8\) billes de couleur rouge, bleu, vert ou jaune d’une urne contenant au moins \(8\) billes de chaque couleur.
Une façon de représenter l’exemple précédent de façon un peu plus algébrique est la suivante. On considère \(x_i\in\,\N\) pour \(i=1,2,3,4\text{.}\) De combien de façons peut-on choisir les \(x_i\) pour que \(x_1+x_2+x_3+x_4=8\text{?}\)
Pour pouvoir compter le nombre de solutions, on fait la transformation suivante. Pour chaque solution \(x_1+x_2+x_3+x_4=8\text{,}\) on considère la chaîne binaire formée comme ceci: on échange chaque \(x_1\) par une séquence de \(1\) de longueur \(x_i\text{,}\) et on ajoute un unique \(0\) entre chaque séquence de \(1\) (ça revient à échanger chaque \(+\) en un \(0\)).
Par exemple, la solution \(2+4+1+1=8\) sera transformée en la chaîne
\begin{equation*}
11011110101\text{.}
\end{equation*}
Ainsi, on vient de trouver une bijection entre les solutions à l’équation \(x_1+x_2+x_3+x_4=8\) et les chaînes binaires de longueur \(8+3=11\) formées de huit caractères \(1\) et de trois caractères \(0\text{.}\)
On sait qu’il existe \(\Binomial{11}{8}\) telles chaînes. On peut généraliser cet argument pour trouver le nombre de \(r-\)combinaisons avec répétition.
Proposition 4.2.24.
Soit \(x_i\in\, \N\) pour \(i=1,2,\dots,r\text{,}\) le nombre de solutions à l’équation
\begin{equation*}
x_1+x_2+\cdots + x_r = n
\end{equation*}
est \(\Binomial{n+r-1}{n}=\Binomial{n+r-1}{r-1}\text{.}\)
Démonstration.
On peut définir une bijection entre ces solutions et les chaînes binaires de longueur \(n+ (r-1)\) formées de \(n\) caractères \(1\) et \(r-1\) caractères \(0\) en utilisant la méthode précédente. Ainsi, le nombre de solutions est bien \(\Binomial{n+r-1}{r}\text{.}\)
Pour ce genre de problèmes, il arrive souvent qu’on ajoute certaines conditions. L’exemple ci-dessous montre comment traiter ces conditions.
Exemple 4.2.25. Combinaisons avec répétition.
Déterminer le nombre de solutions à l’équation \(x_1+x_2+x_3+x_4+x_5+x_6=13\text{,}\) pour \(x_i\in\,\N\) et \(i=1,2,3,4,5,6\text{,}\) si :
(a)
il n’y a pas d’autre condition?
(b)
Réponse.
\(\Binomial{12}{7}=\frac{12!}{7!5!}\)
Solution.
Pour s’assurer que \(x_i\geq 1\text{,}\) on introduit des variables intermédiaires \(y_i\geq 0\) telles que \(x_i=y_i+1\text{.}\) Ainsi, en remplaçant dans l’équation, on a \((y_1+1)+(y_2+1)+(y_3+1)+(y_4+1)+(y_5+1)+(y_6+1)=13\text{,}\) ce qui devient \(y_1+y_2+y_3+y_4+y_5+y_6=7\text{.}\)
Ainsi, il y aura \(\Binomial{12}{7}=\frac{12!}{7!5!}\) solutions.
(c)
\(x_3\geq 2\)
Réponse.
\(\Binomial{16}{11}=\frac{16!}{11!5!}\)
Solution.
Pour s’assurer que \(x_3\geq 2\text{,}\) on introduit la variable intermédiaire \(y_3\geq 0\) telle que \(x_3=y_3+2\text{.}\) Ainsi, en remplaçant dans l’équation, on a \(x_1+x_2+(y_3+2)+x_4+x_5+x_6=13\text{,}\) ce qui devient \(x_1+x_2+y_3+x_4+x_5+x_6=11\text{.}\)
Ainsi, il y aura \(\Binomial{16}{11}=\frac{16!}{11!5!}\) solutions.
(d)
\(x_3\lt 3\)
Réponse.
\(\Binomial{12}{7}=\frac{12!}{7!5!}\)
Solution.
On compte toutes les solutions à l’équation (sans restriction) et on retire les solutions qui ne respectent pas la condition, c’est-à-dire les solutions telles que \(x_3\geq 3\text{.}\) Pour s’assurer que \(x_3\geq 3\text{,}\) on introduit la variable intermédiaire \(y_3\geq 0\) telle que \(x_3=y_3+3\text{.}\) Ainsi, en remplaçant dans l’équation \(x_1+x_2+(y_3+3)+x_4+x_5+x_6=13\text{,}\) on obtient \(x_1+x_2+y_3+x_4+x_5+x_6=10\text{.}\)
Ainsi, il y aura \(\Binomial{18}{5}-\Binomial{15}{5}=\frac{18!}{13!5!}-\frac{15!}{10!5!}\) solutions.
Les points importants de cette section sont:
-
Les permutations;
-
Les combinaisons;
Questions de compréhension de la lecture 4.2.5 Questions de compréhension de la lecture
Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
1.
Sans utiliser une calculatrice (ou un autre outil informatique), expliquer comment calculer \(\frac{100!}{98!}\text{.}\)
2.
On considère l’ensemble \(A=\{a,b,c,d,e,f,g\}\)
(a)
Combien de permutations de l’ensemble \(A\) y a-t-il?
(b)
(c)
Combien de sous-ensembles de \(A\) possèdent quatre éléments?
(d)
Combien de sous-ensembles de \(A\) possèdent trois éléments?
(e)
3.
Combien de mots peut-on former avec les lettres du mot \(ANAGRAMME\text{?}\)
4.
On forme des chaînes binaires de longueur \(8\text{,}\) formés de quatre caractères "\(0\)" et quatre caractères "\(1\)". Combien de ces chaînes binaires y a-t-il?
5.
Soit \(x_i\in\, \N\) pour \(i=1,2,3,4\text{,}\) trouver le nombre de solutions à l’équation
\begin{equation*}
x_1+x_2+x_3+x_4 = 25.
\end{equation*}
6.
7.
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Exercices 4.2.6 Exercices
À faire en classe
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
1.
On forme des chaînes binaires de longueur dix, formés de cinq caractères "\(0\)" et cinq caractères "\(1\)".
(a)
Combiens de ces chaînes binaires y a-t-il?
(b)
Combiens de ces chaînes binaires contiennent cinq "\(1\)" consécutifs?
(c)
2.
On forme des chaînes binaires de longueur \(8\text{,}\) formés de cinq caractères "\(1\)" et trois caractères "\(0\)".
(a)
Combiens de ces chaînes binaires y a-t-il?
(b)
Combiens de ces chaînes binaires contiennent cinq "\(1\)" consécutifs?
(c)
Combiens de ces chaînes binaires contiennent trois "\(0\)" consécutifs?
(d)
3.
On lance une pièce à deux faces à \(8\) reprises. Le résultat est Pile ou Face. Combien de résultats:
(a)
y a-t-il au total?Réponse.
\(2^8\text{.}\)
(b)
contiennent exactement deux Face?(c)
contiennent exactement trois Pile?Réponse.
\(\Binomial{8}{3}=\frac{8!}{3!5!}\)
(d)
contiennent le même nombre de Pile que de Face?Réponse.
\(\Binomial{8}{4}=\frac{8!}{4!4!}\)
4.
De combien de manières peut-on sélectionner \(5\) volontaires dans la classe? (On suppose qu’il y a \(n\) personnes dans la classe.)
5.
Aux olympiades scolaires de l’école du Bonheur, tous les participants gagnent une médaille. S’il y a \(24\) élèves et qu’on attribue \(5\) médailles d’or, \(7\) médailles d’argent et le reste en bronze, de combien de manières est-ce que la distribution peut être faite?
6.
Pour une fin de semaine au chalet, on veut apporter \(5\) jeux de société. Dans la collection, on trouve \(5\) jeux coopératifs et \(8\) jeux de stratégies. Combien de possibilités y a-t-il si:
(a)
On ne donne aucune restriction?
Réponse.
\(\Binomial{13}{5}=\frac{13!}{8!5!}\)
(b)
On souhaite avoir exactement deux jeux coopératifs?
Réponse.
\(\frac{8!}{3!2!3!}\)
Solution.
et ensuite
\begin{equation*}
\Binomial{5}{2}\Binomial{8}{3}=\frac{5!}{3!2!}\frac{8!}{5!3!}=\frac{8!}{3!2!3!}\text{.}
\end{equation*}
(c)
Pour des raisons évidentes, on décide d’exclure des jeux coopératifs le jeu “Pandémie” et si on veut absolument apporter le jeu de stratégie “Smallworld”?
Réponse.
\(\Binomial{11}{4}=\frac{11!}{4!7!}\)
7.
Pour mon anniversaire, je souhaite faire un petit événement avec \(10\) invités. J’ai \(8\) bons amis hommes et \(6\) bonnes amies femmes que je considère inviter. Combien de choix est-ce que j’ai si:
(a)
Je ne mets aucune restriction?
(b)
(c)
Roxanne et Samuel forment un couple. Si je décide d’en inviter un des deux, l’autre doit venir aussi.
(i)
Combien de possibilités s’il n’y a pas d’autres restrictions?
Solution.
On commence par décider si le couple est invité ou non. On obtient leur présence ou absence entraine deux sous-ensembles disjoints de possibilités. Si le couple fait partie des invités, alors il reste \(8\) places à combler, à choisir parmi les \(12\) autres personnes. Cela fait \(\frac{12!}{8!4!}\text{.}\)
À cela, on ajoute les possibilités où Roxanne et Samuel ne sont pas invités. Il faut alors choisir les \(10\) invités parmi les \(12\) personnes. Cela fait \(\frac{12!}{10!2!}\text{.}\)
Par le principe d’addition, on a un total de \(\Binomial{12}{8}+\Binomial{12}{10}=\frac{12!}{8!4!}+\frac{12!}{10!2!}\) possibilités.
(ii)
Parmi celles-ci, combien comprennent le couple?(iii)
Solution.
Encore une fois, on sépare en deux cas distincts, selon si Roxanne et Samuel sont présents ou non. Dans le cas où ils sont présents, on doit ensuite choisir \(4\) hommes parmi les \(7\) restants et \(4\) femmes parmi les \(5\) restants. Selon le principe de multiplication, ceci donnera \(\Binomial{7}{4}\cdot \Binomial{5}{4}=\frac{7!}{4!3!}\times\frac{5!}{4!1!}\text{.}\)
À cela, on doit ajouter les possibilités où Roxanne et Samuel sont absents. Il faut choisir \(5\) hommes parmi les \(7\) qui ne sont pas Samuel et \(5\) femmes parmi les \(5\) qui ne sont pas Roxanne. On obtient alors, par le principe de multiplication \(\Binomial{7}{5}\cdot \Binomial{5}{5} = \frac{7!}{5!2!}\times \frac{5!}{5!0!}\text{.}\)
On combine finalement avec le principe d’addition pour avoir un total de \(\frac{7!}{4!3!}\times\frac{5!}{4!1!}+\frac{7!}{5!2!}\times \frac{5!}{5!0!}\) possibilités.
(iv)
Parmi celles-ci, combien comprennent le couple?(d)
Parmi mes amis, il y a aussi Christian et Sophie, qui sont en chicane et ne peuvent pas être tous les deux présents.
(i)
Combien de possibilités y a-t-il s’il n’y a pas d’autres restrictions?
Solution.
Cette-fois, on distingue trois cas: Christian est présent, mais pas Sophie, Sophie est présent, mais pas Christian ou ni Sophie ni Christian ne sont présents. Ces trois cas sont distincts et le principe d’addition permettra d’obtenir l’ensemble des possibilités.
Si Christian est présent, il faut ensuite choisir les \(9\) autres invités parmi les \(12\) personnes qui ne sont pas Sophie (ou Christian). Cela donne \(\Binomial{12}{9}=\frac{12!}{9!3!}\text{.}\) Le même argument montre que si Sophie est présente, mais pas Christian, le nombre de possibilités est aussi \(\Binomial{12}{9}=\frac{12!}{9!3!}\text{.}\)
Finalement, si les deux sont absents, il faut choisir les \(10\) invités parmi les \(12\) autres possibilités. On obtient alors \(\Binomial{12}{10}=\frac{12!}{10!2!}\text{.}\)
En combinant le tout, il y a \(2\times \frac{12!}{9!3!}+\frac{12!}{10!2!}\) possibilités.
(ii)
8.
(a)
Réponse.
(b)
Combien y a-t-il de fonctions \(h:A\to B\) qui sont surjectives?
Réponse.
Solution.
Pour que la fonction \(h\) soit surjective, on doit avoir \(|f^{-1}(b)|\geq 1\) pour \(b\in\, B\text{,}\) et on doit aussi avoir \(|f^{-1}(1)|+|f^{-1}(2)|+|f^{-1}(3)|+|f^{-1}(4)|=5\text{.}\) Ainsi, il doit y avoir avoir exactement un élément \(b\in\,B\) tel que \(|f^{-1}(b)|=2\) alors que tous les autres éléments auront une seule préimage.
Donc, pour définir une fonction surjective \(h:B\to A\text{,}\) on doit choisir l’élément \(b\) de \(B\) ayant deux préimages (\(4\) possibilités). Ensuite, on choisit les deux préimages de \(b\) (il y \(\Binomial{5}{2}\) possibilités.) Finalement, on doit choisir la préimage des autres éléments de \(B\text{.}\) Ceci revient à permuter trois éléments (il y a \(3!\) possibilités).
Ainsi, par le principe du produit, il y en a
\begin{equation*}
4\cdot \Binomial{5}{2}\cdot 3!=4\cdot \frac{5!}{3!2!}\cdot 3!=2\cdot 5!
\end{equation*}
(c)
Combien y a-t-il de fonctions \(k:B\to A\) qui sont injectives?
Réponse.
\(\Permutation{5}{4}=\frac{5!}{(5-4)!}=5!\)
9.
Soit \(x+y+z+w=24\text{.}\) Combien de solutions y a-t-il si
(a)
Réponse.
\(\Binomial{27}{3}=\frac{27!}{3!24!}\)
(b)
Réponse.
\(\Binomial{27-4}{3}=\Binomial{23}{3}=\frac{23!}{3!20!}\)
10.
Soit \(A\) un ensemble à \(n\) éléments. Une \(k\)-partition de \(A\) est un ensemble de \(k\) sous-ensembles de \(A\) qui ont les propriétés suivantes:
-
ils sont non vides, c’est à dire \(A_i\neq \emptyset\text{;}\)
-
leur intersection deux à deux sont vide, c’est-à-dire \(A_i\cap A_j=\emptyset\) si \(i\neq j\text{;}\)
Par exemple, pour \(A=\{1,2,3,4\}\text{,}\) les ensembles \(A_1=\{1,3\},A_2=\{2\}\) et \(A_{3}=\{4\}\) forment une \(3\)-partition de \(A\text{.}\) Combien y a-t-il de \(3\)-partition de \(A\text{?}\)
11.
Une boite de beignes d’une chaine populaire contient six compartiments qu’un employé remplit pour un client selon les règles suivantes. On cherche à calculer de combien de manières différentes une boite de beignes peut être constituée.
(a)
Il y a trois sortes de beignes, par exemple Chocolat, Érable et Vanille et on remplit la boite. Par exemple VVECCV est une configuration.
(b)
Même chose, mais on permet de laisser un compartiment vide (et le client sera potentiellement déçu). Par exemple, VVE_C_ est une configuration où _ représente l’absence d’un beigne.
(c)
On remplit tous les compartiments, en s’assurant que chaque sorte de beignes soit présente dans la boite.
Indice.
Solution.
On veut minimalement un beigne vanille, un chocolat et un érable. On distingue trois cas: \(VCESSS\) où \(S\) est une saveur répétée trois fois. On retrouve \(VCEVVV, VCECCC\) et \(VCEEEE\text{.}\) On peut aussi avoir, après avoir placé \(VCE\text{,}\) une saveur répétée deux fois et une autre saveur : \(VCEVVC, VCEVVE, VCEEEV, VCEEEC, VCECCV \text{ et } VCECCE\) Finalement, on peut avoir \(VCEVCE\text{.}\) Pour chacun de ces cas, on doit permuter. On aura
\begin{equation*}
\frac{6!}{4!} *3 + \frac{6!}{4! 2!} *6 + \frac{6!}{2! 2! 2!}= 540\text{.}
\end{equation*}
(d)
On remplit tous les compartiments, mais il y a maintenant \(12\) sortes de beignes!
(e)
L’employé, un peu maladroit remplit la boite avec six beignes à la vanille, mais en met potentiellement plus d’un par compartiment. Par exemple VV,V,_,VV,_,V est une configuration possible.
Solution.
(f)
Même chose que la partie 4.2.6.11.e, mais on utilise six beignes différents.
(g)
C’est presque l’heure de la fermeture et il ne reste que \(12\) beignes dans le présentoir, tous de différentes sortes. On veut remplir la boite de \(6\text{.}\)
(h)
On ne met que des beignes au chocolat, en laissant possiblement des compartiments vides.
(i)
C’est le printemps, le sirop d’érable coule en flot. Obtenez dix beignes à l’érable dans une boite de six! (Aucun compartiment ne sera laissé vide). Par exemple, EE,E,EEE,E,EE,E représenterait une configuration où deux beignes sont placés dans les compartiments 1 et 5, trois beignes sont placés dans le compartiment 3 et un beigne est placé dans chacun des compartiments 2,4 et 6.
(j)
Il n’y a plus de boite, alors on met les beignes dans des sacs identiques. On veut mettre six beignes à la vanille dans trois sacs (évidemment, aucun sac ne sera vide, pour éviter le gaspillage).
(k)
Même chose que précédemment, mais avec six beignes différents.
