Nombre de parties d'un ensemble fini et permutations - Maxicours

Nombre de parties d'un ensemble fini et permutations

Objectif

Effectuer des dénombrements simples dans différentes situations.

Points clés
  • Si E est un ensemble à n éléments, alors le nombre de parties de E est 2n : card P(E) = 2n.
  • Soit E un ensemble fini de cardinal n et k un entier tel que 1  k  n. Alors le nombre de k-uplets d’éléments distincts de E est n(n – 1) × … × (n – k + 1) = .
  • Soit E un ensemble fini de cardinal n. On appelle permutation de E un n-uplet d’éléments distincts de E. Le nombre de permutations de E est n! = n × (n – 1) × … × 1.
Pour bien comprendre
  • Connaitre le vocabulaire des ensembles.
  • Calculer le cardinal d’un ensemble.
  • Connaitre les propriétés des ensembles et sous-ensembles, k-uplets.
  • Définir une épreuve de Bernoulli.
1. Nombre de parties d'un ensemble à n éléments
Soit E un ensemble et A une partie de E.
L’ensemble de toutes les parties de E est notée P(E). On a alors A  P(E).
Exemple
Soit E = {abc}. Alors {a} et {bc} sont des parties de E.
Propriété
Soit E un ensemble de cardinal n.
Alors le nombre de parties de E est 2n : card P(E) = 2n.
Démonstration

Soit E un ensemble de cardinal n : E = {x1x2, …, xn} et A une partie de E.

Chaque élément xi de E appartient ou n’appartient pas à A.
On peut donc associer à la partie A un unique n-uplet de {0 ; 1} avec la convention : le i-ème élément du n-uplet vaut 0 si xi  A et il vaut 1 si xi  A.
Par exemple, si E = {x1x2x3x4} et A = {x2, x4}, alors on associe à A le 4-uplet (0 ; 1 ; 0 ; 1).

Réciproquement, à chaque n-uplet de {0 ; 1}, on peut associer une unique partie A de E.

Il y a donc autant de parties A que de n-uplets de l’ensemble {0 ; 1} de cardinal 2.
Or le nombre de n-uplet d’un ensemble de cardinal 2 est 2n.
Donc card P(E) = 2n.

Exemple
Si on reprend l’exemple précédent avec E = {a, b, c} : card E = 3.
Alors card P(E) = 23 = 8.
On peut écrire toutes les parties de E :
P(E) = {ø, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, E}.
Applications
  1. Soit E un alphabet à 2 éléments : E = {A, B}. Un mot de longueur n est un n-uplet de E. Donc le nombre de mots de longueur n (qui aient un sens ou non) est 2n.
    Exemple : il y a 25 = 32 mots de 5 lettres.
  2. On considère une épreuve de Bernoulli : elle a deux issues ( le succès et l’échec). On répète n fois de manière identique et indépendante cette épreuve. On obtient ainsi un n-uplet de E = {, }. Alors le nombre d'issues possibles est 2n.
    Exemple : pour n = 3, on a l’arbre suivant.
    Il y a 23 = 8 issues possibles. Par exemple, et sont des issues possibles.
2. Nombre de k-uplets d'éléments distincts d'un ensemble à n éléments
Soit E un ensemble fini de cardinal n et k un entier tel que 1  k  n.
On appelle k-uplet d’éléments distincts de E tout k-uplet de E dont les éléments sont deux à deux distincts.
Exemple
Si E = {a, b, c, d}, alors card E = 4.
Un triplet d’éléments distincts de E est par exemple (d, c, a).
En revanche, (c, c, a) est un triplet de E, mais n’est pas un triplet d’éléments distincts de E.
Remarque
Une k-liste de E de cardinal n peut contenir plus de n éléments mais une k-liste d’éléments distincts de E ne peut pas contenir plus de n éléments. D’où la condition 1 k n.
Propriété
Soit E un ensemble fini de cardinal n et k un entier tel que 1  k  n.
Alors le nombre de k-uplets d’éléments distincts de E est :
n × (n  1) × … × (n  k + 1).
Démonstration

Soit (x1x2, …, xk) un k-uplet d’éléments distincts de E : c’est un élément du produit cartésien E1 × E2 × … × Ek.

On a n choix possibles pour x1 : card E1 = n.
Puis, ce choix étant fait, il reste (n  1) choix possibles pour x2 : card E2 n – 1.

Il y a (n k + 1) choix possibles pour xk : card Ek n – k + 1.
Alors, d’après la propriété du produit cartésien :
card(E1 × E2 × … × En= card E1 × card E2 × … × card En
card(E1 × E2 × … × Enn × (n + 1) × … × (n – k + 1)

Exemple fondamental à connaitre : Tirage successif sans remise
Une urne contient 10 boules numérotées de 1 à 10.
On tire successivement et sans remise 5 boules de l’urne.
Cela signifie qu’on tire la première boule et on note son numéro (par exemple 2), puis on ne la remet pas dans l’urne. On tire ensuite la deuxième boule et on regarde son numéro (par exemple 9) et ainsi de suite.
Un tirage possible est par exemple (2 ; 9 ; 6 ; 3 ; 1) : c’est un 5-uplet d’éléments distincts de E où E est constitué des 10 boules (n = 10).
Le nombre de tirages possibles est donc 10 × 9 × 8 × 7 × 6 = 30 240.
3. Permutations
Soit E un ensemble fini de cardinal n. On appelle permutation de E un n-uplet d’éléments distincts de E.
Exemple
Si E = {a, b, c, d}.
Une permutation de E est par exemple (b, d, c, a) ou (d, a, b, c).
En revanche, (d, c, c, a) n’est pas une permutation de E car le 4-uplet contient deux éléments identiques.
Propriété
Soit E un ensemble fini de cardinal n.
Alors le nombre de permutations de E est n × (n  1) × … × 1.
On le note n! = n(n – 1) × … × 1.
Démonstration

La démonstration découle directement de la propriété des k-uplets d’éléments distincts.

Remarques
n! se lit « factorielle n ».
Avec cette notation factorielle, le nombre de k-uplets d’éléments distincts de E est :
n(n – 1) × … × (n – k + 1) =
Exemple : Tirage successif sans remise
Une urne contient 10 boules numérotées de 1 à 10.
On tire successivement et sans remise les 10 boules de l’urne.
Le nombre de tirages possibles est donc 10! = 3 628 800.

Vous avez déjà mis une note à ce cours.

Découvrez les autres cours offerts par Maxicours !

Découvrez Maxicours

Comment as-tu trouvé ce cours ?

Évalue ce cours !

 

Des profs en ligne

quote blanc icon

Découvrez Maxicours

Exerce toi en t’abonnant

Des profs en ligne

  • 6j/7 de 17 h à 20 h
  • Par chat, audio, vidéo
  • Sur les matières principales

Des ressources riches

  • Fiches, vidéos de cours
  • Exercices & corrigés
  • Modules de révisions Bac et Brevet

Des outils ludiques

  • Coach virtuel
  • Quiz interactifs
  • Planning de révision

Des tableaux de bord

  • Suivi de la progression
  • Score d’assiduité
  • Un compte Parent