2 Dénombrement (TS2)
Dénombrement (TS2)
algebra
Ensemble fini - Cardinal
Définition 1. Soit
Lorsqu’un ensemble a
éléments, on dit que est un ensemble fini et son
cardinal est On note alors cardE = .
Exemple 2.
est un ensemble fini et cardE =
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.
Parties d’un ensemble fini
est une partie ou sous-ensemble de si tout élément de est élément de
On note (lire inclus dans ). Donc cardA cardE.L’ensemble constitué par toutes les parties de se note
Remarque 4. 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.
Théorème 5. Admis Le nombre de parties d’un ensemble à éléments est
Exemple 6.
Donc nous avons recensé ( dénombré) 8 éléments pour .
La formule du théorème est vérifiée car ,
d’où card
Exercice 7. On dispose de quatre pièces de monnaie: une de 100F, une de 200F, une de 250F et une de 500F.
Réponse
Soit l’ensemble des quatre pièces;
A chaque partie de correspond une somme d’argent
égale à la somme des éléments de cette partie. Il y a donc autant de
sommes que de parties de
Or card
Donc il y a en tout 16 sommes ( théoriques) possibles.
Intersection et réunion
Soient et deux parties de
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).
Remarque 8. est l’ensemble des éléments qui appartiennent au
moins à A ou B.
Lorsque ou n’ont aucun élément en commun, on dit qu’ils sont
disjoints. Dans cas est l’ensemble des
éléments qui appartiennent à A ou bien à B.
Théorème 9.
Exercice 10. Dans une classe de 30 élèves, 19 font espagnol, 18 font arabe comme deuxième langue facultative. Sachant que tous les élèves étudient au moins l’une deux langues. Déterminer le nombre d’élèves qui étudient les deux langues à la fois.
Réponse
Soit l’ensemble des élèves qui étudient l’espagnol
et celui de ceux qui font arabe. l’ensemble des
élèves qui étudient les deux langues à la fois est soit son cardinal. Donc on trouve
Complémentaire
Soit une partie de
Le complémentaire de dans ,
noté , est l’ensemble des éléments de
qui ne sont pas dans
Exemple 11. Si alors
Remarque 12.
Soit l’ensemble << obtenir au moins éléments >> alors est l’ensemble << obtenir au plus éléments >>
Si l’ensemble << avoir au moins un >> alors est l’ensemble << n’avoir aucun >>
Cardinal du complémentaire
Soient et deux parties
non disjointes de .
On note et respectivement les complémentaires de et .
Exercice 13. Dans un camp de vacances hébergeant 80 personnes. 50 font la natation, 33 pratiquent le tennis, 14 pratiquent les deux sports à la fois. Calculer:
Le nombre de personnes qui pratiquent uniquement la natation;
Le nombre de personnes qui ne pratiquent aucun sport.
Le nombre de personnes qui pratiquent au moins l’un des deux sports.
Le nombre de personnes qui pratiquent la natation ou bien le tennis.
Réponse
et sont respectivement
ensembles de ceux qui font natation et tennis.
Une fois le tableau réussi, on obtient les réponses suivantes:
card
card
card card card card
card card
Propriétés classiques
Soient , et trois parties d’un ensemble finis .
Produit cartésien
Définition 14 (Cas de deux ensembles). Soient et deux ensembles finis non
vides.
On appelle produit cartésien par , noté , l’ensemble des
couples où et
Exemple 15. Prenons et
Cardinal du produit cartésien
Il y a 2 choix possibles ou pour écrire le premier terme du couple.
Maintenant pour chacun de ces choix, il y a 3 choix possibles pour écrire le deuxième terme du couple.
On en conclut qu’il y a couples possibles; c’est à dire card. card soit 8.
Théorème 16.
Remarque 17. mais card card
Généralisation
Cette définition s’étend à un nombre quelconque d’ensembles finis: le produit cartésien des ensembles est l’ensemble noté
.Le produit cartésien est noté .
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 sont appelés p-uplets.
card cardcardcardcard
Pour tout ensemble a éléments card.
Exercice 18.
On lance simultanément un jeton de 10F ( ses faces sont notées Pile et Face) et un dé à quatre faces numérotées de 1 à 4. Quels sont les résultats possibles? Combien sont-ils?
Combien de mots de quatre lettres distinctes ou non peut-on constituer avec l’alphabet?
Réponse
Posons et
A l’apparition de la face Pile (P) il y aura 4 numéros possibles à lui associer et à l’ apparition de la face Face (F) il y aura 4 numéros possibles à lui associer Les résultats possibles sont: ce sont donc les éléments du produit cartésien .
D’où il y a card résultats possibles.Notons l’ensemble des 26 lettres de l’alphabet.
La 1 lettre est un élément de ; la 2 lettre est un élément de ; la 3 lettre est un élément de et la 4 lettre est un élément de donc un mot est un 4-uplet d’éléments de : donc il y a cardmots possibles.
Conséquence 19. le principe multiplicatif Si une situation comporte étapes successives offrant chacune possibilité( ou choix) alors le nombre total de possibilités est:
Exemple 20. Un homme pour se rendre à un mariage doit choisir une chemise, un pantalon et une veste. Sachant qu’il possède 5 chemises, 2 vestes et 4 pantalons, de combien de façons peut-il effectuer son choix?
Réponse
Il a 5 possibilités pour choisir la chemise, 2 possibilités pour choisir
la veste et 4 possibilités pour choisir le pantalon.D’après le principe
multiplicatif il a choix .
Partition d’un ensemble
Définition 21. Soient des parties non vides de On dit qu’elles forment une partition de si:
ils sont deux à deux disjointes
et
Exemple 22. 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é 23. Soit un ensemble
fini et des ensembles
formant une partition de
On a card cardcardcardcard
Exercice 24. Combien de nombres peut-on former avec des chiffres distincts choisis parmi les éléments de ?
Réponse
On peut écrire des nombres de 1, 2, 3, 4, 5 chiffres.
On désignent respectivement par les ensembles ’ distincts deux à deux) de ces nombres
et par la réunion de ces cinq ensembles.
On a cardcardcardcardcard
Donc card
Remarque 25. 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 en sembles de la partition.
Propriété 26. Nous retrouvons la formule suivante, déjà rencontrée.
Car et forment une partition de
Conséquence 27. le principe additif Si une situation offre choix comportant chacun possibilités alors le nombre de choix possibles est :
Exemple 28. On veut choisir deux personnes de nationalités différentes parmi 5 camerounais, 10 malgaches et 6 sénégalais. Combien y a t-il de possibilité?
Réponse
Les deux personnes peuvent être choisies:
l’une camerounaise et l’autre malgache: le nombre de choix est égal à
ou l’une camerounaise et l’autre sénégalaise: le principe additif égal à
ou l’une malgache et l’autre sénégalaise: le nombre de choix est égal à
D’après le principe additif, le nombre de choix possibles est
p-listes
Définition 29. Soit un
ensemble à éléments et un
entier naturel non nul.
On appelle ou de
tout élément de
Exemple 30. 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).
Autre formulation de la définition
Une , est liste de
éléments choisis parmi les éléments de ordonnés et non nécessairement
distincts.
Dans une , 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 31. Le nombre de 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 .
Exercice 32. 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?
Réponse
Un résultat d’un tirage peut se représenter par un triplet où désigne le numéro de la 1 boule, celui de la 2 boule,
celui de la 3.
Donc un résultat est une de l’ensemble des
15 numéros, le nombr de tirages possibles est
Conseil
Dans toute situation où on l’on choisit successivement avec remise éléments parmi éléments, on
applique la formule des pour déterminer le
nombre de choix possibles.
Remarque 33 (Nombre d’applications). est le nombre d’applications d’un ensemble de départ à p éléments vers un ensemble d’arrivée à n éléments.
Exemple 34. On veut ranger 15 livres dans un
bibliothèque comportant 3 étagères.
C’est le nombre d"applications de l’ensemble des livres vers l’ensemble
d’arrivée des étagères; donc il y a
Arrangements
Définition 35. Soit un
ensemble à éléments et un
entier naturel non nul tel que .
On appelle arrangement de éléments de toute d’éléments de deux à deux distincts.
Autre formulation de la définition
Un arrangement de éléments de , est 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.
Théorème 36. Le nombre d’arrangements de éléments d’un ensemble à éléments, noté est tel que :
Démonstration
Pour déterminer le nombre d’arrangements de
éléments d’un ensemble à éléments, on peut
utiliser un arbre de choix à niveaux.
Il y a choix possibles pour le 1 élément.
Il y a choix possibles pour le 2 élément.
Il y a choix possibles pour le 3 élément.
.....................................................................
Il y a choix possibles pour le p élément
.
D’après le principe multiplicatif, il y a arrangements de éléments de .
Exemple 37. Dix
athlètes participent à une course. On appelle podium l’arrivée des trois
premiers.
On se propose de déterminer le nombre le nombre de podium possibles, en
supposant qu’il n’y a pas d’ex æquo.
Il y a autant de podiums que d’arrangements de trois athlètes pris parmi
10, c’est à dire . On a :
Une urne contient 10 boules numérotées de
1 à 10. On en tire quatre successivement sans remettre les boules
tirées. Combien y a t-il de tirages possibles?
Chaque tirage correspond à un arrangement de 4 éléments de l’ensemble
des 10 boules.
Il y a donc
Remarque 38. Si , il est impossible de faire des arrangements.
Conseil: 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.
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
Permutations
Définition 41. Soit un
ensemble à éléments.
On appelle permutation de un arrangement des éléments de
Une permutation est un arrangement particulier; donc c’est un choix
successif sans remise de éléments parmi les éléments de
Propriété 42. Le nombre de permutations d’un ensemble à éléments est
Exemple 43. 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
Propriété 44. Le nombre de bijections d’un ensemble à éléments vers un ensemble à éléments est égal à
Exemple 45. Il existe façons de placer 6 personnes autour d’une table ronde dont les places sont numérotées de 1 a 6.
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 nombres de permutations des lettres du mot.
Les anagrammes du nombre 123 sont: 123, 321, 213, 132, 231, 312.
Il y en a C’est le nombres de permutations des chiffres du nombre.
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
Les anagrammes du nombre 12322 sont au nombre de
Régle
NB
Les anagrammes sont très importantes pour déterminer le nombre de
positions des objets dans les tirages successifs.
Combinaisons
Définition 48. E étant un ensemble non vide de éléments, un nombre entier
naturel tel que
On appelle combinaison de éléments de toute partie de ayant éléments.
Exemple 49. Considérons l’ensemble
Donnons toutes les combinaisons à trois éléments de de
Comptage: ,
, ,, , , , , , .
Il y a 10 combinaisons de 3 éléments de On note
par ce nombre.
Remarque 50. Dans une combinaison, on ne tient pas compte de l’ordre des éléments et il n’y a pas de répétition.
Nombre de combinaisons
Désignons par le nombre de toutes les
combinaisons à éléments de
et calculons
Chaque partie à éléments de
permet de réaliser permutations.
Or chaque permutation obtenue est un arrangement à
éléments de .
Le nombre d’arrangements à éléments de est donc égal au nombre de combinaisons à éléments de multiplié par
Par conséquent:
Propriété 51. et sont des nombre entiers naturels tels que :
est un ensemble à
éléments.
Le nombre de combinaisons à éléments de est :
Notation 52.
On montre de même que :
Exercice 53. On tire simultanément cinq jetons dans un sac contenant huit jetons. Combien y a t-il de tirages possibles?
Réponse
Les jetons étant tirés en même temps donc il n’ y a ni d’ordre ni
répétition des jetons. Un tirage peut être donc modélisé par une
combinaison 5 éléments dans un ensemble contenant 8 éléments.
Donc il y a tirages possibles.
Calculons
Autre façons
Conseil
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.
Principes du dénombrement
Pour calculer le cardinal d’un ensemble on peut utiliser : le
comptage, les diagrammes, les arbres.
On peut aussi utiliser trois outils fondamentaux: p-listes,
arrangements, combinaisons. Comme on le verra, chacune de ces notions
peut être modélisée par une situation fréquemment
rencontrée dans les problèmes de dénombrement: le tirage de éléments dans un ensemble contenant éléments.
Dans tous les cas devant un problème de dénombrement, on doit se poser
les questions suivantes:
nombre d’objets dans lesquels on tire, on
choisit etc...
le nombre d’objets à choisir ou quelques fois le
nombre de tirages.
Pour dénombrer un ensemble , on peut utiliser: le comptage, un
diagramme, un arbre de choix, un tableau à double entrée.
On peut aussi utiliser les trois outils fondamentaux: p-listes,
arrangements, combinaisons.
Chacun de ces outils modélise une situation fréquente dans les problèmes
de dénombrement: le tirage (ou choix) de éléments
dans un ensemble contenant éléments.
nombre d’objets dans lesquels on tire, on
choisit etc...
le nombre d’objets à choisir ou quelques fois le
nombre de tirages.
Les et sont
des entiers naturels qu’on peut calculer à l’aide de la
calculatrice.
Pour calculer , on saisit
Pour calculer , on saisit
Dans tous les cas devant un problème de dénombrement, on peut
utiliser le tableau suivant:
Tirage de éléments dans un ensemble à éléments.