27 Dénombrement
Dénombrement
analysis
Combien
peut-on attribuer de numéros de téléphones portables (numéros à 9
chiffres commençant par 77)?
Huit athlètes
prennent le départ d’une course. Combien y a-t-il d’arrivées
possibles?
Combien y a-t-il
de façons de sélectionner une équipe de 11 joueurs parmi les 22 membres
d’un club?
Ces questions constituent des exemples simples de problèmes de
dénombrement.
L’objet de ce chapitre est de mettre en place des outils pour les
résoudre.
Signalons que le dénombrement est particulièrement utile en
probabilité.
Ensemble fini - Cardinal
Définition 1. Soit un entier
naturel.
Lorsqu’un ensemble a
éléments, on dit que est un ensemble fini de
cardinal
On note alors card = .
Exemple 2.
est un ensemble fini et card =
Si , il comporte zéro élément et card
Certains ensembles ne sont pas finis tels que , ,
Remarque 3. Résoudre un problème de dénombrement consiste
généralement à déterminer le cardinal d’un ensemble fini E. Le problème
se pose en général lorsque E est donné en compréhension, c’est-à-dire
par une description de ses éléments.
L’objet de ce qui suit est de trouver des méthodes simples pour calculer
des cardinaux d’ensembles finis.
Définition 4. Soient et deux ensembles finis.
est une partie ou un sous-ensemble de si tout élément de est élément de On note (lire inclus dans ). Donc card card.
L’ensemble constitué par toutes les parties de se note .
Remarque 5. L’ensemble est une partie
de lui-même et l’ensemble vide est une
partie de tout ensemble (c’est une convention!)
est la partie pleine et la partie vide.
Intersection et réunion
Soient et deux parties d’un ensemble
Définition 6.
L’ensemble des éléments communs à et est appelé intersection de et ; noté (lire A inter B).
L’ensemble des éléments qui appartiennent à ou à est appelé réunion de et ; noté (lire A union B).
Exemple 7. Considérons les ensembles suivants: .
On a , .
Remarque 8. est l’ensemble des éléments qui appartiennent au
moins à A ou B.
Lorsque et n’ont aucun élément en commun, on dit qu’ils sont
disjoints; donc on a: Dans ce cas est
l’ensemble des éléments qui appartiennent à A ou bien à
B.
Propriété 9.
Exercice 10. Dans une classe de 30 élèves, 19 élèves font espagnol, 18 élèves font arabe comme deuxième langue facultative. Sachant que tous les élèves étudient au moins l’une des deux langues. Détermine le nombre d’élèves qui étudient les deux langues à la fois.
Solution. Soit l’ensemble des élèves qui
étudient l’espagnol et celui de ceux qui font
arabe donc l’ensemble des élèves qui étudient les deux langues à la fois
est Soit son
cardinal.
est l’ensemble des élèves de la classe
d’effectif
On trouve c’est à dire 7 élèves étudient les
deux langues à la fois. ◻
Remarque 11. Pour le cas de trois ensembles, il est conseillé de s’aider de diagrammes.
Complémentaire
Soit une partie d’un ensemble
Définition 12. Le complémentaire de dans , noté , est l’ensemble des éléments de qui ne sont pas dans
Exemple 13.
Si alors
Propriété 14 (Cardinal du complémentaire).
Parfois, il sera plus simple dans un exercice où l’on a les locutions << au moins >> ou << au plus>>, de dénombrer le complémentaire de A dans un ensemble E connu et d’utiliser l’égalité précédente.
Produit cartésien
Définition 15 (Cas de deux ensembles). Soient et deux ensembles finis non
vides.
On appelle produit cartésien de par , noté (lire croix ), l’ensemble des couples
où et
Exemple 16. Prenons et
On a alors
Cardinal du produit cartésien
Considérons toujours les deux ensembles : et
On a
Un élément de est dans
couples alors les éléments de seront dans
couples.
Donc card
D’une manière générale:
Théorème 17.
Remarque 18. Lorsque on a car un couple est
ordonné
Par contre card card quels que soient et
Cette définition s’étend à un nombre quelconque d’ensembles finis: le produit cartésien de trois ensembles finis A, B et C est l’ensemble noté ABC et card( ABC) =cardA.cardB.cardC.
Les éléments du produit cartésien de deux ensembles sont appelés couples; les éléments du produit cartésien de trois ensembles sont appelés triplets; les éléments du produit cartésien de ensembles sont appelés p-uplets ( .
Conséquence 19 (Le principe multiplicatif). Pour
dénombrer un ensemble, on peut utiliser le principe suivant:
Si une situation comporte étapes successives
offrant chacune possibilités (ou choix) alors
le nombre total de possibilités d’effectuer cette situation dans l’ordre
indiqué des étapes est :
Exemple 20. Le menu d’un restaurant propose un certain jour pour le repas de midi 3 entrées, 4 plats de résistance et 2 desserts. De combien de façons un client peut-il composer son menu ce jour-là ?
Le choix d’un menu est une situation qui comporte 3 étapes :
choix d’une entrée : 3 possibilités
choix d’un plat de résistance : 4 possibilités
choix d’un dessert : 2 possibilités.
D’après le principe multiplicatif, le nombre total de choix possibles
est : menus.
Exercice 21. Un homme, pour se rendre à un mariage doit choisir la veste, la chemise et un pantalon. Sachant qu’il dispose de 2 vestes, 4 pantalons et 3 chemises, de combien de façons peut-il effectuer son choix?
A retenir
Dans une situation de dénombrement, lorsque les différentes étapes sont
liées par la conjonction de coordination << et>> alors il
faut faire une multiplication.
Partition d’un ensemble
Définition 22. Soient des parties non vides d’un ensemble fini On dit qu’elles forment une partition de si:
elles sont deux à deux disjointes
et (leur réunion donne E)
Exemple 23. Soit l’ensemble tel que
les ensembles forment une partition de
les ensembles ne forment pas une partition de car ils ne sont pas disjoints deux à deux.
Propriété 24. Soit un ensemble fini et des ensembles formant une partition de
Cette propriété est appelée principe additif (Nous
l’admettons).
Pour résoudre un problème de dénombrement, il peut-être utile
d’effectuer une partition de l’ensemble à dénombrer. Le cardinal de cet
ensemble est alors la somme des cardinaux des ensembles de la
partition.
Remarque 25. et forment une partition de donc nous retrouvons la formule suivante:
Autre formulation du principe additif
Si une situation offre choix comportant chacun possibilités alors le nombre de choix possibles est :
Exemple 26. Pour aller en ville, une personne
dispose de 3 vélos, 2 motos et 4 bus.
Déterminer le nombre de possibilités de cette personne pour accéder en
ville.
La personne prend un vélo ( avec 3 possibilités) ou une moto ( avec 2 possibilités) ou un bus ( avec 4 possibilités) donc d’après le principe additif, le nombre de possibilités est
NB: Lorsque le raisonnement amène ou ou ou bien alors il faut faire une addition.
Notion de p-listes
Définition 27. Soit un
ensemble à éléments et un
entier naturel non nul.
Une p-liste, est une liste de éléments ordonnés et
non nécessairement distincts choisis parmi les
éléments de .
Exemple 28. sont des 3-listes de
l’ensemble .
est une 10-liste de
l’ensemble : il correspond, par
exemple, à un résultat de 10 lancers consécutifs d’une pièce de monnaie
(pile ou face).
Remarque 29. Dans une p-liste, on tient compte de l’ordre des éléments de la liste et un élément choisi peut être répété plusieurs fois dans la liste.
Théorème 30. Le nombre de p-listes d’un ensemble à éléments est
Démonstration
Il y a choix possibles pour le 1 élément de la
liste.
Il y a choix possibles pour le 2 élément de la
liste.
Il y a choix pour le 3 élément de la liste.
.......................................................................................
Il y a choix possibles pour le p élément de la
liste.
D’après le principe multiplicatif, on a .
Exemple 31. Une urne contient 15 boules numérotées
de 1 à 15. On en tire trois successivement en remettant à chaque fois la
boule tirée. Combien y a t-il de tirages possibles?
Soit E l’ensemble des 15 boules.
Les boules tirées sont ordonnées puisqu’on les tire l’une après l’autre
; elles ne sont pas nécessairement distinctes puisqu’on remet la boule
tirée dans l’urne après chaque tirage.
Donc un tirage est une 3-liste de l’ensemble E: le nombre de tirages
possibles est
Méthode
Dans toute situation où l’on choisit successivement avec remise éléments parmi éléments, on applique la formule des p-listes pour déterminer le nombre de choix possibles.
NB
Dans une p-liste , p peut-être supérieur à n.
Arrangements
Définition 32. Soit un
ensemble à éléments et un
entier naturel non nul tel que .
On appelle arrangement de éléments de toute p-liste d’éléments de deux à deux distincts.
Un arrangement de éléments de , est une liste de éléments
choisis parmi les éléments de ordonnés et deux à deux distincts.
Donc dans un arrangement, on tient compte de l’ordre des éléments de la
liste et chaque élément de la liste est écrit une et une seule fois (pas
de répétition).
Nombre d’arrangements
Considérons l’exemple suivant.
Exemple 33. Dix athlètes participent à une course.
On appelle podium l’arrivée des trois premiers.
On se propose de déterminer le nombre de podiums possibles, en supposant
qu’il n’y a pas d’ex æquo.
Dans un podium les 3 athlètes sont << ordonnés >> et ne
peuvent se << répéter>>. Chaque podium correspond donc à un
arrangement de trois athlètes pris parmi 10 athlètes . Donc il y a
autant de podiums que d’arrangements de trois athlètes pris parmi
10.
Déterminons le nombre de ces arrangements de
athlètes pris parmi 10.
Il y a choix possibles pour la 1 place .
Il y a choix possibles pour la 2 place.
Il y a choix possibles pour la 3 place.
D’après le principe multiplicatif, il y a arrangements de éléments de
l’ensemble à 10 éléments. Soit 720 podiums.
D’une manière générale:
Théorème 34. Le nombre d’arrangements de éléments d’un ensemble à éléments, noté , est tel que :
Exemple 35.
Exercice 36. Une urne contient 11 boules numérotées de 1 à 11. On en tire quatre successivement sans remettre à chaque fois la boule tirée. Combien y a -t-il de tirages possibles?
Solution. Le mot << successivement >> suggère que
l’ordre de tirage des boules est important et il n’y peut avoir de
répétition car la boule tirée n’est pas remise dans l’urne. Chaque
tirage correspond donc à un arrangement de 4 éléments de l’ensemble des
10 boules.
Il y a donc ◻
Remarque 37. Si , il est impossible de faire des arrangements.
Dans toute situation où l’on effectue un choix de manière successive sans remise (élection de bureau avec postes, course et ordre d’arrivée...), on applique la formule des arrangements.
Exercice 38. L’association de 20 membres souhaite élire
le président,
le secrétaire et
le trésorier
Combien y-a-t-il de possibilités d’avoir ces trois responsables
Notation factorielle
Pour un nombre entier naturel non nul, le produit est appelé factorielle
n et est noté
Par convention
Exemple 39.
Propriété 40. Soit
et deux nombres entiers
naturels non nuls tels que : . On a
Par convention
Exemple 41.
Permutations
Définition 42. Soit un
ensemble à éléments.
On appelle permutation de un
arrangement des éléments de
Une permutation est un arrangement particulier (où ; donc c’est un choix successif sans remise de éléments parmi les éléments de
Propriété 43. Le nombre de permutations d’un ensemble à éléments est .
On a aussi
Exemple 44. Le nombre de façons de placer 6 personnes autour d’une table ronde dont les places sont numérotées de 1 a 6 est égal à . Soit (c’est le nombre de façons de permuter les 6 personnes autour de la table)
Exemple 45. Un parieur a sélectionné trois chevaux
avec lesquels il veut composer son tiercé. De combien de façons
dispose-t-il pour les classer dans l’ordre?
Réponse: le nombre de façons est (c’est le nombre de façons de permuter les trois
chevaux)
Notion d’Anagramme
Définition 46. On appelle une anagramme d’un mot (resp. d’un nombre), tout mot (resp. tout nombre) obtenu à partir de toutes les lettres (resp. tous les chiffres) de ce mot (resp. de ce nombre).
Exemple 47.
Les anagrammes du mot BAC sont: CAB, BCA, BAC, CBA, ABC, ACB.
Il y en a c’est le nombre de permutations des lettres du mot BAC.
Les anagrammes du nombre 123 sont: 123, 321, 213, 132, 231, 312.
Il y en a c’est le nombre de permutations des chiffres du nombre 123.
Les anagrammes du mot EVE sont: VEE, EVE, EEV .
Il y en a . La lettre E se répète 2 fois, donc on a divisé par
Les anagrammes du mot DENOMBREMENT sont au nombre de
La lettre E se répète 3 fois, les lettres M et N se répètent 2 fois donc on divise par
Les anagrammes du nombre 12322 sont au nombre de
NB: Les anagrammes nous permettent de déterminer le nombre de positions des objets dans les tirages successifs.
Combinaisons
Définition 48. E étant un ensemble non vide à éléments, un nombre entier
naturel tel que
On appelle combinaison de éléments de toute partie de
ayant éléments.
On dit aussi combinaison de éléments parmi éléments.
Exemple 49. Considérons l’ensemble
Donnons toutes les combinaisons à trois éléments de
Faisons le comptage: , , ,, , , , , , .
Il y a 10 combinaisons de 3 éléments pris parmi 6 éléments. On note par
ce nombre c’est-à-dire .
Remarque 50. Dans une combinaison, on ne tient pas compte de l’ordre des éléments et il n’y a pas possibilité de répétition des éléments.
Nombre de combinaisons
On note par le nombre de toutes les
combinaisons à éléments d’ensemble à éléments.
Donnons des exemples de calcul de .
Exemples et
On utilise aussi la formule suivante que nous admettons.
Exercice 51. On tire simultanément deux jetons dans
un sac contenant sept jetons numérotés.
Combien y a -t-il de tirages possibles?
Solution. Les jetons étant tirés en même temps (en vrac!) donc
il n’y a ni ordre ni répétition des 2 jetons tirés. Un tirage peut être
donc modélisé par une combinaison de 2 éléments dans un ensemble
contenant 7 éléments. Donc il y a tirages
possibles.
Calculons
Autre façon ◻
Remarque 52. Dans une situation où l’on effectue un choix sans ordre ni répétition (cas d’un tirage simultané), on utilise la formule des combinaisons.
Exercice 53. On constitue un groupe de 5 personnes choisies parmi 12 femmes et 10 hommes
De combien de façons peut-on constituer ce groupe de 5 personnes ?
De combien de façons peut-on constituer ce groupe avec uniquement des hommes ?
De combien de façons peut-on constituer ce groupe avec des personnes de même sexe?
Quelques exercices classiques
Exercice 54. Une urne contient 3 boules bleues, 4 boules rouges et 2 boules vertes. Les boules sont supposées indiscernables au toucher.
On tire simultanément trois boules de l’urne.
Combien y a- t-il de tirages possibles:
contenant des boules de la même couleur?
contenant des boules de couleurs deux à deux distinctes?
contenant deux boules rouges et une boule verte?
Solution. Tirage simultané de trois boules parmi 9.
Les boules sont tirées en même temps donc il n’y a ni ordre ni répétition des 3 boules tirées.
Un tirage correspond donc à une combinaison de 3 éléments dans un ensemble contenant 9 éléments.
On utilise l’outil des combinaisons: donc il y a tirages possibles.
Nombre de tirages contenant des boules de même couleur.
Les trois boules tirées sont bleues ou bien sont rouges.
Le nombre de tirages est donc .
Nombre de tirages contenant des boules de couleurs deux à deux distinctes (ou nombre de tirages tirage tricolore).
Un tirage ici est un élément du produit cartésien de trois ensembles: l’un constitué d’une boule bleue prise parmi 3 bleues et l’autre constitué d’une boule rouge prise parmi 4 rouges et le dernier d’une boule verte prise parmi 2 vertes.
Le nombre de tirages est donc .
Nombre de tirages contenant deux rouges et une verte.
Un tirage ici est un élément du produit cartésien de deux ensembles: l’un constitué de 2 boules rouges prises parmi 4 et l’autre constitué d’une boule verte prise parmi 2.
Le nombre de tirages est donc .
◻
Exercice 55. Une urne contient 3 boules bleues, 4 boules rouges et 2 boules vertes. Les boules sont supposées indiscernables au toucher. On tire successivement avec remise trois boules de l’urne. Combien y a- t-il de tirages:
contenant des boules de même couleur?
contenant des boules de couleurs deux à deux distinctes?
contenant deux boules rouges et une boule verte?
Solution. Correction
On tire successivement avec remise trois boules de l’urne.
On utilise l’outil des p-listes: donc il y a tirages possibles.
Nombre de tirages contenant des boules de même couleur.
Les trois boules tirées sont bleues ou bien sont rouges ou bien sont vertes.
Le nombre de tirages est donc .Nombre de tirages contenant des boules de couleurs deux à deux distinctes.
Par exemple la première boule tirée est bleue prise parmi 3, suivie d’une deuxième boule rouge prise parmi 4, suivie d’une troisième boule verte prise parmi 2: donc il y a tirages ayant la configuration BRV. On obtient tous les tirages tricolores possibles en multipliant ce résultat par le nombre d’anagrammes du mot BRV.
Le nombre de tirages est donc .Nombre de tirages contenant deux boules rouges et une boule verte.
Par exemple on tire 2 boules rouges prises parmi 4 suivies d’une boule verte prise parmi 2: donc il y a tirages ayant la configuration RRV. Puis on obtient tous les tirages possibles comportant deux boules rouges et une boule verte en multipliant ce résultat par le nombre d’anagrammes du mot RRV.
Le nombre de tirages est donc .
◻
Exercice 56. Une urne contient 3 boules bleues, 4
boules rouges et 2 boules vertes. Les boules sont supposées
indiscernables au toucher.
On tire successivement sans remise trois boules de l’urne.
Combien y a- t-il de tirages:
contenant des boules de même couleur?
contenant des boules de couleurs deux à deux distinctes?
contenant deux boules rouges et une boule verte?
Solution. On tire successivement sans remise trois boules de l’urne.
On utilise l’outil des arrangements: donc il y a tirages possibles.
Nombre de tirages contenant des boules de même couleur.
Les trois boules tirées sont bleues ou bien sont rouges.
Le nombre de tirages est donc tirages possibles.Nombre de tirages contenant des boules de couleurs deux à deux distinctes.
Par exemple la première boule est bleue prise parmi 3, suivie d’une deuxième boule rouge prise parmi 4, suivie d’une troisième boule verte prise parmi 2: donc il y a tirages ayant la configuration BRV. On obtient tous les tirages tricolores possibles en multipliant ce résultat par le nombre d’anagrammes du mot BRV.
Le nombre de tirages est doncNombre de tirages contenant deux rouges et une verte.
Par exemple 2 boules rouges prises parmi 4 suivies d’une boule verte prise parmi 2: donc il y a tirages ayant la configuration RRV. Puis on obtient tous les tirages possibles comportant deux boules rouges et une boule verte en multipliant ce résultat par le nombre d’anagrammes du mot RRV.
Le nombre de tirages est donc
◻