1.3 Des dénombrements utiles
Si des ensembles finis E et F ont le même nombre d’éléments, on sait qu’il existe
des applications bijectives de E dans F . Calculons le nombre de ces bijections.
Proposition. Si E et F sont des ensembles finis ayant le même nombre n d’éléments,
il y a n! applications bijectives de E dans F .
Démonstration. Posons E = {a 1 , . . . , a n } et F = {b 1 , . . . , b n }. Pour définir une bijection de
f : E → F , on peut choisir l’élément f (a 1 ) arbitrairement dans F ; l’élément f (a 2 ) doit être
différent de f (a 1 ), ce qui laisse n−1 possibilités ; ensuite, il reste n−2 possibilités pour choisir
f (a 2 ), et en général n−k possibilités pour choisir f (a k ). Finalement, il y a n(n−1) · · · 2 · 1
possibilités pour définir une bijection de E dans F .
Quand on se donne un ensemble fini E sous la forme E ={a 1 ,. . .,a n }, les éléments de
E ont été ordonnés : il y a un premier élément a 1 , un deuxième a 2 , etc. Si l’on change la
numérotation, les éléments de E sont les mêmes, mais l’ordre est différent. Numéroter
les éléments de E , c’est établir une bijection de l’ensemble {1,2,. . .,n} dans E . D’après
la proposition précédente, il y a donc n! façons de numéroter les éléments de E .
Nombre de p -arrangements
Définition
Soit E un ensemble fini à n éléments et soit p un entier tel que 1 p n. Un
p-arrangement d’éléments de E est une suite (a 1 , a 2 , . . . , a p ) de p éléments de E
deux à deux différents.
Pour définir un p-arrangement (a 1 , a 2 , . . . , a p ) d’un ensemble E à n éléments, il y
a n façons de choisir a 1 , n−1 façons de choisir a 2 (car a 2 doit être différent de a 1 ),
etc, donc finalement n(n−1) · · · (n−p+1) façons de choisir les éléments a 1 , . . . , a p .
Proposition. Soit E un ensemble à n éléments. Si p est un entier tel que 1 p n,
le nombre de p-arrangements de E est n(n−1) · · · (n−p+1) = n!
(n−p)!
.
Si E est un ensemble à n éléments, un n-arrangement de E est une bijection de
{1, 2, . . . , n} dans E : on retrouve ainsi qu’il y a n! bijections entre deux ensembles à
n éléments. Ainsi, on a l’égalité 0! = 1.
Nombre de parties à p éléments
Proposition. Soit E un ensemble à n éléments. Si p est un entier tel que 0 p n,
le nombre de parties de E ayant p éléments est
n!
p!(n−p)!
.
Démonstration. Il n’y a qu’une partie à zéro éléments : la partie vide ; le résultat est donc
vrai si p = 0, car par convention, 0! = 1. Supposons p 1. Soit A une partie de E ayant p
éléments. Les p-arrangements de E formés avec les éléments de A sont définis en se donnant
une bijection de {1, 2, . . . , p} dans A. Il y a p! bijections de {1, 2, . . . , p} dans A, donc il y a
60 – ENSEMBLES FINIS
Si des ensembles finis E et F ont le même nombre d’éléments, on sait qu’il existe
des applications bijectives de E dans F . Calculons le nombre de ces bijections.
Proposition. Si E et F sont des ensembles finis ayant le même nombre n d’éléments,
il y a n! applications bijectives de E dans F .
Démonstration. Posons E = {a 1 , . . . , a n } et F = {b 1 , . . . , b n }. Pour définir une bijection de
f : E → F , on peut choisir l’élément f (a 1 ) arbitrairement dans F ; l’élément f (a 2 ) doit être
différent de f (a 1 ), ce qui laisse n−1 possibilités ; ensuite, il reste n−2 possibilités pour choisir
f (a 2 ), et en général n−k possibilités pour choisir f (a k ). Finalement, il y a n(n−1) · · · 2 · 1
possibilités pour définir une bijection de E dans F .
Quand on se donne un ensemble fini E sous la forme E ={a 1 ,. . .,a n }, les éléments de
E ont été ordonnés : il y a un premier élément a 1 , un deuxième a 2 , etc. Si l’on change la
numérotation, les éléments de E sont les mêmes, mais l’ordre est différent. Numéroter
les éléments de E , c’est établir une bijection de l’ensemble {1,2,. . .,n} dans E . D’après
la proposition précédente, il y a donc n! façons de numéroter les éléments de E .
Nombre de p -arrangements
Définition
Soit E un ensemble fini à n éléments et soit p un entier tel que 1 p n. Un
p-arrangement d’éléments de E est une suite (a 1 , a 2 , . . . , a p ) de p éléments de E
deux à deux différents.
Pour définir un p-arrangement (a 1 , a 2 , . . . , a p ) d’un ensemble E à n éléments, il y
a n façons de choisir a 1 , n−1 façons de choisir a 2 (car a 2 doit être différent de a 1 ),
etc, donc finalement n(n−1) · · · (n−p+1) façons de choisir les éléments a 1 , . . . , a p .
Proposition. Soit E un ensemble à n éléments. Si p est un entier tel que 1 p n,
le nombre de p-arrangements de E est n(n−1) · · · (n−p+1) = n!
(n−p)!
.
Si E est un ensemble à n éléments, un n-arrangement de E est une bijection de
{1, 2, . . . , n} dans E : on retrouve ainsi qu’il y a n! bijections entre deux ensembles à
n éléments. Ainsi, on a l’égalité 0! = 1.
Nombre de parties à p éléments
Proposition. Soit E un ensemble à n éléments. Si p est un entier tel que 0 p n,
le nombre de parties de E ayant p éléments est
n!
p!(n−p)!
.
Démonstration. Il n’y a qu’une partie à zéro éléments : la partie vide ; le résultat est donc
vrai si p = 0, car par convention, 0! = 1. Supposons p 1. Soit A une partie de E ayant p
éléments. Les p-arrangements de E formés avec les éléments de A sont définis en se donnant
une bijection de {1, 2, . . . , p} dans A. Il y a p! bijections de {1, 2, . . . , p} dans A, donc il y a
60 – ENSEMBLES FINIS