Définition
Soit
un entier naturel non nul. Soit\(k\)ensembles non vides
.
• Toute liste ordonnée
, avec \(x_i \in E_i\)pour
allant de
à
, est appelée
(ou
-liste).
• L'ensemble de ces
-upletsest donc le produit cartésien
.
Remarques
• Un 2-uplet est uncouple.
• Un 3-uplet est untriplet.
• Soit
un ensemble non vide fini de cardinal
n
. Soit
k
un entier compris entre
et
. Un
-upletd'éléments de
est un élément de
.
Exemple
Soit
un ensemble à trois éléments. On peut former des listesd'éléments de\(E\):
• des
-uplets, c'est-à-dire des couples :
, etc.
• des
-uplets, c'est-à-dire des triplets :
, etc.
• des
-uplets :
, etc.
Remarque
Pour faciliter les notations, on peut remplacer ces
-uplets par des « mots », c'est-à-dire des suites de lettres sans séparateur ni parenthèses.
peut ainsi se noter\(a\)
.
peut ainsi se noter\(a a b c\).
✎ Dénombrement des k-uplets (ou k-listes)
Méthode Dénombrer des \(\boldsymbol k\)-uplets.
Lors du lancer d'une pièce de monnaie, on note
l'ensemble des résultats possibles : « Pile », noté
, et « Face », noté
.
.
On lance trois fois de suite la pièce de monnaie.
On forme donc des listes de trois éléments (des
-uplets)pris parmi les éléments de
Utilisation d'un arbre
Il y a deux possibilités pour le premier élément (
ou
), deux possibilités pour le deuxième élément (
ou
) etdeux possibilités pour le troisième élément (
ou
).
Ainsi, le nombre de chemins différents est de
.
Le nombre de
-uplets est\(8.\)
Utilisation de cases
Au lieu de représenter un arbre, on peut chercher à former des « mots » de trois lettres, en utilisant les lettres
et
.
Il y a deux possibilités pour la première lettre(
ou
), deux possibilités pour la deuxième lettre (
ou
) et deux possibilités pour la troisième lettre(
ou
).
Il y a :
mots différents possibles formés avec les lettres
et
.
Le nombre de
-uplets est donc
.
L'ensemble de ces listes de
éléments est :
.
Propriété
Le nombre de listes de
éléments pris dans un ensemble
à
éléments est :
.
Nombre de parties d'un ensemble fini
Propriété
Soit
un ensemble fini à
éléments.
Le nombre de parties (de sous-ensembles) de
est
.
Démonstration
On considère
un ensemble fini à
éléments. On cherche à former une partie d'éléments de
.
Pour former une telle partie, on a deux choix pour chaque élément de
: l'incorporer dans la partie ou non.
Cela revient à choisir, pour chaque élément de
, un élément dans l'ensemble
.
Autrement dit, on associe à une partie de
une liste à
éléments formés par des
et des
.
Pour chacun de ces éléments de la liste, il y a deux possibilités.
Le nombre de parties (de sous-ensembles) d'un ensemble à
éléments est égal au nombre de
-uplets de l'ensemble
c'est-à-dire
.
Permutation d'un ensemble fini, notation factorielle
Définition
Soit
un ensemble fini à
éléments, avec
non nul.
Une liste de
éléments formée avec les
éléments distincts de l'ensemble
est appelée unepermutationde
.
Exemple
Soit le mot «
». On considère l'ensemble
des lettres de ce mot.
.
Alors les permutations de l'ensemble
sont :
.
.
Il y a
permutations de l'ensemble
.
Remarque
Une anagramme (mot féminin) est un mot formé en changeant de place les lettres d'un mot donné (que le mot obtenu ait un sens ou non). Donc, le nombre d'anagrammes du mot«
» est 6.
Propriété
Le nombre de permutations d'un ensemble
à
éléments, avec
, est :
.
Définition
Soit\(n\)un entier naturel.
• Pour tout\(n ⩾ 1\),
se note
et se lit « factorielle
» ou «
factorielle ». C'est le produit des entiers de
à
.
• Par convention, on a
.
Exemple
. C'est le nombre de permutations de l'ensemble
de l'exemple précédent.
RemarqueRelation de récurrence
Pour tout entier naturel
, on a
.
Exemple
On cherche le nombre d'anagrammes du mot «
».
Il y a
éléments distincts dans l'ensemble des lettres du mot «
», donc le nombre de permutations est
.
Listes d'éléments distincts
Définition
Soit
un ensemble fini de
éléments, avec
non nul.
Soit
un entier tel que
.
Unarrangementde
éléments de
est une liste de
éléments de
deux à deux distincts.
Exemples
• Classement des meilleurs concurrents lors d'une épreuve, lors d'une course, etc.
• Tirage sans remise de
jetons parmi des jetons numérotés de
à
.
Remarque
Soit
un ensemble fini de
éléments, avec
non nul. Un arrangement de
éléments de
est une liste de
éléments de
deux à deux distincts, c'est-à-dire une permutation de
.
Propriété
Soit
un entier naturel non nul et
un entier tel que
.
Le nombre d'arrangements dans une liste de
éléments parmi
est
, ce qui peut aussi s'écrire
.
Exemple
Le nombre de classements des
meilleurs élèves à un devoir de mathématiques dans un groupe de
élèves est :
. En effet, il y a
possibilités pour l'élève qui a obtenu la meilleure note du groupe, puis
possibilités pour celui qui a obtenu la deuxième meilleure note, puis
possibilités pour celui qui a obtenu la troisième meilleure note.
☛ Utiliser des listes d'éléments distincts
Énoncé
Comment classer
concurrents lors d'une course d'athlétisme sans ex aequo ?
Solution
On note
l'ensemble des
concurrents. On cherche à former des mots de
lettressans répétition.
Pour la première lettre, il y a
choix possibles. Comme elle ne peut plus être réutilisée, il ne reste plus que
choix possibles pour la deuxième lettre. Puis il reste
choix possibles pour la troisième lettre,
choix possibles pour la quatrième et
seul choix possible pour la dernière.
.
Conclusion: il y a donc
manières de classer
concurrents sans ex aequo.