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.

  1. est un ensemble fini et card =

  2. Si , il comporte zéro élément et card

  3. 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).

    tikzpicture-1

  • L’ensemble des éléments qui appartiennent à ou à est appelé réunion de et ; noté (lire A union B).

    tikzpicture-2

Exemple 7. Considérons les ensembles suivants: .

On a , .

tikzpicture-3

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

tikzpicture-4

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 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)

tikzpicture-5

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

  1. De combien de façons peut-on constituer ce groupe de 5 personnes ?

  2. De combien de façons peut-on constituer ce groupe avec uniquement des hommes ?

  3. 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:

  1. contenant des boules de la même couleur?

  2. contenant des boules de couleurs deux à deux distinctes?

  3. 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.

  1. 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 .

  2. 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 .

  3. 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:

  1. contenant des boules de même couleur?

  2. contenant des boules de couleurs deux à deux distinctes?

  3. 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.

  1. 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 .

  2. 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 .

  3. 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:

  1. contenant des boules de même couleur?

  2. contenant des boules de couleurs deux à deux distinctes?

  3. 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.

  1. 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.

  2. 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 donc

  3. Nombre 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

 ◻