Fiche 15 • Combinatoire et dénombrement
S. Soit E et F deux ensembles finis. Nous avons :
Card (EX F) = Card (E) · Card(F)
Card('.F(E, F)) = Card (FE)= Card (Ff.,d(El.
6. Soit E un ensemble fini. Nous avons:
Card ('P(E)) = Card ('.F(E, 10, 1 f)) = Card (10, l fE) = 2 c ord(EJ.
7. Soit E un ensemble fini, A c E et IA la fonction indicatrice de A, voir Fiche 16.
Card (A) = L: 1, (x).
x 4. DÉNOMBREMENT
a) Factorielle
Nous appelons factorielle la fonction, notée!, de N dans N définie par 11! = 1 x2 x · · · x 11. Par
convention, 0 ' est égal à 1.
b) Nombre de permutations den objets
Le nombre des bijections d'un ensemble E à /1 éléments sur lui-même, c'est-à-dire le nombre de
permutations de 11 objets, vaut 11•.
c) Nombre d'arrangements den objets m à m
Soit E et F deux ensembles finis tels que Card (E) = m .;; /1 = Card (F). Alors le nombre des
applications injectives de E dans Fest égal à:
m
11•
(
)
(
)
A,, = (n - m)! =nn - 1 ··· n - m+ 1.
Nous appelons A=' nombre d 'arrangements de 11 objets m à m.
Remarque
A~ est aussi le no mbre de suites distinctes à m éléments sans répétit ion qu'il est possible de former avec
un ensemble de n éléments.
d) Nombre de combinaisons den objets p à p
Soit E un ensemble fini de cardinal /1 et f' E N ttel que f' .;; 11. Le nombre des parties A de E
comportant f' éléments est égal à :
11 1
11(11 - l )···(ll - f)+ 1)
fJ!(11 - fJ)!
p(p - 1) ... 1
Ce nombre est noté (;) ou encore c:.
Nous appelons(; ) nombre des combinaisons de 11 objets p à p.
• (; )est le nombre de choix possibles de f' éléments différents pris dans un ensemble den objets,
indépendamment de l'ordre dans leq uel les éléments sont c hoisis.
• Relations fondamentales
Nous avons(; )= c.~p)• (~) = t,) = I, (':) = c,~ 1 ) = 11.
38