Dénombrement

Leçon 1 : Premiers outils de dénombrement

OBJECTIFS

À la fin de cette leçon l’élève doit être capable de dénombrer avec :

• Relation entre les parties d’un ensemble fini
• Les arbres de choix, les tableaux à double entrée
• Les produits cartésiens

SITUATION PROBLÈME

L’enseignant de Njoya lui propose le problème suivant : « Dans un camp de vacances hébergeant 80 personnes, 55 personnes pratiquent la natation, 33 le tennis et 16 ne pratiquent aucun des deux sports. Combien de personnes pratiquent à la fois le tennis et la natation ? »

En cas de solution juste, l’enseignant promet à Njoya un menu dans un restaurant où l’on propose les plats suivants :

• Entrées : une salade (S), une purée d’avocats (P)
• Résistance : Koki (K), pilé de pomme de terre (Pi) et Njapche (N)
• Desserts : Ananas (A), Orange (O) et Mangue (M)

1. Quelle solution proposer à Njoya pour avoir cette récompense ?
2. Quel est le nombre de menus possibles en cas de solution juste pour Njoya ?

1- RELATION ENTRE LES PARTIES D’UN ENSEMBLE FINI

ACTIVITÉ 1.1.1

On donne les ensembles $E=\{0,1,2,3,4,5,6,7,8,9\}$, $A=\{1,5,9,8\}$ et $B=\{2,5,8,0,4\}$.

1. Quels sont les cardinaux de chacun de ces ensembles ? Que représentent les ensembles $A$ et $B$ pour l’ensemble $E$ ?
2. Déterminer l’ensemble $A\cup B$ des éléments qui sont dans $A$ ou dans $B$.
3. Déterminer l’ensemble $A\cap B$ des éléments qui sont dans $A$ et dans $B$.
4. Comparer $\text{card}(A\cup B)$ avec $\text{card}(A)+\text{card}(B)-\text{card}(A\cap B)$.
5. Déterminer l’ensemble $\overline{A}$ des éléments qui ne sont pas dans $A$ et l’ensemble $A-B$ des éléments de $A$ qui ne sont pas dans $B$.
6. Comparer $\text{card}(A)$ et $\text{card}(E)-\text{card}(A)$, puis $\text{card}(A-B)$ et $\text{card}(A)-\text{card}(A\cap B)$.

RÉSUMÉ

VOCABULAIRE

Soit $E$ un ensemble fini et soient $A$ et $B$ deux parties de $E$.

• $A$ est une partie de $E$ si tous les éléments de $A$ sont aussi des éléments de $E$ et dans ce cas $\text{card}(A)\leq \text{card}(E)$.
• $A \cup B$ est l’ensemble des éléments qui sont dans $A$ ou dans $B$.
• $A \cap B$ est l’ensemble des éléments qui sont dans $A$ et dans $B$.
• $\overline{A}$ ou complémentaire de $A$ dans $E$ est l’ensemble des éléments de $E$ qui ne sont pas dans $A$.
• $A - B$ est l’ensemble des éléments de $A$ qui ne sont pas dans $B$.

PROPRIÉTÉ

On a les propriétés suivantes sur les parties d’un ensemble fini :

• $\text{card}(A \cup B)=\text{card}(A)+\text{card}(B)-\text{card}(A \cap B)$
• $\text{card}(\overline{A})=\text{card}(E)-\text{card}(A)$
• $\text{card}(A-B)=\text{card}(A)-\text{card}(A \cap B)$

Ces propriétés peuvent se représenter par le diagramme suivant appelé diagramme de Venn.

APPLICATION

1. Dans une classe de 3^e, tous les élèves étudient au moins l’espagnol et l’allemand. 30 étudient l’espagnol, 20 étudient l’allemand et 15 étudient l’espagnol et l’allemand. Quel est le nombre d’élèves de cette classe ?
2. Dans une classe, 3 langues sont pratiquées. On sait que 20 élèves font l’anglais, 15 l’allemand, 18 l’espagnol, 7 l’anglais et l’allemand, 9 l’allemand et l’espagnol, 8 l’anglais et l’espagnol et enfin 5 pratiquent les trois langues. Quel est le nombre d’élèves de la classe sachant que chacun fait au moins une langue ?

2- PRODUIT CARTÉSIEN

ACTIVITÉ

On donne les ensembles $A=\{a,b,c\}$ et $B=\{1,2\}$.

1. Complète en colonnes (sur chaque croisement de segment) l’arbre de choix suivant :

2. Déterminer l’ensemble $A \times B$ de tous les couples $(x\,;y)$ tels que $x \in A$ et $y \in B$.
3. Comparer $\text{card}(A \times B)$ et $\text{card}(A)\times\text{card}(B)$.

RÉSUMÉ

DÉFINITION

Soient $E_1$ et $E_2$ deux ensembles finis.

On appelle $E_1 \times E_2$ (produit cartésien de $E_1$ et $E_2$) l’ensemble des couples $(x_1\,;x_2)$ tels que $x_1 \in E_1$ et $x_2 \in E_2$.

Le nombre d’éléments de $E_1 \times E_2$ est $\text{card}(E_1 \times E_2)=\text{card}(E_1)\times\text{card}(E_2)$.

De manière générale, soient $E_1, E_2, \ldots, E_n$ des ensembles finis.

On appelle produit cartésien $E_1 \times E_2 \times \ldots \times E_n$ l’ensemble des éléments sous la forme $(x_1\,;x_2\,;\ldots\,;x_n)$ tels que $x_1 \in E_1,\; x_2 \in E_2,\; \ldots,\; x_n \in E_n$.

On a : $\text{card}(E_1 \times E_2 \times \ldots \times E_n) = \text{card}(E_1)\times\text{card}(E_2)\times\ldots\times\text{card}(E_n)$.

REMARQUE

Les éléments d’un produit cartésien peuvent s’obtenir, lorsque les cardinaux sont faibles, en établissant un arbre de choix.

APPLICATION

1. Une femme a dans sa garde-robe : 4 jupes, 5 chemisiers et 3 vestes. Elle choisit au hasard une jupe, un chemisier et une veste. Combien de façons différentes peut-elle ainsi s’habiller ?
2. Deux groupes de 12 et de 15 décident de faire la paix en échangeant des poignées de mains. Chaque membre d’un groupe serre la main de tous les membres de l’autre groupe. Combien de poignées de mains seront-elles échangées ?

3- TABLEAU À DOUBLE ENTRÉE

ACTIVITÉ

Dans une classe de 50 élèves : 24 ont 16 ans, 14 ont 17 ans et les autres ont plus de 17 ans. 23 élèves ont opté pour l’espagnol comme deuxième langue et les autres ont opté pour l’allemand. 13 élèves de 16 ans font l’espagnol, 10% des élèves de plus de 17 ans font l’allemand.

1. Compléter le tableau suivant :

2. Comment appelle-t-on ce type de tableau ?
3. Combien d’élèves n’ont pas 16 ans et ne font pas l’espagnol ?

RÉSUMÉ

Dans certains cas pour facilement dénombrer, on peut utiliser un tableau à double entrée.

APPLICATION

Une tentative d’homicide a eu lieu au cours d’un bal. La police a arrêté 18 suspects et leur a demandé de répondre par oui ou par non à chacune des questions suivantes :

« Avez-vous entendu une détonation ? » et « Avez-vous vu quelqu’un s’enfuir ? »

10 personnes ont répondu « oui » à la première question, 5 personnes ont répondu « non » à la deuxième question et 6 personnes ont répondu « non » aux deux questions. Quel est le nombre de personnes ayant « oui » aux deux questions ?

Leçon 2 : p-uplets avec ou sans répétition

OBJECTIFS

À la fin de cette leçon l’élève doit être capable de :

• reconnaître un p-uplet ou un p-arrangement ;
• dénombrer avec les p-uplets et les p-arrangements ;
• reconnaître une permutation et dénombrer avec les permutations.

SITUATION PROBLÈME

Pour ouvrir un coffre-fort urgentement, Pemboura doit utiliser un code de 4 chiffres en se servant de 3 indices qui lui arrivent avant chaque tentative ratée :

• indice 1 : les chiffres peuvent se répéter dans le code ;
• indice 2 : les chiffres ne peuvent pas se répéter dans le code ;
• indice 3 : les chiffres qui composent le code sont 1, 4, 7 et 9.

1. Quel est le nombre de codes possibles après l’indice 1 ?
2. Quel est le nombre de codes possibles après l’indice 2 ?
3. Quel est le nombre de codes possibles après l’indice 3 ?

ACTIVITÉ

Soit $E = \{1,2,3,4\}$.

I

1. Détermine tous les couples $(x;y)$ tels que $x,y \in E$. Quel est le nombre total de couples obtenu ?
2. Dans ces couples, l’ordre importe-t-il ? Peut-il y avoir répétition ?
3. 1. Combien de possibilités y a-t-il pour le choix de $x$ ?
   2. Combien de possibilités y a-t-il pour le choix de $y$ ?
   3. En déduire une astuce pour déterminer le nombre de couples $(x;y)$.

II

1. Détermine tous les couples $(x;y)$ tels que $x,y \in E$ et $x \neq y$. Quel est le nombre total de couples obtenu ?
2. Dans ces couples, l’ordre importe-t-il ? Peut-il y avoir répétition ?
3. 1. Combien de possibilités y a-t-il pour le choix de $x$ ?
   2. Combien de possibilités y a-t-il pour le choix de $y$ ?
   3. En déduire une astuce pour déterminer le nombre de couples $(x;y)$.

III

1. Détermine tous les quadruplets $(x;y;z;t)$ tels que $x,y,z,t \in E$ et $x \neq y \neq z \neq t$. Ce sont des permutations d’éléments de $E$. Quel est le nombre de quadruplets obtenu ?
2. 1. Combien de possibilités y a-t-il pour le choix du premier élément de la permutation ?
   2. Combien de possibilités y a-t-il pour le choix du deuxième élément de la permutation ?
   3. Combien de possibilités y a-t-il pour le choix du troisième élément de la permutation ?
   4. En déduire une astuce pour avoir le nombre de permutations de $E$.

RÉSUMÉ

1- P-UPLETS AVEC RÉPÉTITION

DÉFINITION

Soit $E$ un ensemble à $n$ éléments et soit $p \in \mathbb{N}^* = \{1,2,\dots\}$. On appelle p-uplet de $E$ tout élément sous la forme $(x_1,x_2,\dots,x_p)$ tels que $x_1,x_2,\dots,x_p \in E$. Le nombre de p-uplets de $E$ est donc $n^p$.

REMARQUE

• Un p-uplet de $E$ est aussi un élément du produit cartésien $E \times E \times \dots \times E$ ($p$ fois) que l’on note encore $E^p$.
• Dans ce type de p-uplet :
  • l’ordre importe ;
  • il peut y avoir répétition.

APPLICATION 1.2.1

1. Soit $E$ un ensemble à $n$ éléments. Quel est le nombre possible d’applications de $E$ vers $E$ ?
2. Une urne contient 10 boules numérotées de 1 à 10 indiscernables au toucher. On tire successivement et avec remise 3 boules de cette urne. Quel est le nombre de tirages possibles ?
3. Les numéros d’immatriculation d’une compagnie sont composés de deux lettres suivies de 4 chiffres non nuls. Les lettres sont prises dans l’ensemble $\{A,B,C,D\}$. Quel est le nombre de numéros d’immatriculations possibles ?

2- P-ARRANGEMENT OU P-UPLETS SANS RÉPÉTITION

DÉFINITION

Soit $E$ un ensemble à $n$ éléments et soit $p \le n$. On appelle p-arrangement de $E$ ou p-uplet sans répétition, tout p-uplet de $E$ à éléments deux à deux distincts, c’est-à-dire les éléments sous la forme $(x_1,x_2,\dots,x_p)$ tels que $x_i \in E$ et $x_i \neq x_j$ pour $i \neq j$ et $1 \le i,j \le p$.

Le nombre de p-arrangements de $E$ est noté $A_n^p$ et on a :
$A_n^p = n(n-1)(n-2)\dots(n-p+1)$ (on retranche 1 jusqu’à atteindre $p$ facteurs).

EXEMPLE

$A_4^2 = 4 \times 3 = 12$

$A_{12}^4 = 12 \times 11 \times 10 \times 9$

REMARQUE

Dans le cas des arrangements :

• l’ordre importe ;
• il n’y a pas de répétition possible.

APPLICATION

1. Soit $E$ un ensemble à $n$ éléments. Quel est le nombre d’applications injectives de $E$ vers $E$ ?
2. Une urne contient 10 boules numérotées de 1 à 10. On tire au hasard, successivement et sans remise, 3 boules de cette urne. Quel est le nombre de tirages possibles ?
3. Christian et Claude font partie d’un club de 18 personnes. On veut constituer un bureau de 5 personnes à 5 fonctions (président, vice-président, secrétaire, trésorier et censeur) différentes dans cumul de fonctions.
   1. Quel est le nombre de bureaux possibles à former ?
   2. Quel est le nombre de bureaux possibles :
      1. où Christian est présent ?
      2. où Christian est trésorier ?
      3. où Christian et Claude ne sont pas présents ?
      4. où Christian et Claude ne se retrouvent pas ensemble ?

3- PERMUTATIONS

DÉFINITION

Soit $E$ un ensemble à $n$ éléments. On appelle permutation de $E$ tout $n$-arrangement de $E$. Le nombre de permutations de $E$ est noté $n!$ et vaut :

$n! = n(n-1)(n-2)\dots 2 \times 1$

PROPRIÉTÉ

• Par convention : $0! = 1$ et $1! = 1$ ;
• $n! = n(n-1)! = n(n-1)(n-2)!$ ;
• $A_n^p = \dfrac{n!}{(n-p)!}$.

EXEMPLE

• $7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$ ou $7! = 7 \times 6 \times 5!$ selon que l’on veut simplifier ou pas.
• $A_7^2 = \dfrac{7!}{(7-2)!}$
  $= \dfrac{7 \times 6 \times 5!}{5!}$
  $= 7 \times 6$
  $A_7^2 = 42$.

APPLICATION

1. Résoudre les équations suivantes dans $\mathbb{N}$ : $A_n^3 = 72n \; ; \; A_n^4 = 42A_n^2$.
2. Soit $E$ un ensemble à $n$ éléments. Quel est le nombre d’applications bijectives de $E$ vers $E$ ?
3. Quel est le nombre d’anagrammes du mot PRISEE ? (On distinguera le cas où l’on tient compte de l’accent et le cas où on n’en tient pas compte.)
4. 12 présidents doivent s’asseoir sur 12 chaises dans un restaurant.
   1. Quel est le nombre de dispositions possibles ?
   2. Quel est le nombre de dispositions si l’un des présidents a sa chaise réservée ?

Leçon 3 : p-combinaison et binôme de Newton

OBJECTIFS

À la fin de cette leçon l’élève doit être capable de :

• reconnaître une combinaison d’un ensemble ;
• dénombrer avec des combinaisons ;
• utiliser le triangle de Pascal pour développer et réduire.

SITUATION PROBLÈME

Dans une soirée rassemblant 10 personnes, chaque invité échange une poignée de mains avec chacun de ses convives. Après ces échanges, ils décident de faire un jeu de cache-cache en se séparant en plusieurs groupes.

1. Combien cela fait-il de poignées de mains ?
2. Combien cela fait-il de groupes possibles ?

ACTIVITÉ

I

Soit $E=\{1,2,3,4\}$.

1. Détermine toutes les parties de $E$ à 2 éléments. Combien y en a-t-il au total ?
2. Dans ces parties, l’ordre importe-t-il ? Y a-t-il répétition d’éléments ?
3. Calculer $A_4^2$ en utilisant les simplifications factorielles vues aux arrangements.
4. Quelle remarque faites-vous ?

II

1. Développer $(a+b)^2$ et $(a+b)^3$.
2. Calculer :
   $\displaystyle \sum_{p=0}^{2} C_2^p a^{2-p}b^p$ et $\displaystyle \sum_{p=0}^{3} C_3^p a^{3-p}b^p$.
3. Quelles remarques faites-vous ?

RÉSUMÉ

1- p-COMBINAISON

DÉFINITION

Soit $E$ un ensemble à $n$ éléments et soit $p \le n$. On appelle p-combinaison de $E$ toute partie de $E$ ayant $p$ éléments. Le nombre de p-combinaisons de $E$ est noté $C_n^p$ et on a :

$C_n^p=\dfrac{A_n^p}{p!}=\dfrac{n!}{p!(n-p)!}$.

PROPRIÉTÉ

Soit $n,p\in\mathbb{N}$ avec $p\le n$.

• $C_n^0 = 1$ et $C_n^1 = n$
• $C_n^p = C_n^{\,n-p}$

EXEMPLE

• $C_7^3=\dfrac{7!}{3!4!} =\dfrac{7\times6\times5\times4!}{3\times2\times4!} =35$.
• $C_{12}^4=\dfrac{12!}{4!8!}$.

REMARQUE

Dans le cas des combinaisons :

• l’ordre n’importe pas ;
• les éléments sont deux à deux distincts (pas de répétition).

APPLICATION

1. Résoudre les équations suivantes : $C_n^2=190$ ; $2C_n^1+6C_n^3=9n$.
2. On tire simultanément 5 cartes d’un jeu de 32 cartes. On obtient ainsi une main de 5 cartes.
   1. Dénombrer les mains possibles.
   2. Dénombrer les mains contenant :
      1. exactement deux as ;
      2. au moins un as ;
      3. l’as de pique et au moins deux trèfles ;
      4. 3 cartes d’une couleur et deux autres d’une autre.

2- BINÔME DE NEWTON

PROPRIÉTÉ

Pour développer $(a+b)^n$, avec $n\in\mathbb{N}$, on peut utiliser le binôme de Newton qui stipule que :

$(a+b)^n=\displaystyle\sum_{p=0}^{n} C_n^p\,a^{\,n-p}b^p$, les coefficients du développement étant les $C_n^p$.

On peut résumer ces coefficients à l’aide du triangle de Pascal suivant :

REMARQUE

Soit $E$ un ensemble à $n$ éléments.

• Le nombre de parties de $E$ à 0 élément est $C_n^0$.
• Le nombre de parties de $E$ à 1 élément est $C_n^1$.
• Le nombre de parties de $E$ à 2 éléments est $C_n^2$.
• Le nombre de parties de $E$ à $n-1$ éléments est $C_n^{\,n-1}$.
• Le nombre de parties de $E$ à $n$ éléments est $C_n^{\,n}$.

Ainsi, le nombre de parties de $E$ est :

$C_n^0 + C_n^1 + C_n^2 + \cdots + C_n^{n-1} + C_n^n = \displaystyle\sum_{p=0}^{n} C_n^p = \displaystyle\sum_{p=0}^{n} C_n^p (1)^p (1)^{n-p} = (1+1)^n = 2^n$.

APPLICATION

1. Quel est le nombre de parties de l’ensemble $A=\{0,1,6,8,89,45\}$ ?
2. Développer et réduire $(a-1)^5$ et $(1-3)^6$.