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:

  1. Le nombre de personnes qui pratiquent uniquement la natation;

  2. Le nombre de personnes qui ne pratiquent aucun sport.

  3. Le nombre de personnes qui pratiquent au moins l’un des deux sports.

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

  1. card

  2. card

  3. card card card card

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

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

  2. Combien de mots de quatre lettres distinctes ou non peut-on constituer avec l’alphabet?

Réponse

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

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