Revenir
Revenir

Listes d'éléments

un entier naturel non nul. Soit\(k\)ensembles non vides

Sommaire

k-uplet (ou k-liste)✎ Dénombrement des k-uplets (ou k-listes)Nombre de parties d'un ensemble finiPermutation d'un ensemble fini, notation factorielleListes d'éléments distincts☛ Utiliser des listes d'éléments distincts

k-uplet (ou k-liste)

Définition
Soit
kkk
un entier naturel non nul. Soit\(k\)ensembles non vides
E1,E2,...,EkE_1, E_2, ..., E_kE1​,E2​,...,Ek​
.
    • Toute liste ordonnée
(x1,x2,...,xk)(x_1,x_2,...,x_k)(x1​,x2​,...,xk​)
, avec \(x_i \in E_i\)pour
iii
allant de
111
à
kkk
, est appelée 
k-upletk \text {-uplet}k-uplet
(ou
kkk
-liste).
    • L'ensemble de ces
kkk
-upletsest donc le produit cartésien
E1×E2×...×EkE_1\times E_2\times ...\times E_kE1​×E2​×...×Ek​
.
Remarques
    • Un 2-uplet est uncouple.
    • Un 3-uplet est untriplet.
    • Soit
EEE
un ensemble non vide fini de cardinal 
n
. Soit
k
un entier compris entre
111
et
nnn
. Un
kkk
-upletd'éléments de
EEE
est un élément de
EkE^kEk
.
Exemple
Soit
E={a ; b ; c}E = \{ a~;~ b~;~ c \}E={a ; b ; c}
un ensemble à trois éléments. On peut former des listesd'éléments de\(E\):
    • des
222
-uplets, c'est-à-dire des couples :
(a ; b),(b ; a),(a ; c),(b ; c),(a ; a),(b ; b)(a~;~b), (b~;~a), (a~;~c), (b~;~c), (a~;~a), (b~;~b)(a ; b),(b ; a),(a ; c),(b ; c),(a ; a),(b ; b)
, etc.
    • des
333
-uplets, c'est-à-dire des triplets :
(a ; b ; c),(a ; c ; b),(b ; a ; c),(c ; b ; b)(a~;~b~;~c), (a~;~c~;~b), (b~;~a~;~c), (c~;~b~;~b)(a ; b ; c),(a ; c ; b),(b ; a ; c),(c ; b ; b)
, etc.
    • des
444
-uplets :
(c ; a ; b ; c),(b ; b ; a ; c)(c~;~a~;~b~;~c), (b~;~b~;~a~;~c)(c ; a ; b ; c),(b ; b ; a ; c)
, etc.
Remarque
Pour faciliter les notations, on peut remplacer ces
kkk
-uplets par des « mots », c'est-à-dire des suites de lettres sans séparateur ni parenthèses.
(a ; b)(a~;~b)(a ; b)
peut ainsi se noter\(a\)
bbb
.
(a ; a ; b ; c)(a~;~a~;~b~;~c)(a ; a ; b ; c)
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
EEE
l'ensemble des résultats possibles : « Pile », noté
P\text PP
, et « Face », noté
F\text FF
.
E={P ; F}E = \{ \text P ~;~ \text F \}E={P ; F}
.
On lance trois fois de suite la pièce de monnaie.
On forme donc des listes de trois éléments (des
333
-uplets)pris parmi les éléments de
E.E.E.
Utilisation d'un arbre
Il y a deux possibilités pour le premier élément (
P\text PP
ou
F\text FF
), deux possibilités pour le deuxième élément (
P\text PP
ou
F\text FF
) etdeux possibilités pour le troisième élément (
P\text PP
ou
F\text FF
).
Ainsi, le nombre de chemins différents est de
2×2×2=82 \times 2 \times 2 = 82×2×2=8
.
Le nombre de 
333
-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
P\text PP
et
F\text FF
.
Il y a deux possibilités pour la première lettre(
P\text PP
ou
F\text FF
), deux possibilités pour la deuxième lettre (
P\text PP
ou
F\text FF
) et deux possibilités pour la troisième lettre(
P\text PP
ou
F\text FF
).
Il y a : 
2×2×2=82 \times 2 \times 2 = 82×2×2=8
mots différents possibles formés avec les lettres
P\text PP
et
F\text FF
. 
Le nombre de 
333
-uplets est donc
888
.
L'ensemble de ces listes de
333
éléments est :
{PPP ; PPF ; PFP ; PFF ; FPP ; FPF ; FFP ; FFF}\{ \mathrm {PPP ~;~ PPF ~;~ PFP ~;~ PFF ~;~ FPP ~;~ FPF ~;~ FFP ~;~ FFF} \}{PPP ; PPF ; PFP ; PFF ; FPP ; FPF ; FFP ; FFF}
.
Propriété
Le nombre de listes de 
kkk
éléments pris dans un ensemble
EEE
à
nnn
éléments est : 
nk\boxed{n^k}nk​
.

Nombre de parties d'un ensemble fini

Propriété
Soit
EEE
un ensemble fini à
nnn
éléments.
Le nombre de parties (de sous-ensembles) de
EEE
est
2n2^n2n
.
Démonstration
On considère
EEE
un ensemble fini à
nnn
éléments. On cherche à former une partie d'éléments de
EEE
.
Pour former une telle partie, on a deux choix pour chaque élément de
EEE
: l'incorporer dans la partie ou non.
Cela revient à choisir, pour chaque élément de
EEE
, un élément dans l'ensemble 
{0 ; 1}\{ 0~;~ 1 \}{0 ; 1}
.
Autrement dit, on associe à une partie de
EEE
une liste à
nnn
éléments formés par des
000
et des
111
.
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 à
nnn
éléments est égal au nombre de
nnn
-uplets de l'ensemble
{0 ; 1}\{ 0~ ;~ 1 \}{0 ; 1}
c'est-à-dire
2n2^n2n
.

Permutation d'un ensemble fini, notation factorielle

Définition
Soit
EEE
un ensemble fini à
nnn
éléments, avec
nnn
non nul.
Une liste de
nnn
éléments formée avec les
nnn
éléments distincts de l'ensemble
EEE
est appelée unepermutationde
EEE
.
Exemple
Soit le mot «
MOT\text M\text O\text TMOT
». On considère l'ensemble
EEE
des lettres de ce mot. 
E={M ; O ; T}E = \{ \text M~;~ \text O~;~ \text T \}E={M ; O ; T}
.
Alors les permutations de l'ensemble
EEE
sont :
MOT, MTO, TMO, TOM, OMT, OTM\text {MOT, MTO, TMO, TOM, OMT, OTM}MOT, MTO, TMO, TOM, OMT, OTM
.
3×2×1=63 \times 2 \times 1 = 63×2×1=6
.
Il y a
666
permutations de l'ensemble
EEE
.
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«
MOT\text M\text O\text TMOT
» est 6.
Propriété
Le nombre de permutations d'un ensemble 
EEE
à
nnn
éléments, avec 
n⩾1n ⩾ 1n⩾1
, est :
n×(n−1)×...×3×2×1\boxed{n \times (n - 1) \times ... \times 3 \times 2 \times 1}n×(n−1)×...×3×2×1​
.
Définition
Soit\(n\)un entier naturel.
    • Pour tout\(n ⩾ 1\), 
n×(n−1)×...×3×2×1n \times (n - 1) \times ... \times 3 \times 2 \times 1n×(n−1)×...×3×2×1
se note 
n!n!n!
 et se lit « factorielle
nnn
 » ou «
nnn
factorielle ». C'est le produit des entiers de
111
à
nnn
.
    • Par convention, on a 
0!=10 ! = 10!=1
.
Exemple
3!=3×2×1=63! = 3 \times 2 \times 1 = 63!=3×2×1=6
. C'est le nombre de permutations de l'ensemble
EEE
de l'exemple précédent.
RemarqueRelation de récurrence
Pour tout entier naturel 
nnn
, on a 
(n+1)!=(n+1)×n!\boxed{(n + 1)! = (n + 1) \times n!}(n+1)!=(n+1)×n!​
.
Exemple
On cherche le nombre d'anagrammes du mot «
MIEL\text M\text I\text E\text LMIEL
».
Il y a
444
éléments distincts dans l'ensemble des lettres du mot «
MIEL\text M\text I\text E\text LMIEL
», donc le nombre de permutations est
4!=4×3×2×1=244! = 4 \times 3 \times 2 \times 1 = 244!=4×3×2×1=24
.

Listes d'éléments distincts

Définition
Soit
EEE
un ensemble fini de
nnn
éléments, avec 
nnn
non nul.
Soit
kkk
un entier tel que
1⩽k⩽n1 ⩽ k ⩽ n1⩽k⩽n
.
Unarrangementde
kkk
éléments de 
EEE
est une liste de
kkk
éléments de 
EEE
deux à deux distincts.
Exemples
    • Classement des meilleurs concurrents lors d'une épreuve, lors d'une course, etc.
    • Tirage sans remise de
444
jetons parmi des jetons numérotés de
111
à
666
.
Remarque
Soit
EEE
un ensemble fini de
nnn
éléments, avec 
nnn
non nul. Un arrangement de
nnn
éléments de 
EEE
est une liste de
nnn
éléments de 
EEE
deux à deux distincts, c'est-à-dire une permutation de 
EEE
.
Propriété
Soit
nnn
un entier naturel non nul et
kkk
un entier tel que 
1⩽k⩽n1 ⩽ k ⩽ n1⩽k⩽n
.
Le nombre d'arrangements dans une liste de
kkk
éléments parmi
nnn
est 
n×(n−1)×...×(n−k+1)n \times (n - 1) \times ... \times (n - k + 1)n×(n−1)×...×(n−k+1)
, ce qui peut aussi s'écrire
n!(n−k)!\boxed{\dfrac{n!}{(n-k)!}}(n−k)!n!​​
.
Exemple
Le nombre de classements des
333
meilleurs élèves à un devoir de mathématiques dans un groupe de
151515
élèves est :
15×14×13=273015 \times 14 \times 13 = 273015×14×13=2730
. En effet, il y a 
151515
possibilités pour l'élève qui a obtenu la meilleure note du groupe, puis
141414
possibilités pour celui qui a obtenu la deuxième meilleure note, puis
131313
possibilités pour celui qui a obtenu la troisième meilleure note.

☛ Utiliser des listes d'éléments distincts

Énoncé
Comment classer
555
concurrents lors d'une course d'athlétisme sans ex aequo ?
Solution
On note 
E={a ; b ; c ; d ; e}E = \{ a~;~ b~;~ c~;~ d~;~ e \}E={a ; b ; c ; d ; e}
 l'ensemble des
555
concurrents. On cherche à former des mots de
555
lettressans répétition.
Pour la première lettre, il y a
555
 choix possibles. Comme elle ne peut plus être réutilisée, il ne reste plus que 
444
choix possibles pour la deuxième lettre. Puis il reste
333
choix possibles pour la troisième lettre,
222
choix possibles pour la quatrième et
111
seul choix possible pour la dernière.
5×4×3×2×1=1205 \times 4 \times 3 \times 2 \times 1 = 1205×4×3×2×1=120
.
Conclusion: il y a donc
120120120
manières de classer
555
concurrents sans ex aequo.