Sauter au contenu

Mathématiques discrètes Version préliminaire

Section 4.1 Méthodes de dénombrement: Principes de base

Dans ce chapitre, nous allons étudier les différentes méthodes permettant de compter des objets ayant certaines propriétés. Les techniques de dénombrement sont basées sur des principes relativement simples, mais peuvent demander beaucoup d’ingéniosité afin de dénombrer les bons objets, ne pas en oublier et les compter une seule fois!
🔗
Lorsqu’on veut dénombrer certains objets, il est souvent utile de penser au problème comme si l’on voulait accomplir la tâche et de compter le nombre de façons différentes d’accomplir cette tâche. En particulier, on va souvent décrire les problèmes de dénombrement en termes du nombre de façons de choisir certains objets.
🔗
Dans cette section, nous étudierons les principes du produit et de la somme et leur variante.
🔗

Sous-section 4.1.1 Principe du produit

Lorsqu’on veut compter le nombre de façons différentes d’accomplir une tâche, il est souvent plus efficace de séparer la tâche en différentes étapes plus simples. On doit alors compter le nombre de façons d’accomplir chacune des étapes, et ensuite multiplier ces nombres pour obtenir le résultat. C’est ce qu’on appelle le principe du produit. On considère un exemple de base avant d’énoncer le principe en général.
🔗

Exemple 4.1.1. Le nombre de costumes.

Supposons qu’un de vos amis doit choisir un costume pour animer un spectacle. Si votre ami doit choisir parmi 3 chapeaux, 6 chandails et 4 pantalons. De combien de façons différentes peut-il s’habiller?
🔗
Solution.
On sépare la tâche de choisir le costume en trois étapes: choisir le chapeau, choisir le chandail et finalement choisir les pantalons. Il y a 3 façons d’exécuter la première tâche, 6 façons d’exécuter la deuxième tâche et 4 façons d’exécuter la troisième. Ainsi, au total, il y a \(3\cdot 6\cdot 4 =72\) façons de choisir un costume différent.
🔗
🔗
🔗

Remarque 4.1.2. L’indépendance des choix.

À l’exemple 4.1.1, l’ordre dans lequel on exécute chacune des tâches n’a pas d’importance. Le nombre de choix pour une tâche n’est pas affecté par le choix de l’autre tâche. Si votre ami choisit son chapeau en premier, ou bien il peut choisir son chandail en premier, et le nombre de costumes ne change pas. Ainsi, lorsqu’on veut dénombrer les costumes, on peut décider d’un ordre arbitraire (par exemple, chapeau, chandail, pantalons).
🔗
🔗
Le principe utilisé à l’exemple précédent est ce qu’on appelle le principe du produit. On le nomme parfois aussi le principe du ET, car on doit faire un premier choix, ET ensuite faire un deuxième choix. En langage plus formel, le principe du produit peut s’énoncer de deux façons.
🔗

Exemple 4.1.4. Exemples de base du principe du produit.

On veut compter le nombre de façons d’accomplir chacune des tâches suivantes.
  1. Une compagnie formée de seulement deux employés, Damien et Laura, loue un étage d’un immeuble de bureaux. Si cet étage possède 15 bureaux, de combien de manières peut-on assigner un bureau à chaque employé?
    🔗
    🔗
  2. Les chaises d’un auditorium sont étiquetées à l’aide d’une lettre un d’un nombre entier de 1 à 100. Combien de chaises peut-on étiqueter de cette façon.
    🔗
    🔗
  3. Combien de plaques d’immatriculation peut-on obtenir, si une plaque est formée de 3 lettres suivies de trois chiffres si l’on accepte toutes les séquences possibles?
    🔗
    🔗
🔗
Réponse.
\(210 \) manières.
🔗
\(2600\) chaises.
🔗
\(17576000\) plaques d’immatriculation
🔗
🔗
🔗
Solution.
  1. Pour assigner un bureau à chaque employé, on commence à assigner un bureau à Laura, puis on assigne un bureau à Damien. Il y a 15 bureaux possibles pour Laura. Ensuite, il reste 14 bureaux possibles pour Damien. Ainsi, il y a \(15\cdot 14 = 210 \) façons d’assigner un bureau à chaque employé.
    🔗
    🔗
  2. Pour étiqueter une chaise, on doit d’abord choisir une lettre, et ensuite choisir un nombre entier de 1 à 100. Il y a 26 choix possibles pour la lettre, et 100 choix possibles pour l’entier. On peut donc étiqueter \(26\cdot 100 = 2600\) chaises.
    🔗
    🔗
  3. Pour chaque lettre, il y a 26 choix possibles. Pour chaque chiffre, il y a 10 choix possibles. Il y a donc \(26\cdot 26\cdot 26 \cdot 10\cdot 10\cdot 10 = 17576000\) possibilités.
    🔗
    🔗
🔗
🔗
🔗
À l’exercice 1.3.6.10.a, on a considéré le nombre de fonctions, de fonctions injectives et de fonctions surjectives allant de \(A=\{0,1\}\) vers \(B=\{a,b,c\}\text{.}\) Puisque ces ensembles sont assez petits, il a été possidble d’énumérer toutes ces fonctions directement. On veut maintenant utiliser le principe du produit pour compter le nombre de fonctions et le nombre de fonctions injectives allant de \(A\) vers \(B\text{.}\) Par la suite, on va généraliser à des ensembles quelconques.
🔗

Exemple 4.1.5. Retour sur le nombre de fonctions.

Soit \(A=\{0,1\}\) et \(B=\{a,b,c\}\text{.}\)
  1. Combien y a-t-il de fonctions \(f:A\to B\text{?}\)
    🔗
    🔗
  2. Combien y a-t-il de fonctions injectives \(f:A\to B\text{?}\)
    🔗
    🔗
🔗
Solution.
  1. On compte le nombre de façon qu’il y a de définir une telle fonction \(f\text{.}\) Pour se faire, on sépare la tâche en deux étapes: choisir la valeur de \(f(0)\) et ensuite choisir la valeur de \(f(1)\text{.}\)
    🔗
    Lorsqu’on choisit la valeur de \(f(0)\text{,}\) on a trois choix possibles: \(f(0)=a\text{,}\) \(f(0)=b\) ou bien \(f(0)=c\text{.}\)
    🔗
    Une fois qu’on a choisi \(f(0)\text{,}\) on doit choisir \(f(1)\text{.}\) Encore une fois, on a trois choix possibles: \(f(1)=a\text{,}\) \(f(1)=b\) ou bien \(f(1)=c\text{.}\)
    🔗
    Par le principe du produit, il y a alors \(3\cdot 3 =9\) façons différentes de choisir une fonction \(f:A\to B\text{.}\)
    🔗
    On remarque encore une fois que le fait de choisir \(f(0)\) avant \(f(1)\) n’a pas d’importance. Puisque cela n’a pas d’importance, on peut donc décider d’un ordre arbitraire.
    🔗
    🔗
    🔗
  2. Comme à la partie précédente, on compte le nombre de façons de définir une telle fonction \(f\text{.}\) Pour se faire, on sépare la tâche en deux étapes: choisir la valeur de \(f(0)\) et ensuite choisir la valeur de \(f(1)\text{.}\)
    🔗
    Lorsqu’on choisit la valeur de \(f(0)\text{,}\) on a trois choix possibles: \(f(0)=a\text{,}\) \(f(0)=b\) ou bien \(f(0)=c\text{.}\)
    🔗
    Une fois qu’on a choisi \(f(0)\text{,}\) on doit choisir \(f(1)\text{.}\) Attention! Ici, on veut une fonction injective! Supposons par exemple que \(f(0)=c\text{,}\) il ne reste alors que deux choix possibles: \(f(1)=a\) ou bien \(f(1)=b\text{.}\) La même chose est vraie si l’on avait choisi une autre valeur pour \(f(0)\text{,}\) il ne resterait que deux choix possibles pour \(f(1)\text{.}\)
    🔗
    Par le principe du produit, il y a alors \(3\cdot 2 =6\) façons différentes de choisir une fonction injective \(f:A\to B\text{.}\)
    🔗
    🔗
    🔗
🔗
🔗
🔗

Remarque 4.1.6. Et les fonctions surjectives, elles?

Le cas des fonctions surjectives est beaucoup plus complexe. On étudiera ce cas dans une prochaine section [provisional cross-reference: exe-nbrFonctionsSurj].
🔗
🔗
On veut maintenant généraliser l’exemple précédent à des ensembles finis quelconques.
🔗

Démonstration.

D’abord, on a que pour chaque élément \(a\in A\text{,}\) on doit choisir la valeur de \(f(a)\text{.}\) Ainsi, pour chaque \(a\in A\text{,}\)il y a \(n\) possibilités pour \(f(a)\text{.}\) Puisqu’on doit faire \(m\) choix et qu’il y a \(n\) possibilités, pour chacun de ces choix, par le principe du produit, il y aura \(n\cdot n\cdot \cdots \cdot n =n^m\) fonctions différentes.
🔗
Si on veut que les fonctions soient injectives, on suppose qu’on étiquette les éléments de \(A\) par \(a_1,a_2,\dots,a_m\text{.}\) On commence par choisir la valeur de \(f(a_1)\text{.}\) Il y a \(n\) choix possible. On note cette valeur \(b_1\text{,}\) c’est-à-dire que \(f(a_1)=b_1\text{.}\)
🔗
On veut maintenant choisir la valeur de \(f(a_2)\text{.}\) Puisque \(f\) est injective, \(f(a_2)\neq b_1\text{.}\) Il reste donc \(n-1\) choix pour \(f(a_2)\text{.}\) On veut poursuivre ce raisonnement de façon général pour tous les éléments de \(A\text{.}\)
🔗
Supposons qu’on ait choisi les valeurs de \(f(a_i)\) pour tous les \(k\) premières valeurs de \(i\text{,}\) c’est-à-dire pour \(1\leq i \leq k \lt m\text{,}\) et qu’on veut maintenant choisir la valeur de \(f(a_{k+1})\text{.}\) Puisque \(f\) est injective, on aura que \(f(a_{k+1})\neq f(a_i)\) pour \(1\leq i \leq k \lt m\text{.}\) Il reste donc \(n-k\) choix pour la valeur de \(f(a_{k+1})\text{.}\) On répète cette démarche jusqu’à ce qu’on ait défini \(f(a_m)\text{.}\)
🔗
On remarque d’ailleurs que si \(m\gt n\text{,}\) on ne peut pas trouver de fonction injective (car on ne pourra pas trouver de valeur pour tous les \(f(a_i)\)).
🔗
Ainsi, par le principe du produit, il y aura \((n)\cdot (n-1)\cdot \cdots \cdot( n-(m-1) )\) fonctions injectives différentes. En effet, lorsqu’on veut choisir la valeur de \(f(a_m)\text{,}\) il restera \(m-1\) choix possibles (attention aux indices!).
🔗
🔗
À la section 1.1, on a introduit, pour un ensemble \(A\text{,}\) l’ensemble \(\mathscr{P}(A)\) des puissances de \(A\) (voir 1.1.13). On avait remarqué que la cardinalité de \(\mathscr{P}(A)\) semblait être donnée par \(|\mathscr{P}(A)|= 2^{|A|}\text{.}\) On utilise le principe du produit sur un exemple avant de généraliser ce résultat à un ensemble de taille fini quelconque.
🔗

Exemple 4.1.8. Retour sur l’ensemble des puissances.

On considère l’ensemble \(A=\{a,b,c\}\text{.}\) On sait que \(|\mathscr{P}(A)|=2^3\text{,}\) car on a décrit \(\mathscr{P}(A)\) en extension à la section 1.1.
🔗
On veut utiliser le principe du produit pour arriver à la même conclusion. On pourra ensuite généraliser au cas où \(|A|=n\text{.}\)
🔗
Solution.
On veut dénombrer le nombre de sous-ensembles différents de \(A\text{.}\) Ceci revient à compter le nombre de façons différentes qu’on peut construire un tel sous-ensemble \(E \subseteq A\text{.}\)
🔗
Pour se faire, on sépare la tâche "construire \(E\)" en trois étapes. On commence par choisir si \(a \in E\text{.}\) Il y a deux choix possibles (oui ou non). On choisit ensuite si \(b\in E\text{.}\) Il y a deux choix possibles (oui ou non). Finalement, on choisit si \(c\in E\text{.}\) Encore une fois, il y a deux choix possibles.
🔗
Par le principe du produit, il y a \(2\cdot 2\cdot 2 = 2^3=8\) façons différentes de choisir un ensemble \(E\in \mathscr{P}(A)\text{,}\) et donc \(|\mathscr{P}(A)|=2^3\text{.}\)
🔗
🔗
🔗
En utilisant un argument similaire, on peut déterminer la taille de l’ensemble des puissances pour un ensemble fini de taille quelconque.
🔗

Démonstration.

Supposons qu’on ordonne les éléments de \(A\) d’une manière quelconque, c’est-à-dire qu’on les étiquette par \(a_1,\ a_2\,\ \dots, a_n\text{.}\)
🔗
On veut maintenant construire (choisir) un sous-ensemble \(E\) de \(A\text{.}\) Pour se faire, on regarde successivement chaque élément de \(A\text{.}\) Pour chaque élément \(a_i\text{,}\) il y a deux choix possibles. Soit \(a_i\in\ E\text{,}\) soit \(a_i\notin\ E\text{.}\) Par le principe du produit, il y a \(2\times 2\times \cdots\times 2 =2^n\) façons différentes de construire le sous-ensemble \(E\text{.}\) Ainsi, \(\left|\mathscr{P}(A)\right|=2^n\text{.}\)
🔗
🔗
À la section, 4.2, on étudiera plus en détail les permutations et les combinaisons. On introduit l’idée avec l’exemple ci-dessous, ainsi qu’avec l’exemple 4.1.22 un peu plus tard .
🔗

Exemple 4.1.10. Les permutations.

Combien de "mots" différents peut-on écrire en utilisant les lettres du "mot" \(ABCDE\text{?}\) Ici, "mot" veut simplement dire une suite de lettres, même si le "mot" n’est pas un vrai mot en français (ou n’importe quelle autre langue). On dit aussi qu’il s’agit des permutations des lettres de \(ABCDE\text{.}\)
🔗
Solution 1.
On utilise le principe du produit. On choisit la première lettre du mot, ensuite la deuxième, et ainsi de suite jusqu’à la dernière lettre.
🔗
Pour la première lettre, on a \(5\) choix possibles. Pour la deuxième lettre, il reste \(4\) choix possibles. Pour la troisième lettre, il reste \(3\) choix possibles. Pour la quatrième lettre, il reste \(2\) choix possibles. Finalement, il ne reste que \(1\) choix pour la dernière lettre.
🔗
Ainsi, il y a \(5\times 4\times 3\times 2\times 1 =120\) mots différents qu’on peut obtenir à partir des lettres de \(ABCDE\text{.}\)
🔗
Ce problème est un exemple de permutations. On verra, à la prochaine section, que le nombre de permutations de \(5\) objets est \(5!\text{,}\) où la notation \(k!\) y sera également définie.
🔗
🔗
Solution 2.
Une solution alternative est de remarquer que d’écrire un mot utilisant les lettres de \(ABCDE\) est équivalent à choisir une fonction injective \(f: \{1,2,3,4,5\}\to \{A,B,C,D,E\}\text{,}\) où \(f(i)\) est la lettre à la position \(i\) du mot. Par exemple, les mots \(ABCDE\) et \(EDCBA\) sont équivalents aux fonctions \(f_1\) et \(f_2\) définies par
\begin{align*} f_1(1)\amp=A \amp f_2(1)\amp=E \\ f_1(2)\amp=B \amp f_2(2)\amp=D \\ f_1(3)\amp=C \amp f_2(3)\amp=C \\ f_1(4)\amp=D \amp f_2(4)\amp=B \\ f_1(5)\amp=E \amp f_2(5)\amp=A \end{align*}
🔗
Ainsi, le nombre de mots différents formés à partir des lettres de \(ABCDE\) est aussi le nombre de fonctions injectives de \(\{1,2,3,4,5\}\) vers \(\{A,B,C,D,E\}\text{.}\) Par l’exemple 2, on sait qu’il y en a \(5\times 4\times 3\times 2\times 1 =120\text{.}\)
🔗
🔗
🔗
🔗

Sous-section 4.1.2 Principe de la somme

Il est parfois difficile d’utiliser le principe du produit directement pour dénombrer une situation. Cela se produit souvent lorsque le nombre de façons d’accomplir une tâche dépend d’une condition. On doit alors compter le nombre de façons d’accomplir la tâche pour chaque condition, et ensuite additionner ces résultats. On commence par considérer un exemple très simple, avant d’énoncer ce principe.
🔗

Exemple 4.1.11. Des lettres ou des chiffres.

Supposons que l’on doive créer un mot de passe composé de quatre caractères pour un site quelconque. Supposons qu’en plus tous les caractères doivent soit tous être une des \(26\) lettres de l’alphabet, ou bien ils doivent tous être un chiffre (de \(0\) à \(9\)). Combien de façons différentes y a-t-il de choisir un mot de passe?
🔗
Solution.
On sépare la tâche selon si on choisit d’utiliser des lettres ou des chiffres pour notre mot de passe.
🔗
Si l’on choisit d’utiliser des lettres pour le mot de passe, on aura \(26\) choix pour chacun des caractères, et donc \(26^4\) choix possibles pour le mot de passe.
🔗
Si par contre, on choisit d’utiliser des chiffres, alors on aura \(10\) choix pour chacun des caractères, et donc \(10^4\) choix possibles pour le mot de passe.
🔗
Au total, puisqu’on doit avoir des lettres ou des chiffres, il y aura \(26^4+10^4=466\ 976\) choix possibles.
🔗
🔗
🔗
Le principe utilisé à l’exemple précédent s’appelle le principe de la somme. On le nomme également le principe du OU, car on peut accomplir la tâche d’une première façon OU d’une deuxième façon. En langage plus formel, le principe de la somme peut s’énoncer de deux façons.
🔗
On montre ici comment utiliser le principe de la somme dans le cas le plus simple. Dans les faits, on devra souvent utiliser le principe à plusieurs reprises, ou bien le combiner au principe du produit.
🔗

Exemple 4.1.13. Exemple de base du principe de la somme.

Supposons que le Cégep Gérald-Godin veut choisir, parmi les professeurs en mathématiques ou les professeurs en informatique, un représentant du programme de SIM pour siéger sur un comité exécutif. Sachant qu’il y a \(9\) professeurs en mathématiques et \(7\) professeurs en informatique combien de façons y a-t-il de choisir ce représentant, en supposant qu’un professeur ne peut pas être à la fois un professeur d’informatique et un professeur de mathématique?
🔗
Réponse.
\(16\)
🔗
🔗
Solution.
Il y a \(9\) façons de choisir un professeur de mathématiques, alors qu’il y a \(7\) façons de choisir un professeur d’informatique. Puisque le représentant est soit un professeur de mathématiques, soit un professeur d’informatique, il y a \(9+7=16\) façons différentes de choisir un tel représentant.
🔗
🔗
🔗
Évidemment, il est souvent utile de séparer une tâche en plus de deux choix. On peut alors utiliser le principe de la somme à plusieurs reprises, tel qu’illustré à l’exemple 4.1.14 .
🔗

Exemple 4.1.14. Utilisation successive du principe de la somme.

Un élève d’un cours d’informatique doit choisir pour l’évaluation finale, un projet parmi trois listes selon le langage de programmation utilisé. S’il y a \(15\) projets possibles en C, \(12\) projets possibles en python et \(7\) projets possibles en Pascal, combien de projets différents est-ce qu’un élève peut choisir?
🔗
Réponse.
\(34\)
🔗
🔗
Solution.
Lorsqu’un élève choisit son projet, il peut soit choisir de le faire en C, soit en python ou soit en Pascal. S’il choisit de le faire en C, il aura \(15\) choix possibles. S’il choisit de le faire en python, il en aura \(12\text{,}\) alors que s’il le fait en Pascal, il n’en aura que \(7\text{.}\) Si on utilise le principe de la somme à deux reprises, on a qu’il y a \(15+12+7=34\) façons de choisir un projet pour l’évaluation finale.
🔗
🔗
🔗
🔗

Sous-section 4.1.3 Combinaison du principe du produit et du principe de la somme

Tel que mentionné précédemment, il est souvent nécessaire de combiner le principe de la somme avec le principe du produit. Souvent, on commence par utiliser le principe de la somme pour séparer la tâche selon certaines conditions, et ensuite on utilise le principe du produit pour dénombrer le nombre de façons d’exécuter la tâche sous chacune des conditions. C’est ce qu’on a fait à l’exemple 4.1.11.
🔗

Exemple 4.1.15. Nombre de variables en BASIC.

Dans une version du langage informatique BASIC, le nom d’une variable doit être une chaîne de caractères formée d’un ou de deux caractères alphanumériques. Un caractère alphanumérique est soit une des \(26\) lettres de l’alphabet ou bien un chiffre de \(0\) à \(9\text{.}\)
🔗
De plus, le premier caractère doit toujours être une lettre, et il existe \(5\) noms de variables formées de deux caractères qui sont des variables protégées, c’est-à-dire qu’on ne peut pas donner ces noms à nos variables. Combien de noms de variables différents peut-on avoir dans cette version de BASIC?
🔗
Réponse.
\(957\)
🔗
🔗
Solution.
Soit \(V\) le nombre de noms de variables possible. Soit aussi \(V_1\) le nombre de ces noms formés d’un seul caractère, et soit \(V_2\) le nombre des noms formés de deux caractères. Ainsi, par le principe de la somme, on aura \(V=V_1+V_2\text{.}\)
🔗
Pour \(V_1\text{.}\) Puisque le premier caractère doit être une lettre, il y a seulement \(26\)possibilités, c’est-à-dire \(V_1=26\text{.}\)
🔗
Pour \(V_2\text{.}\) On doit choisir le premier caractère, qui doit être une lettre (donc \(26\) possibilités), et ensuite le deuxième caractère qui peut être soit une lettre soit un chiffre (par le principe de la somme, il y a \(26+10=36\) possibilités). Ainsi, par le principe du produit, il y a \(26\cdot 36=936\) possibilités. Cependant, on doit retirer les \(5\) possibilités représentant les noms réservés. On a donc \(V_2=936-5=931\text{.}\)
🔗
Finalement, on obtient \(V=V_1+V_2=26+931=957\text{.}\)
🔗
🔗
🔗
Bien que le principe de la somme et le principe du produit soient relativement simples en principe, il n’est pas toujours si simple de voir comment les utiliser pour répondre à un problème de dénombrement. Ceci peut rendre la résolution de problèmes de dénombrement particulièrement frustrante… Voici un exemple où il faut utiliser d’un peu plus d’intuition pour trouver la solution.
🔗

Exemple 4.1.16. Sous-ensembles de cardinalité paire.

Soit \(E\) un ensemble fini de cardinalité \(n\text{.}\) Combien de sous-ensembles de \(E\) ont une cardinalité paire si:
  1. \(n=4\text{;}\)
    🔗
    🔗
  2. \(n\) est un entier quelconque.
    🔗
    🔗
🔗
Solution.
  1. Supposons que \(E=\{e_1, e_2, e_3, e_4\}\text{.}\) Puisque l’ensemble est de cardinalité relativement petite, on peut essayer d’énumérer ces sous-ensembles de cardinalité paire. On obtient alors
    \begin{align*} E_1\amp=\{e_3, {\color{red}e_4}\} \amp E_2\amp=\{\} \\ E_3\amp= \{e_1, {\color{red}e_4}\}\amp E_4\amp=\{e_1,e_2\} \\ E_5\amp= \{e_2, {\color{red}e_4}\} \amp E_6\amp =\{e_1,e_3\} \\ E_7\amp= \{e_1, e_2, e_3, {\color{red}e_4}\} \amp E_8\amp = \{e_2,e_3\}. \end{align*}
    🔗
    Avant de considérer le cas général, on fait quelques remarques. Notons \(A=E-\{e_4\}=\{e_1, e_2, e_3\}\text{.}\) On peut voir que le nombre de sous-ensembles de cardinalité paire de \(E\) est équivalent au nombre de sous-ensembles de \(A\text{.}\) En effet, on peut voir un lien entre ceux-ci si on liste les sous-ensembles de \(A\text{.}\)
    \begin{align*} A_1\amp=\{e_3\} \amp A_2\amp=\{\} \\ A_3\amp= \{e_1\}\amp A_4\amp=\{e_1,e_2\} \\ A_5\amp= \{e_2\} \amp A_6\amp =\{e_1,e_3\} \\ A_7\amp= \{e_1, e_2, e_3\} \amp A_8\amp = \{e_2,e_3\}. \end{align*}
    🔗
    Si on compare les sous-ensembles \(E_i\) aux sous-ensembles \(A_i\text{,}\) on remarque que ceux ayant un indice pair sont égaux, c’est-à-dire que \(E_2=A_2\text{,}\) \(E_4=A_4\text{,}\) \(E_6=A_6\) et \(E_8=A_8\text{.}\) De même, chaque sous-ensemble \(E_i\) ayant un indice impair est obtenu à partir du sous-ensemble \(A_i\text{,}\) auquel on a ajouté l’élément \(\color{red}e_4\text{,}\) c’est-à-dire que \(E_1=A_1\cup \{{\color{red}e_4}\}\text{,}\) \(E_3=A_3\cup \{{\color{red}e_4}\}\text{,}\) \(E_5=A_5\cup \{{\color{red}e_4}\}\) et \(E_7=A_7\cup \{{\color{red}e_4}\}\text{.}\)
    🔗
    On utilisera cette remarque pour déterminer la solution dans le cas général.
    🔗
    🔗
  2. Supposons qu’on écrit \(E=\{e_1,\dots,e_n\}\) et posons \(A=E-\{e_n\}\text{.}\) Notons \(P\) le nombre de sous-ensembles de \(E\) de cardinalité pair. On choisit \(X\) un sous-ensemble de cardinalité paire de la façon suivante. Tout d’abord, on remarque que soit \(e_n\in\, X\text{,}\) ou bien \(e_n\notin\, X\text{.}\) Ainsi, par le principe de la somme, on a que \(P=P_1+P_2\text{,}\) où \(P_1\) est le nombre de sous-ensembles de cardinalité paire contenant \(e_n\text{,}\) et \(P_2\) le nombre de ces sous-ensembles qui ne contiennent pas \(e_n\text{.}\)
    🔗
    D’un côté, on remarque que \(e_n\notin\, X\) si et seulement si \(X\subseteq A\) et \(|X|\) est pair. Ainsi, \(P_1\) est le nombre de sous-ensembles de \(E-\{e_n\}\) de cardinalité paire.
    🔗
    De l’autre côté, on remarque aussi que \(e_n\in\, X\) si et seulement si \(X-\{e_n\}\subseteq A\) avec \(|X-\{e_n\}|\) impair. Ainsi, \(P_2\) est le nombre de sous-ensembles de \(E-\{e_n\}\) de cardinalité impair.
    🔗
    Par ce qui précède, on a que \(P=P_1+P_2\) est aussi le nombre de sous-ensembles de \(A\text{.}\) Or, on sait que ce nombre est \(|\mathscr{P}\left(A\right)|=2^{n-1}\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
Dans certains problèmes de dénombrement, il arrive qu’au moins une des tâches doive être accomplie d’une certaine façon, en ajoutant une restriction quelconque. Dans ce cas, il est souvent plus utile de compter toutes les façons possibles d’accomplir la tâche, et de lui soustraire les façons d’accomplir la tâche qui ne respectent pas la restriction. On utilise alors le principe de la somme "à l’envers". Ce genre d’argument est très utile lorsqu’on voit les mots "au moins un" dans l’exercice.
🔗

Exemple 4.1.17. Nombre de mots de passe.

Un site internet vous demande de choisir un mot de passe lors de la création de votre compte. Ce mot de passe doit être formé de \(6,\ 7\text{ ou }8\) caractères alphanumériques. De plus, chaque mot de passe doit contenir au moins un chiffre. Combien de mots de passe possible y a-t-il?
🔗
Réponse.
\(2\ 684\ 483\ 063\ 360\)
🔗
🔗
Solution.
On note \(P\) le nombre de mots de passe total, et \(P_i\) le nombre de mots de passe à \(i\) caractères, pour \(i\in\ \{6,\ 7,\ 8\}\text{.}\) Par le principe de la somme, on a \(P=P_6+P_7+P_8\text{.}\)
🔗
Pour calculer \(P_6\text{,}\) on compte tous les mots de passe à \(6\) caractères. Par la suite, on lui soustrait le nombre de mots de passe à \(6\) caractères qui ne contiennent pas de chiffres. En effet, par le principe de la somme \(\text{Mots de passe à }6\text{ caractères }=\text{Mots de passe à }6\text{ caractères sans chiffre}+\text{Mots de passe à }6\text{ caractères avec chiffres}\text{,}\) et donc \(\text{Mots de passe à }6\text{ caractères avec chiffres}=\text{Mots de passe à }6\text{ caractères }-\text{Mots de passe à }6\text{ caractères sans chiffres}\text{.}\)
🔗
Par le principe du produit, il y a \(36^6\) chaînes de \(6\) caractères alphanumériques. De plus, \(26^6\) de ces chaînes ne contiennent que des lettres, c’est-à-dire ne contiennent pas de chiffres. Ainsi, par l’argument donné au paragraphe précédent, \(P_6=36^6-26^6=2\ 176\ 782\ 336-308\ 915\ 776=1\ 867\ 866\ 560\text{.}\) On utilise le même argument pour \(P_7\) et \(P_8\text{.}\)
🔗
Pour \(P_7\text{,}\) on obtient \(P_7=36^7-26^7= 70\ 332\ 353\ 920 - 78\ 364\ 164\ 096 = 8\ 031\ 810\ 176\)
🔗
Pour \(P_8\text{,}\) on obtient \(P_8=36^8-26^8= 2\ 821\ 109\ 907\ 456 - 208\ 827\ 064\ 576 =2\ 612\ 282\ 842\ 880\)
🔗
Ainsi, on a \(P = P_6+P_7+P_8=2\ 684\ 483\ 063\ 360\text{.}\)
🔗
🔗
🔗
🔗

Sous-section 4.1.4 Le principe d’inclusion-exclusion (ou de la soustraction )

Il arrive que, lorsqu’on sépare les façons d’effectuer une tâche en deux catégories, certaines des façons d’effectuer la tâche se retrouvent dans les deux catégories. Dans ce cas, on ne peut pas simplement utiliser le principe de la somme, car on compte les éléments qui se trouvent dans les deux catégories deux fois.
🔗

Exemple 4.1.18. Le nombre de costumes bleus ou vert!

Supposons qu’un de vos amis doit choisir un costume pour animer un spectacle. Si votre ami doit choisir parmi 5 chapeaux dont 3 sont bleus, 2 chandails et 6 pantalons, dont 4 sont verts. De combien de façons différentes peut-il s’habiller, s’il doit porter un chapeau bleau ou un pantalon vert?
🔗
Solution.
On note \(C\) le nombre de costumes avec chapeau bleu ou pantalon vert. Pour déterminer \(C\text{,}\) on sépare la tâche de choisir le costume en deux catégories: la première catégorie est celle formée des costumes avec un chapeau bleu, alors que la deuxième est celle formée des costumes avec un pantalon vert.
🔗
On note \(C_b\) le nombre de costumes avec chapeau bleu, et \(C_v\) le nombre de costumes avec un pantalon vert. Par le principe du produit, on a que \(C_b=3\times 2\times 6 =36\text{.}\) De même, on obtient \(C_v=5\times 2\times 4=40\)
🔗
Cependant, \(C\neq C_b+C_v\text{!}\) En effet, dans l’expression \(C_b+C_v\text{,}\) on a compté les costumes avec chapeau bleu et pantalon vert deux fois. Une fois dans \(C_b\text{,}\) et une fois dans \(C_v\text{.}\)
🔗
Ainsi, on note \(C_{bv}\) le nombre de costumes avec chapeau bleu et pantalon vert. On obtient \(C_{bv}=3\times 2\times 4=24 \text{.}\) On a alors \(C=C_b+C_v-C_{bv}=36+40-24=52\text{.}\)
🔗
🔗
🔗

Remarque 4.1.19.

On aurait pu résoudre l’exemple 4.1.18 en séparant le choix des costumes en trois catégories, les costumes avec chapeau bleu, mais pantalon non vert (il y en a \(3\times 2\times 2= 12\)), les costumes avec chapeau bleu et pantalon vert (il y en a \(24\) ), et finalement les costumes avec chapeau non bleu et pantalon vert (il y en a \(2\times 2\times 4=16\)).
🔗
De cette façon, on peut utiliser le principe de la somme directement et obtenir le nombre de costumes avec chapeau bleu ou pantalon vert, qui est \(12+24+16=52\text{.}\)
🔗
🔗
Le principe utilisé à l’exemple 4.1.18 est le principe d’inclusion-exclusion. Il s’agit du même principe que celui de la formule 1.2.4.7. On énonce le principe de deux façons différentes.
🔗

Démonstration.

🔗

Exemple 4.1.21. Exemple de base du principe d’inclusion-exclusion.

Une chaîne binaire est une chaîne de caractères où chaque caractère est soit un \(1\text{,}\) soit un \(0\text{.}\) Combien de chaînes binaires de longueur \(8\) qui commencent par un \(1\) ou finissent avec deux \(0\) ?
🔗
Réponse.
\(160\)
🔗
🔗
Solution.
Soit \(B\) le nombre de chaînes binaires voulues, et soit \(B_1\) le nombre de chaînes binaires de longueur \(8\) commençant par un \(1\) et \(B_{00}\) le nombre de chaînes binaires de longueur \(8\) se terminant avec deux \(0\text{.}\)
🔗
Si on utilise directement le principe de la somme (de façon erronée), on obtient
\begin{equation*} B=B_1+B_{00}. \end{equation*}
Cependant, on ne peut pas utiliser le principe de la somme, car il existe des chaînes binaires de longueur \(8\) qui commencent par un \(1\) ET se terminent par deux \(0\text{.}\) On note le nombre de ces chaînes \(B_{100}\text{.}\)
🔗
Ainsi, par le principe d’inclusion-exclusion, on a
\begin{equation*} B=B_1+B_{00}-B_{100}. \end{equation*}
🔗
Par le principe du produit, on a que \(B_1=2^7\text{.}\) En effet, chaque caractère, sauf le premier (qui est fixé à \(1\)), peut être un \(1\) ou un \(0\text{.}\) Il reste donc \(7\) choix à faire, avec \(2\) possibilités pour chaque choix.
🔗
De même, on peut voir que \(B_{00}= 2^6\text{,}\) car cette fois deux des caractères sont fixés.
🔗
Enfin, on peut également voir par le principe du produit que \(B_{100}=2^5\text{,}\) car trois des caractères sont fixés.
🔗
Finalement, on a
\begin{align*} B\amp=B_1+B_{00}-B_{100}=2^7+2^6-2^5\\ \amp=1000\ 0000_2+100\ 0000_2-10\ 0000_2\\ \amp=1010\ 0000_2=160 \end{align*}
🔗
🔗
🔗

Sous-section 4.1.5 Le principe de la division

Une technique de dénombrement intéressante pour obtenir certaines égalités de manière très efficace est de compter la même chose de deux façons différentes. On peut se servir de cette idée lorsqu’on utilise le principe du produit de deux façons différentes pour la même tâche. Ceci nous permettra de simplifier certains problèmes de dénombrement.
🔗
Par exemple, on considère deux problèmes similaires, mais pour lesquels celui qui semble plus complexe est simple à résoudre.
🔗
D’un côté, supposons qu’on doive choisir trois personnes dans un groupe de quatre, sans leur attribuer un rôle particulier. Ceci est équivalent à dénombrer les sous-ensembles \(X\subseteq A\text{,}\) avec \(|X|=3\) et \(|A|=4\text{.}\) Avec de petites cardinalités, on peut simplement énumérer les sous-ensembles \(X\text{.}\) Cependant, il est à priori difficile de dénombrer cette situation avec des cardinalités plus élevées.
🔗
D’un autre côté, supposons qu’on doive choisir un président, un vice-président et un trésorier parmi un groupe de quatre personnes. En utilisant le principe du produit, il est facile de compter le nombre de façons d’accomplir cette tâche.
🔗
On remarque qu’on peut séparer la tâche de choisir un président, un vice-président et un trésorier parmi quatre personnes en deux étapes. Tout d’abord on choisit les trois personnes parmi quatre, et ensuite on choisit leur rôle. Étonnamment, il est plus difficile de compter le nombre de façons de choisir trois personnes, que de choisir trois personnes avec un rôle.
🔗
L’exemple ci-dessous nous permettra de montrer comment utiliser le lien entre ces deux situations pour dénombrer le nombre de façons de choisir trois personnes parmi quatre sans rôle.
🔗

Exemple 4.1.22. Choisir trois personnes parmi quatre.

On doit choisir trois personnes parmi un groupe de quatre personnes afin de former un comité.
  1. De combien de façons peut-on choisir ces trois personnes, si on doit choisir un président, un vice-président et un trésorier?
    🔗
    🔗
  2. De combien de façons peut-on choisir ces trois personnes, si on ne leur attribue pas un rôle particulier?
    🔗
    🔗
🔗
Solution.
Pour la première partie, on doit choisir un président, et ensuite choisir un vice-président, et finalement choisir un trésorier. Par le principe du produit, il y a \(4\times 3\times 2 =24\) façons de former le comité.
🔗
Ensuite, on remarque qu’on peut séparer la tâche de sélection avec rôle en deux étapes.
🔗
Premièrement, on choisit trois personnes parmi quatre. On note \(C_3^4\) le nombre de façons d’accomplir cette étape. Ensuite, on choisit un rôle pour chacune des personnes. À l’aide du principe du produit, on sait qu’il y a \(3\times 2\times 1 =6\) façons d’accomplir cette étape.
🔗
Ainsi, on sait que \(24=C_3^4\times 6\text{.}\) On peut alors isoler \(C_3^4\) pour obtenir \(C_3^4=\frac{24}{6}=4\text{.}\)
🔗
🔗
🔗
Le principe utilisé à l’exemple précédent s’appelle le principe de la division. Il est basé sur le principe du produit, et on peut l’énoncer de trois façons différentes.
🔗

Exemple 4.1.24. Exemple de base du principe de la division.

Supposons qu’il faille placer quatre personnes, Damien, Jean-Michel, Alexandre et Valérie, autour d’une table ronde (à quatre chaises).
🔗
De combien de façons différentes peut-on accomplir cette tâche, si deux façons de s’assoir sont considérées les mêmes si chaque personne possède le même voisin à gauche et le même voisin à droite.
🔗
Réponse.
\(6\)
🔗
🔗
Solution.
On commence par assigner une première chaise à Valérie. Celle-ci choisit arbitrairement une chaise qu’on numérote par \(1\text{.}\) Ensuite, on numérote les autres chaises de \(2\) à \(4\) de façon systématique (disons en tournant dans le sens horaire). Il y aura \(4\) façons différentes de faire ceci, car le résultat dépend uniquement du choix de Valérie.
🔗
Par la suite, on assigne arbitrairement une personne à la chaise \(2\) (il y aura \(3\) façons de faire ce choix). On continue pour la chaise \(3\) (\(2\) façons) et finalement la chaise \(4\) ( \(1\) seule façon de faire).
🔗
Par le principe du produit, il y a \(4\cdot 3\cdot 2\cdot 1 = 4!=24\) façons d’accomplir cette tâche.
🔗
Cependant, on se rend compte que le choix de la première chaise n’a pas d’impacte sur l’arrangement final, car on distingue deux arrangements seulement si les voisins des gens sont différents. Par le principe de la division, on doit diviser par \(4\) le résultat précédent, et il y aura donc \(\frac{24}{4}=6\) façons différentes d’assoir les gens.
🔗
🔗
🔗
🔗

Sous-section 4.1.6 Le principe d’étiquetage

On peut remarquer que plusieurs des exemples 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 \) ou même \(6\times 5 \times \cdots \times 2\times 1\text{.}\) Il convient maintenant de se définir une notation qui permet d’écrire plus succintement de tels calculs.
🔗

Définition 4.1.25. La factorielle.

Soit \(k\in\ \N\text{,}\) on définit \(k!\) (on dit la factorielle de \(k\text{,}\) ou bien \(k\) factorielle) comme étant le produit des nombres naturels de \(1\) jusqu’à \(k\text{.}\)
🔗
Par convention, on définit aussi \(0!=1\text{.}\) On justifiera un peu plus tard ce choix.
🔗
🔗

Exemple 4.1.26. Des exemples de factorielles.

On cherche à calculer les valeurs suivantes:
  1. \(4!\text{;}\)
    🔗
    🔗
  2. \(6!\text{;}\)
    🔗
    🔗
  3. \(7!\text{;}\)
    🔗
    🔗
  4. \(\frac{83!}{80!}\text{.}\)
    🔗
    🔗
🔗
Solution.
  1. Selon la définition, on a \(4!=4\times 3\times 2\times 1=24\text{;}\)
    🔗
    🔗
  2. De manière similaire, \(6!=6\times 5\times 4\times 3\times 2\times 1=720\text{.}\)
    🔗
    🔗
  3. Ici, il peut être intéressant de remarquer que \(7!=7\times (6\times 5\times 4\times 3\times 2\times 1)=7\times 6!\text{.}\) On peut donc se servir de la réponse précédente pour trouver \(7!=7\times 720=4040\text{.}\)
    🔗
    🔗
  4. Ici, vu la grandeur des nombres, on peut être tenté de prendre la calculatrice, mais il y a de fortes chances que celle-ci ne soit pas d’une grande aide. En raisonnant un peu comme pour le calcul précédant, on peut montrer que \(83!=83\times 82\times 81\times 80!\) et donc que \(\frac{83!}{80!}=\frac{83\times 82\times 81\times 80!}{80!}=83\times 82\times 81=551 286\text{.}\)
    🔗
    🔗
🔗
🔗
🔗

Remarque 4.1.27. Factorielle et calculatrice.

Il existe normalement une touche factorielle sur les calculatrices. Souvent identifiée par le symbole !, celle-ci permet de calculer la factorielle d’un nombre, mais il y a une limite due à la capacité de mémoire et d’affichage des calculatrices. Normalement, selon la calculatrice, cette limite est atteinte entre \(60!\) et \(70!\text{.}\)
🔗
🔗
On voit maintenant comment utiliser cette notation dans les problèmes de dénombrement.
🔗

Exemple 4.1.28. Disposition de cinq lettres.

On considère les lettres A,B,C,D,E. De combien de manières différentes peut-on ordonner ces lettres?
🔗
Solution.
Selon le principe du produit, on a \(5\times 4\times 3\times 2\times 1=5!=120\) possibilités. Ceci correspond bien à la réponse de l’exemple 4.1.10.
🔗
🔗
🔗
Pour le cas général, on obtient le résultat suivant.
🔗

Démonstration.

Il y a \(n\) manières de choisir le premier objet, puis \(n-1\) manières de choisir le deuxième et ainsi de suite jusqu’au dernier. Par le principe du produit, il y a
\begin{equation*} n\times (n-1)\times \cdots \times 2\times 1=n! \end{equation*}
manières au total.
🔗
🔗
Une question naturelle qui survient à ce moment, surtout dans le contexte où l’on réarrange des lettres est: que se passe-t-il si des lettres sont répétées? Si le nombre de lettres est relativement petit, on peut s’en sortir en énumérant tous les cas, mais on aimerait trouver une manière plus générale pour le cas où cela ne serait pas une réelle possibilité.
🔗

Exemple 4.1.30. Un cas avec des lettres répétées.

On considère le mot « bateau ». De combien de manières différentes peut-on réarranger les lettres de ce mot?
🔗
Solution 1.
On peut procéder d’une manière analogue à la méthode de l’exemple 4.1.28, mais cette fois-ci la lettre « a » est répétée. Ainsi, bien que le mot « bateau » contienne six lettres, on a seulement cinq choix pour la première lettre. Qu’en est-il pour la deuxième lettre? Tout dépend du choix effectué pour la première lettre. Si c’est un « a », on a encore cinq lettres possibles à utiliser, mais si c’est l’une des autres lettres, alors il ne reste que quatre possibilités. La méthode n’est donc pas aussi simple.
🔗
Plutôt que d’affecter une lettre à chacune des positions, on renverse la situation. Pour chaque lettre, on affecte une position dans le nouvel arrangement. L’astuce dans ce cas est de garder les « a » pour la fin. On a donc \(6\) positions possibles pour placer « b », puis \(5\) endroits pour placer « t », \(4\) endroits pour le « e » et \(3\) endroits pour la lettre « u ». Les deux positions restantes seront occupées par les lettres « a ». Il y a donc \(6\times 5\times 4\times 3=360\) possibilités. En voici deux d’entre elles:
\begin{align*} \underline{\text{a}}\underline{\text{b}}\underline{\text{t}}\underline{\text{a}}\underline{\text{u}}\underline{\text{e}}&,\underline{\text{u}}\underline{\text{a}}\underline{\text{t}}\underline{\text{b}}\underline{\text{e}}\underline{\text{a}}\text{.} \end{align*}
🔗
🔗
Solution 2.
Une autre façon de calculer le nombre de possibilités est de considérer le problème comme si les « a » étaient en fait disctincts. On pourrait écrire b\(\text{a}_1\)te\(\text{a}_2\)u et arranger ces six lettres discinctes en \(6!=720\) manières différentes. Or pour chacun de ces arrangements, il existe un arrangement jumeau où les positions de \(\text{a}_1,\text{a}_2\) sont inversées, mais qui ne se reflète pas dans le mot en tant que tel. On compte ainsi toutes les possibilités en double lorsque l’on dit qu’il y en a \(720\text{.}\) La réponse est donc \(720/2=360\) manières distinctes.
🔗
🔗
🔗
La première solution est astucieuse pour le cas où il n’y a qu’une lettre qui est répétée, mais dans un mot comme «SASTISFAIRE », l’approche n’est pas aussi concluante. On peut toutefois s’attarder à la seconde solution pour tenter de la généraliser. D’abord, un exemple plus simple.
🔗

Exemple 4.1.31.

De combien de manières distinctes peut-on arranger les lettres du mot « saucisse » pour former une chaine de caractères?
🔗
Solution.
En s’inspirant de la solution à l’exemple précédent, on compte qu’il y a huit lettres dans le mot «saucisse «, mais que la lettre « s » est répétée trois fois. Est-ce que chaque arrangement de ces huit lettres est compté trois fois alors? Pas tout à fait. Si l’on distingue les « s », il y a \(3\times 2 \times 1\) manières de les arranger. On compte donc une disposition spécifique des lettres non pas trois, mais six fois. Ainsi, il y a
\begin{equation*} \frac{8!}{6}=6720 \end{equation*}
manières d’arranger ces lettres.
🔗
🔗
🔗
On revient finalement au mot « SASTISFAIRE », qui contient deux fois la lettre « a », deux fois la lettre «i » et trois fois la lettre « s ». Si toutes les lettres étaient distinctes, il y aurait \(11!\) manières de les réordonner. En distinguant les « a », on compte en double tout comme avec les « i ». De plus, en distinguant les « s », on compte aussi chacun de ces arrangements six fois. Par le principe de division, il y a donc
\begin{equation*} \frac{11!}{2\times 2 \times 6}=151200 \end{equation*}
manières de disposer les lettres du mot « satisfaire ».
🔗
Une manière différente d’écrire le dernier calcul est
\begin{equation*} \frac{11!}{2!\times 2! \times 3!}=151200\text{,} \end{equation*}
provenant du fait que l’on peut ordonner les «a,i » de deux factorielles manières entre elles et les « s » de trois factorielles manières.
🔗
On revient sur l’exemple 4.1.22 pour le résoudre sous un autre angle.
🔗

Exemple 4.1.32.

On considère à nouveau le problème qui consiste à choisir \(3\) personnes parmi \(4\text{,}\) dans un premier temps sans leur attribuer de rôle spécifique puis en leur donnant les rôles de président, vice-président et trésorier.
🔗
Solution 1.
On imagine les quatre personnes en ligne, et on considère la chaine de caractères « PVSN », les lettres représentant respectivement les choix pour le président, le vice-président, le secrétaire et la personne qui ne sera pas choisie. Comme il y a quatre lettres et qu’aucune n’est répétée, il y a \(4!\) manières de choisir les gens qui feront partie du comité et de leur attribuer un rôle.
🔗
🔗
Solution 2.
On imagine à nouveau les quatre personnes en ligne et on considère cette fois la chaine de caractères « CCCN ». Ici, la lettre « C » représente être choisi et la lettre « N » ne pas l’être. On peut arranger ces lettres de \(\frac{4!}{3!1!}=6\) manières, qui permettent de sélectionner les personnes choisies.
🔗
🔗
🔗
Ces derniers exempes ouvre la porte au dernier principe de la section.
🔗

Exemple 4.1.34. Une course particulière.

Une course avec \(20\) participants a lieu dans une école. On veut utiliser le principe d’étiquetage pour déterminer:
  1. de combien de manières les participants peuvent franchir la ligne d’arrivée;
    🔗
    🔗
  2. de combien de manières on peut former le podium, c’est-à-dire les trois premières places;
    🔗
    🔗
  3. de combien de manières on peut donner une médaille d’or au cinq premiers coureurs, une médaille d’argent au sept suivants et une médaille de bronze au huit derniers.
    🔗
    🔗
🔗
🔗
Solution.
  1. On utilise les étiquettes \(P_1,P_2,\ldots , P_{20}\) pour identifier la position des coureurs. Comme toutes les étiquettes sont différentes, il y a \(20!\) possibilités.
    🔗
    🔗
  2. On utilise les étiquettes \(P,D,T,N,N,\ldots , N\text{,}\) où il y a \(17\) fois la lettre \(N\text{.}\) Selon le principe d’étiquetage, il y a \(\frac{20!}{1!1!1!17!}=20\times 19\times 18=6840\) manières différentes d’avoir le podium.
    🔗
    🔗
  3. On utilise les étiquettes \(OOOOOAAAAAAABBBBBBBB\text{.}\) On a donc \(\frac{20!}{5!7!8!}=99768240\) manières d’attribuer les médailles.
    🔗
    🔗
🔗
🔗
🔗
Dans les problèmes de dénombrement, on remarque qu’une petite modification à une question peut entraîner une grande différence dans la méthode de résolution. Il est alors important d’utiliser le bon principe au bon moment.
🔗
On remarque également que, pour résoudre certains problèmes, il est parfois plus facile de transformer celui-ci en un problème déjà résolu. À la section 4.2, on introduit quelques cas de base qui nous serviront à résoudre une grande partie des problèmes de dénombrement.
🔗

Questions de compréhension de la lecture 4.1.7 Questions de compréhension de la lecture

Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
🔗

1.

Un test est formé de \(10\) questions à choix multiples. Chaque question possède \(4\) réponses possibles.
🔗
(a)
De combien de façons un étudiant peut-il répondre aux questions s’il répond à toutes les questions?
🔗
(b)
De combien de façons un étudiant peut-il répondre aux questions s’il peut laisser une réponse vide à certaines questions?
🔗
🔗

2.

Une marque populaire de vêtements produit des chandails en \(12\) couleurs, en version à manches courtes ou à manches longues et est offert en trois tailles différentes. Combien de types de chandails différents sont produits par cette marque?
🔗
🔗

3.

Combien d’entiers \(0\leq n \lt 100\text{:}\)
🔗
(a)
sont divisibles par \(7\text{?}\)
🔗
🔗
(b)
sont divisibles par \(7\text{,}\) mais pas par \(11\text{?}\)
🔗
🔗
(c)
sont divisibles par \(7\) et par \(11\text{?}\)
🔗
(d)
sont divisibles par \(7\) ou par \(11\text{?}\)
🔗
(e)
sont divisibles par exactement un des entiers \(7\) ou \(11\text{?}\)
🔗
(f)
ne sont divisibles ni par \(7\) ni par \(11\text{?}\)
🔗
(g)
ont des chiffres différents les uns des autres?
🔗
(h)
ont des chiffres différents les uns des autres et sont pair?
🔗
🔗

4.

On considère des chaînes de trois caractères de chiffres en base \(10\text{.}\) Combien de ces chaînes:
🔗
(a)
ne contiennent pas le même chiffre trois fois?
🔗
🔗
(b)
ont exactement deux chiffres qui sont des \(4\text{?}\)
🔗
🔗
🔗

5.

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.1.8 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.
Combien de chaînes de quatre chiffres
🔗
(a)
sont formées de chiffres différents?
🔗
Réponse.
\(10\cdot 9\cdot 8\cdot 7=5040 \text{.}\)
🔗
🔗
Solution.
Lorsqu’on choisit le premier chiffre, il y a \(10\) possibilités. Pour chaque chiffre qu’on choisit par la suite, il y a toujours un choix de moins que pour le chiffre précédent. Ainsi, par le principe du produit, on a \(10\cdot 9\cdot 8\cdot 7=5040 \)
🔗
🔗
🔗
(b)
se terminent par un nombre pair?
🔗
Réponse.
\(5\cdot 10^3 = 5\,000\)
🔗
🔗
Solution.
On commence par choisir le dernier chiffre. Pour que celui-ci soit pair, il y a \(5\) choix possibles. Pour chacun des autres chiffres, il y a \(10\) possibilités, car les chiffres peuvent se répéter.
🔗
🔗
🔗
(c)
ont exactement trois chiffres qui sont des \(9\text{?}\)
🔗
Réponse.
\(9+9+9+9=36\)
🔗
🔗
Solution.
On conditionne sur la position du chiffre qui n’est pas un \(9\text{.}\) C’est-à-dire qu’on utilise le principe de la somme selon la position du chiffre qui n’est pas \(9\text{.}\)
🔗
Le chiffre est soit à la position \(1\text{,}\) soit à la position \(2\text{,}\) soit à la position \(3\) ou bien à la position \(4\text{.}\) Dans chacun des cas, il ne reste qu’à trouver la valeur de ce chiffre, car on sait que les autres chiffres sont des \(9\text{.}\) Il y aura donc \(9\) possibilités, soit \(0\text{,}\) \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(4\text{,}\) \(5\text{,}\) \(6\text{,}\) \(7\) ou \(8\text{.}\)
🔗
Ainsi, par le principe de la somme, il y a \(9+9+9+9=36\) possibilités.
🔗
🔗
🔗
🔗
2.
Lors de la finale de la course du \(100\) mètres aux derniers jeux Olympiques, il y avait \(8\) coureurs. De combien de manières possibles le podium pouvait-il être composé?
🔗
Réponse.
\(8\cdot 7\cdot 6\)
🔗
🔗
Solution.
On construit le podium en trois étapes. On choisit la personne qui est première, et ensuite la personne qui est deuxième, et finalement la personne qui est troisième. Il y a \(8\) choix pour la première personne, \(7\) choix pour la deuxième et \(6\) choix pour la troisième. Par le principe du produit, il y a \(8\cdot 7\cdot 6\) podiums différents.
🔗
🔗
🔗
3.
Combien de chaînes de sept lettres minuscules y a-t-il
🔗
(a)
si les lettres peuvent se répéter?
🔗
Réponse.
\(26^7 \)
🔗
🔗
Solution.
Il y a \(26\) possibilités pour chacune des sept lettres, puisqu’il peut y avoir des répétitions. Par le principe du produit, il y a \(26\cdot 26 \cdot 26\cdot 26\cdot 26\cdot 26\cdot 26 =26^7 \) chaînes possibles.
🔗
🔗
🔗
(b)
si les lettres ne peuvent pas se répéter?
🔗
Réponse.
\(26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21 \cdot 20 \)
🔗
🔗
Solution.
Pour la première lettre qu’on choisit, il y a \(26\) possibilités. Cependant, puisque les répétitions ne sont pas autorisées, il ne restera que \(26-1=25\) choix pour la deuxième lettre. De même, il ne restera que \(24\) lettres pour la troisième, et ainsi de suite. Par la principe du produit, il y a donc \(26\cdot 25\cdot 24 \cdot 23 \cdot 22 \cdot 21 \cdot 20\) chaînes différentes.
🔗
🔗
🔗
(c)
qui commencent par un “x”, si les lettres peuvent se répéter?
🔗
Réponse.
\(26^6 \)
🔗
🔗
Solution.
Puisque la première lettre est un “x”, il n’y a qu’une seule possibilité pour cette lettre. Puisque les répétitions sont permises, il y aura \(26\) choix pour les six lettres restantes. Par le principe du produit, il y aura \(1 \cdot 26 \cdot 26 \cdot 26 \cdot 26 \cdot 26 \cdot 26= 26^6\) chaînes différentes.
🔗
🔗
🔗
(d)
qui commencent par un “x”, si les lettres ne peuvent pas se répéter?
🔗
Réponse.
\(25\cdot 24\cdot 23\cdot 22\cdot 21 \cdot 20 \)
🔗
🔗
Solution.
Puisque la première lettre est un “x”, il n’y a qu’une seule possibilité pour cette lettre. Puisque les répétitions ne sont pas autorisées, il ne restera que \(26-1=25\) choix pour la deuxième lettre. De même, il ne restera que \(24\) lettres pour la troisième, et ainsi de suite. Par la principe du produit, il y a donc \(1\cdot 25\cdot 24 \cdot 23 \cdot 22 \cdot 21 \cdot 20\) chaînes différentes.
🔗
🔗
🔗
(e)
qui commencent et se terminent par un “x”, si les lettres peuvent se répéter?
🔗
Réponse.
\(26^5 \)
🔗
🔗
Solution.
Puisque la première lettre est un “x”, il n’y a qu’une seule possibilité pour cette lettre. De même, il n’y a qu’une seule possibilité pour la dernière lettre. Il reste cinq lettres à déterminer, et puisque les répétitions sont permises, il y a \(26\) choix possibles pour ces cinq lettres. Par le principe du produit, il y a \(1 \cdot 1\cdot 26\cdot 26\cdot 26\cdot 26\cdot 26 = 26^5\) chaînes différentes.
🔗
🔗
🔗
(f)
qui commencent par les lettres “bo” (dans cet ordre), si les lettres peuvent se répéter?
🔗
Réponse.
\(26^5 \)
🔗
🔗
Solution.
Puisque la première lettre est un “b”, il n’y a qu’une seule possibilité pour cette lettre. De même, il n’y a qu’une seule possibilité pour la deuxième lettre, car il s’agit d’un “o”. Il reste cinq lettres à déterminer, et puisque les répétitions sont permises, il y a \(26\) choix possibles pour ces cinq lettres. Par le principe du produit, il y a \(1 \cdot 1\cdot 26\cdot 26\cdot 26\cdot 26\cdot 26 = 26^5\) chaînes différentes.
🔗
🔗
🔗
(g)
qui commencent et se terminent par les lettres “bo” (dans cet ordre), si les lettres peuvent se répéter?
🔗
Réponse.
\(26^3 \)
🔗
🔗
Solution.
Puisque les deux premières lettres sont “bo”, il n’y a qu’une seule possibilité pour ces deux lettres. De même, il n’y a qu’une seule possibilité pour les deux dernières lettres, qui sont aussi “bo”. Il reste trois lettres à déterminer, et puisque les répétitions sont permises, il y a \(26\) choix possibles pour ces trois lettres. Par le principe du produit, il y a \(1 \cdot 1\cdot 1\cdot 1\cdot 26\cdot 26\cdot 26 = 26^3\) chaînes différentes.
🔗
🔗
🔗
(h)
qui commencent ou se terminent par les lettres “bo” (dans cet ordre), si les lettres peuvent se répéter?
🔗
Réponse.
\(26^5+26^5-26^3 \)
🔗
🔗
Solution.
On note \(C_{bo}\) les chaînes commençant par “bo”. Par l’exercice 4.1.8.3.f, on a que \(C_{bo}=26^5\text{.}\) On note ensuite \(C^{bo}\) les chaînes se terminant par “bo”. Par un argument similaire, on a que \(C^{bo}=26^5\text{.}\) Finalement, on note \(C_{bo}^{bo}\) les chaînes qui commencent et se terminent par “bo”. Par l’exercice 4.1.8.3.g, on a que \(C_{bo}^{bo}=26^3\text{.}\) Par le principe d’inclusion-exclusion, le nombre de chaînes qui commencent ou se terminent par les lettres “bo” sera \(C_{bo} + C^{bo} - C_{bo}^{bo} = 26^5+26^5-26^3\text{.}\)
🔗
🔗
🔗
🔗
4.
Soit \(E\) un ensemble tel que \(|E|=100\text{.}\) Combien de sous-ensembles de \(E\) possèdent plus d’un élément?
🔗
Réponse.
\(2^{100}-101\)
🔗
🔗
Solution.
Il y a \(2^{100}\) sous-ensembles au total. Il y a un sous-ensemble qui ne contient aucun élément (l’ensemble vide) et il y a \(100\) sous-ensembles contenant un seul élément. Ainsi, il y aura \(2^{100}-101\) sous-ensembles avec plus d’un élément.
🔗
🔗
🔗
5.
On considère les entiers \(n\) tels que \(0\lt n\lt 1\,000\,000\text{.}\)
🔗
(a)
Combien de ces entiers \(n\) sont divisibles par \(4\) ou \(6\text{?}\)
🔗
Indice.
Pour être divisible par \(4\) et par \(6\text{,}\) il faut et il suffit d’être divisible par \(12\text{.}\)
🔗
🔗
Réponse.
\(333\,332 \)
🔗
🔗
Solution.
On note \(N_4 = \{n\in \N ~|~ 0 \lt n \lt 1\ 000\ 000 \text{ et } 4 \text{ divise } n\}\text{.}\) Si \(4|n\text{,}\) alors \(n\) s’écrit comme \(n=4 t\) pour \(t\in \Z\text{.}\) Ainsi, on peut réécrire \(N_4\) comme \(N_4 = \{4t \in \N ~|~ 0 \lt 4t \lt 1\ 000\ 000 \text{ et } t\in \Z\}\text{.}\) On peut alors conclure que \(|N_4|\) est le nombre de \(t\) satisfaisant les inéquations \(0 \lt 4t \lt 1\ 000\ 000\text{.}\) En divisant par \(4\text{,}\) celles-ci deviennent alors \(0 \lt t \lt 250\ 000 \text{,}\) ou encore \(1\leq t \leq 249\ 999\text{.}\) Ansi, \(|N_4|=249\ 999\text{.}\)
🔗
On note ensuite \(N_6 = \{n\in \N ~|~ 0 \lt n \lt 1\ 000\ 000 \text{ et } 6 \text{ divise } n\}\text{.}\) Par le même argument que pour \(N_4\text{,}\) on a que \(|N_6|\) est le nombre de \(t\) satisfaisant les inéquations \(0 \lt 6t \lt 1\ 000\ 000\text{.}\) En divisant par \(6\text{,}\) celles-ci deviennent alors \(0 \lt t \lt \frac{1\ 000\ 000}{6} = 166\ 666,\overline{6} \text{,}\) ou encore \(1\leq t \leq 166\ 666\text{.}\) Ansi, \(|N_6|=166\ 666\text{.}\)
🔗
Enfin, on note \(N_{12} = \{n\in \N ~|~ 0 \lt n \lt 1\ 000\ 000 \text{ et } 12 \text{ divise } n\}\text{.}\) Par le même argument que pour \(N_4\text{,}\) on a que \(|N_{12}|\) est le nombre de \(t\) satisfaisant les inéquations \(0 \lt 12t \lt 1\ 000\ 000\text{.}\) En divisant par \(12\text{,}\) celles-ci deviennent alors \(0 \lt t \lt \frac{1\ 000\ 000}{12} = 83\ 333,\overline{3} \text{,}\) ou encore \(1\leq t \leq 83\ 333\text{.}\) Ansi, \(|N_6|=83\ 333\text{.}\)
🔗
Par le principe d’inclusion-exclusion, et par l’indice, on a que le nombre d’entiers \(n\) tels que \(0 \lt n \lt 1\ 000\ 000\) avec \(4|n\) ou \(6|n\) est donné par \(|N_{4}|+|N_{6}|-|N_{12}|=249\ 999 + 166\ 666-83\ 333=333\ 332\text{.}\)
🔗
🔗
🔗
(b)
Combien de ces entiers \(n\) ne sont divisibles ni par \(4\) ni par \(6\text{?}\)
🔗
Indice.
L’énoncé “n’est divisible ni par \(4\text{,}\) ni par \(6\)” est la négation de l’énoncé “est divisible par \(4\) ou par \(6\)”.
🔗
🔗
Réponse.
\(666\,667\)
🔗
🔗
Solution.
On sait qu’il y a \(9\999\ 999\) entiers \(n\) tels que \(0 \lt n \lt 1\ 000\ 000\text{.}\) Par le principe de la soustraction, l’indice et l’exercice 4.1.8.5.a, on a que parmi les entiers \(n\) tels que \(0 \lt n \lt 1\ 000\ 000\text{,}\) le nombre de ceux-ci qui ne sont divisibles ni par \(4\text{,}\) ni par \(6\) est \(9\ 999\ 999 - 333\ 332\)
🔗
🔗
🔗
🔗
6.
Supposons qu’un mot de passe pour un système informatique doit avoir entre \(8\) et \(12\) (inclusivement) caractères, où chaque caractère est soit une lettre minuscule ou majuscule, un chiffre ou l’un des caractères spéciaux \(\ast,\, \gt,\,\lt,\,!,\,+\text{ et }= \text{.}\)
🔗
(a)
Combien de mots de passe différents sont disponibles pour ce système informatique?
🔗
Indice.
\(26+26+10+6\)
🔗
Réponse.
\(68^{8}+68^{9}+68^{10}+68^{11}+68^{12}=9\,920\,671\,339\,261\,325\,541\,376\)
🔗
🔗
Solution.
On note \(P_i\) le nombre de mots de passe valides composés \(i\) caractères, pour \(i\in \{8,9,10,11,12\}\text{.}\)
🔗
En utilisant le principe du produit sur chaque \(P_i\text{,}\) on a que
\begin{align*} P_{8}\amp = 68^{8} \\ P_{9}\amp = 68^{9} \\ P_{10}\amp = 68^{10} \\ P_{11}\amp = 68^{11} \\ P_{12}\amp = 68^{12} \end{align*}
🔗
Ensuite, en utilisant le principe de la somme, on a que le nombre de mots de passe disponible est \(P_{8}+P_{9}+P_{10}+P_{11}+P_{12}=68^{8}+68^{9}+68^{10}+68^{11}+68^{12}\text{.}\)
🔗
🔗
🔗
(b)
Combien de ces mots de passe contiennent au moins un des caractères spéciaux?
🔗
Indice.
Combien de ces mots de passe ne contiennent pas de caractères spéciaux?
🔗
🔗
Réponse.
\(\left(68^{8}+68^{9}+68^{10}+68^{11}+68^{12}\right) - \left( 62^{8}+62^{9}+62^{10}+62^{11}+62^{12}\right)=6\,641\,514\,961\,387\,068\,437\,760\)
🔗
🔗
Solution.
On commence par trouver le nombre de mots de passe qui ne contiennent pas de caractères spéciaux, qu’on notera \(P^n\text{.}\) Par un argument similaire à celui de l’exercice 4.1.8.6.a, on a que \(P^n=62^{8}+62^{9}+62^{10}+62^{11}+62^{12}\text{.}\)
🔗
Par le principe de la soustraction et par l’exercice 4.1.8.6.a, on a que le nombre de mots de passe qui contiennent au moins un des caractères spéciaux est \(\left(68^{8}+68^{9}+68^{10}+68^{11}+68^{12}\right) - \left( 62^{8}+62^{9}+62^{10}+62^{11}+62^{12}\right)\)
🔗
🔗
🔗
🔗
7.
On considère l’ensemble des propositions formées à partir de \(n\) propositions atomiques.
🔗
(a)
Combien de lignes possède le tableau de vérité d’une de ces propositions?
🔗
Indice.
Chaque de ligne dans le tableau de vérité correspond à une combinaison des valeurs de vérités des \(n\) propositions atomiques.
🔗
🔗
Réponse.
\(2^n\)
🔗
🔗
Solution.
Tel qu’indiqué dans l’indice, chaque ligne du tableau de vérité correspond à un choix de la valeur de vérité des propositions atomiques. Puisqu’il y a deux possibilités pour la valeur de vérité d’une proposition, par le principe du produit, il y aura \(2\cdot 2\cdots 2 = 2^n\) lignes.
🔗
🔗
🔗
(b)
Combien de tableaux de vérité différents y a-t-il pour ces propositions? On considère que deux tableaux sont les mêmes si leur dernière colonne sont les mêmes.
🔗
Indice 1.
On considère que deux tableaux de vérités sont les mêmes si les propositions se trouvant à la dernière colonne sont équivalentes.
🔗
🔗
Indice 2.
Si \(P\) est une proposition de cet ensemble, pour chaque ligne du tableau de vérité, combien de valeur de vérité est-ce que \(P\) peut avoir ?
🔗
🔗
Réponse.
\(2^{2^n}\)
🔗
🔗
Solution.
Pour chacune des lignes du tableau de vérité d’une proposition \(P\text{,}\) celle-ci est vraie ou fausse. Il y a donc \(2\) possibilités par ligne. Par le principe du produit, il y aura \(2\cdot 2\cdots 2 = 2^{\text nombre de ligne}\) possibilités pour les valeurs de vérité de \(P\text{.}\) Par l’exercice 4.1.8.7.a, on sait que le tableau de vérité de la proposition \(P\) sera formé de \(2^n\) lignes. Ainsi, il y a \(2^{2^n}\) propositions différentes formées à partir de \(n\) propositions atomiques.
🔗
🔗
🔗
🔗
8.
On considère les fonctions \(f:\{1,2,\dots,n\}\to \{0,1\}\) où \(n\in\,\N^\ast\text{.}\)
🔗
(a)
Combien de ces fonctions sont injectives?
🔗
Réponse.
Si \(n=1\text{,}\) il y en a \(2\text{.}\) Si \(n=2\text{,}\) il y en a aussi 2. Si \(n\geq3\text{,}\) il y en a \(0\text{.}\)
🔗
🔗
Solution.
Si \(n=1\text{,}\) alors on considère une fonction injective \(f:\{1\}\to \{0,1\}\text{.}\) Pour déterminer \(f\text{,}\) il suffit de déterminer la valeur de \(f(1)\text{.}\) Il y a deux valeurs possibles (\(f(1)=0\) ou bien \(f(1)=1\)). Dans les deux cas, la fonction \(f\) sera injective.
🔗
Si \(n=2\text{,}\) alors on considère une fonction injective \(f:\{1,2\}\to \{0,1\}\text{.}\) Pour déterminer \(f\text{,}\) il suffit de déterminer la valeur de \(f(1)\) ainsi que la valeur de \(f(2)\text{.}\) Si on commence par choisir la valeur de \(f(1)\text{,}\) alors il y a deux valeurs possibles (\(f(1)=0\) ou bien \(f(1)=1\)). Ensuite, pour que \(f\) soit injective, il faut et il suffit que \(f(1)\neq f(2)\) . Ainsi, il ne restera qu’une seule valeur possible pour \(f(2)\text{.}\) Par le principe du produit, il y aura \(2\cdot 1 = 2\) fonctions injectives possibles.
🔗
Finalement, si \(n\geq 3\text{,}\) alors on considère une fonction injective \(f:\{1,2,3,\dots,n\}\to \{0,1\}\text{.}\) Après avoir choisi la valeur de \(f(1)\) et la valeur de \(f(2)\text{,}\) puisque \(f(1)\neq f(2)\text{,}\) alors on aura soit \(f(1)=0\) et \(f(2)=1\text{,}\) ou bien \(f(1)=1\) et \(f(2)=0\text{.}\) Dans les deux cas, il sera impossible de choisir une valeur pour \(f(3)\) telle que \(f(1)\neq f(3)\) et \(f(2)\neq f(3)\text{.}\) Il n’y a donc aucune fonction injective \(f:\{1,2,3,\dots,n\} \to \{0,1\}\) si \(n\geq 3\text{.}\)
🔗
🔗
🔗
(b)
Combien de ces fonctions sont telles que \(f(1)=f(n)=0\text{?}\)
🔗
Réponse.
Si \(n=1\) ou \(n=2\text{,}\) il y en a une seule. Si \(n \geq 3\text{,}\) il y en a \(2^{n-2}\text{.}\)
🔗
🔗
🔗
(c)
Combien de ces fonctions sont telles que \(|f^{-1}(1)\cap\{1,2,\dots,n-1\}|=1\text{?}\)
🔗
Indice.
Ici, on doit supposer que \(n\geq 2\text{,}\) car sinon la notation \(\{1,2,\dots,n-1\}\) n’est pas cohérente.
🔗
🔗
Réponse.
Si \(n\geq 2\text{,}\) alors il y aura \(2\cdot(n-1)\) fonctions qui respectent la condition.
🔗
🔗
Solution.
À faire
🔗
🔗
🔗
🔗
9.
Pour un mariage, de combien de façons différentes est-ce qu’un photographe peut arranger en une ligne \(6\) personnes d’un groupe de \(10\text{,}\) où les mariés sont dans le groupe de \(10\text{,}\) si
🔗
(a)
la mariée doit être sur la photo?
🔗
Indice.
On commence par placer la mariée. Une fois la mariée placée, il reste à placer \(5\) personnes parmi les \(9\) personnes restantes.
🔗
🔗
Réponse.
\(6\frac{9!}{4!}=90720\)
🔗
🔗
🔗
(b)
les mariés doivent tous deux être sur la photo?
🔗
Indice.
On commence par placer la mariée. Une fois la mariée placée, on place le marié. Une fois les mariés placés, il reste à placer \(4\) personnes parmi les \(8\) personnes restantes.
🔗
🔗
Réponse.
\(6\cdot 5\frac{8!}{4!}=50400\)
🔗
🔗
🔗
(c)
exactement un des mariés doit être sur la photo?
🔗
Indice 1.
On commence par choisir si c’est la mariée ou le marié qui est sur la photo.
🔗
🔗
Indice 2.
On peut aussi utiliser le principe de la somme selon lequel des deux est sur la photo.
🔗
🔗
Réponse.
\(6\frac{8!}{3!}+6\frac{8!}{3!}=80640\)
🔗
🔗
🔗
🔗
10.
Pour un mariage, de combien de façons différentes est-ce qu’un photographe peut arranger en une ligne \(6\) personnes, incluant les mariés, si
🔗
(a)
les mariés doivent être l’un à côté de l’autre?
🔗
Indice.
On peut considérer les mariés comme une seule personne! Il suffit de choisir qui est à gauche, et qui est à droite!
🔗
🔗
Réponse.
\(240\)
🔗
🔗
🔗
(b)
la mariée n’est pas à côté du marié?
🔗
Indice 1.
On vient d’énumérer les façons d’accomplir cette tâche si les mariés sont l’un à côté de l’autre. Comment faire pour calculer le complément?
🔗
🔗
Indice 2.
De combien de façons peut-on accomplir la tâche sans aucune restriction?
🔗
🔗
Réponse.
\(480\)
🔗
🔗
🔗
(c)
la mariée est quelque part à gauche du marié?
🔗
Indice.
De combien de façons peut-on accomplir la tâche sans aucune restriction? Parmi ces façons, y a-t-il plus de façons d’avoir la mariée à droite ou à gauche du marié?
🔗
🔗
Réponse.
\(360\)
🔗
🔗
🔗
🔗
11.
On lance une pièce de monnaie \(8\) fois. De combien de manières peut-on obtenir \(5\) fois le résultat Pile et \(3\) fois le résultat Face?
🔗
Réponse.
\(56\) manières
🔗
🔗
Solution.
On utilise le principe d’étiquetage avec les caractères \(PPPPPFFF\text{.}\) On obtient \(\frac{8!}{3!5!}=56\) possibilités.
🔗
🔗
🔗
12.
Un groupe de \(12\) amis se rencontre dans un parc. Ils décident de former une ligne pour commander une crème glacée.
🔗
(a)
De combien de manières la ligne peut-elle être formée?
🔗
Réponse.
\(12!\)
🔗
🔗
Solution.
Selon la proposition 4.1.29, il y a \(12!\) manières.
🔗
🔗
🔗
(b)
De combien de manières la ligne peut-elle être formée si le groupe contient \(3\) garçons et \(9\) filles et que les garçons font la ligne ensemble, tout comme les filles?
🔗
Réponse.
\(4354560\) manières
🔗
🔗
Solution.
On imagine deux blocs \(G,F\text{,}\) l’un contenant les garçons, l’autre contenant les filles. Par le principe d’addtion, le nombre total de possibilités sera obtenu en considérant la dispotion \(GF\) et la disposition \(FG\text{.}\) Pour chacune de ces possibilités, il faut arranger les membres garçons entre eux et les membres filles entre elles. Par le principe de multiplication, il y a \(3!9!=2177280\) manières. Ainsi, le nombre total de possibilités est de \(2\times 30240=4354560\text{.}\)
🔗
🔗
🔗
(c)
Indépendamment de tout ce qui précède, de combien de manières peut-on former la ligne si les amis Amélie, Brad et Charlie veulent rester grouper?
🔗
Solution.
On utilise le principe d’étiquetage et le principe de multiplication. Dans un premier temps, on note \(M\) groupe de trois amis inséparables. Il faut donc arranger la chaine \(M,A_1,A_2,A_3,A_4,A_5,A_6,A_7,A_8,A_9\text{.}\) On peut arranger cette chaine de \(10!\) manières. Pour chacune de celles-ci, on peut aussi changer l’ordre d’apparition des trois amis \(M=ABC\text{.}\) On a \(3!\) manière de faire cela, pour un total de \(3!10!=21772800\) possibilités.
🔗
🔗
🔗
🔗
13.
On considère l’équation \(x+y+z=14\text{.}\) Combien de solutions y a-t-il si \(x,y,z\in \mathbb{N}\text{?}\)
🔗
Solution.
On imagine \(14\) fois le symbole \(1\) écrit en ligne. Si on sépare ces symboles en trois groupes, on obtiendra une solution à l’équation. Par exemple, la disposition \(11|111111|111111\) correspond à \(x=2,y=6,z=6\text{.}\) De manières générales, on a \(14\) symboles \(1\) et deux séparateurs à disposer. Il y a donc
\begin{equation*} \frac{16!}{14!2!}=120 \end{equation*}
solutions.
🔗
🔗
🔗
🔗

Exercices supplémentaires

14.
Combien de chaînes binaires de longueur \(10\) contiennent cinq \(1\) consécutifs ou cinq \(0\) consécutifs?
🔗
Indice 1.
Utiliser le principe de la somme en séparant selon l’endroit où commence la séquence de longueur cinq. Il y aura plusieurs cas à considérer.
🔗
Il faudra aussi utiliser le principe d’inclusion-exclusion.
🔗
🔗
Indice 2.
Attention! La chaîne binaire peut contenir plus de cinq \(1\) ( ou \(0\)) consécutifs. C’est-à-dire qu’il faut compter la chaîne \(1111110000\)
🔗
🔗
Réponse.
\(222\)
🔗
Solution.
On commence par compter celles qui ont une séquence de cinq \(1\) consécutifs. De plus, on conditionne sur la position du premier \(1\) de la première séquence de \(1\) consécutifs.
🔗
Si la séquence commence à la première position, les chaînes seront de la forme \(11111\ast\ast\ast\ast\ast\text{,}\) où les \(\ast\) sont quelconques (\(0\text{ ou }1\)). Il y a donc \(2^5\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la deuxième position, les chaînes seront de la forme \(011111\ast\ast\ast\ast\text{.}\) Il y a donc \(2^4\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la troisième position, les chaînes seront de la forme \(\ast011111\ast\ast\ast\text{.}\) Il y a donc \(2^4\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la quatrième position, les chaînes seront de la forme \(\ast\ast011111\ast\ast\text{.}\) Il y a donc \(2^4\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la cinquième position, les chaînes seront de la forme \(\ast\ast\ast011111\ast\text{.}\) Il y a donc \(2^4\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la sixième position, les chaînes seront de la forme \(\ast\ast\ast\ast011111\text{.}\) Il y a donc \(2^4\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Ainsi, il y a \(2^5+2^4+2^4+2^4+2^4+2^4=112\) chaînes ayant une séquence de cinq \(1\) consécutifs. Par symétrie du problème, on sait qu’il y aura autant de chaînes ayant une chaîne de cinq \(0\) consécutifs.
🔗
Finalement, on doit remarquer qu’il y a deux chaînes qui possèdent une séquence de cinq \(1\) consécutifs et une séquence de cinq \(0\) consécutifs. Il s’agit de \(1111100000\) et \(0000011111\)
🔗
Par le principe d’inclusion-exclusion, on a \(112+112-2=222\)
🔗
🔗
🔗
15.
Combien de chaînes binaires de longueur \(8\) contiennent quatre \(1\) consécutifs ou trois \(0\) consécutifs?
🔗
Indice.
Cette question est similaire au numéro précédent, mais plus difficile, car on peut avoir plusieurs fois trois \(0\) consécutifs dans la même chaîne.
🔗
🔗
Réponse.
\(147\)
🔗
Solution.
On commence par compter celles qui ont une séquence de quatre \(1\) consécutifs. De plus, on conditionne sur la position du premier \(1\) de la première séquence de \(1\) consécutifs.
🔗
Si la séquence commence à la première position, les chaînes seront de la forme \(1111\ast\ast\ast\ast\text{,}\) où les \(\ast\) sont quelconques (\(0\text{ ou }1\)). Il y a donc \(2^4\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la deuxième position, les chaînes seront de la forme \(01111\ast\ast\ast\text{.}\) Il y a donc \(2^3\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la troisième position, les chaînes seront de la forme \(\ast01111\ast\ast\text{.}\) Il y a donc \(2^3\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la quatrième position, les chaînes seront de la forme \(\ast\ast01111\ast\text{.}\) Il y a donc \(2^3\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Si la séquence commence à la cinquième position, les chaînes seront de la forme \(\ast\ast\ast01111\text{.}\) Il y a donc \(2^3\) chaînes dont la séquence de \(1\) commence à cette position.
🔗
Ainsi, il y a \(2^4+2^3+2^3+2^3+2^3=48\) chaînes ayant une séquence de cinq \(1\) consécutifs.
🔗
Par la suite, on compte celles qui ont une séquence de trois \(0\) consécutifs. De plus, on conditionne sur la position du premier \(0\) de la première séquence de \(0\) consécutifs.
🔗
Si la séquence commence à la première position, les chaînes seront de la forme \(000\ast\ast\ast\ast\ast\text{,}\) où les \(\ast\) sont quelconques (\(0\text{ ou }1\)). Il y a donc \(2^5\) chaînes dont la première séquence de \(0\) commence à cette position.
🔗
Si la séquence commence à la deuxième position, les chaînes seront de la forme \(1000\ast\ast\ast\ast\text{.}\) Il y a donc \(2^4\) chaînes dont la première séquence de \(0\) commence à cette position.
🔗
Si la séquence commence à la troisième position, les chaînes seront de la forme \(\ast\ast1000\ast\ast\text{.}\) Il y a donc \(2^4\) chaînes dont la première séquence de \(0\) commence à cette position.
🔗
Si la séquence commence à la quatrième position, les chaînes seront de la forme \(\ast\ast\ast1000\ast\text{,}\) mais ne peut pas être \(0001000\ast\) car la première séquence doit commencer à la quatrième position! Il y a donc \(2^4-2\) chaînes dont la première séquence de \(0\) commence à cette position.
🔗
Si la séquence commence à la cinquième position, les chaînes seront de la forme \(\ast\ast\ast\ast1000\text{.}\) Cependant, il y a \(3\) chaînes ayant une séquence d’au moins trois \(0\) au début de la chaîne. Il s’agit de \(00001000\text{,}\) \(00011000\) et \(10001000\text{.}\) Il y a donc \(2^4-3\) chaînes dont la première séquence de \(0\) commence à cette position.
🔗
Ainsi, il y a \(2^5+2^4+2^4+2^4+(2^4-2)+(2^4-3)=107\) chaînes ayant une séquence de cinq \(1\) consécutifs.
🔗
Finalement, on doit remarquer qu’il y a huit chaînes qui possèdent une séquence de quatre \(1\) consécutifs et une séquence de trois \(0\) consécutifs.
🔗
Par le principe d’inclusion-exclusion, on a \(48+107-8=147\text{.}\)
🔗
🔗
🔗
🔗
🔗
🔗
PrécédentTopSuivant