Ensembles et fonctions.

par
Daouda Niang Diatta
(email:[email protected])

pour
La Licence 1 d'Informatique et d'Ingénierie.
(L12I)

Département Informatique.
UFR Sciences et Technologies.
Université Assane Seck de Ziguinchor.

Introduction
On développe dans ce chapitre les constructions de base de la théorie des ensembles, en
particulier celles qui concernent les fonctions en même temps que certains outils de base
pour l'énumération des éléments des ensembles considérés.

1 Ensembles
La théorie des ensembles a été introduite par Georg Cantor (1845 - 1918). Bien qu'il
soit nécessaire d'en donner une axiomatique rigoureuse pour éviter les paradoxes, nous
n'aurons pas trop besoin d'insister là-dessus, étant donné que les ensembles considérés dans
ce cursus sont soit finis, soit des ensembles classiques comme N=f0; 1; 2; 3; :::g, Z=f:::;
¡2; ¡1; 0; 1; 2; :::g, l'ensemble Q des nombres rationnels, ou l'ensemble R des nombres réels.

1.1 Définition et propriétés de base des ensembles

Définition. (Ensemble) Un ensemble est une collection d'objets qui en constituent les
éléments. On peut décrire un ensemble de deux manières :
En extension. On donne la liste exhaustive des éléments de l'ensemble :
E := fe1; e2; ::::g:

En compréhension. On donne la propriété satisfaite par les éléments de l'ensemble :

E := fx j P (x)g:

Le fait que l'objet x appartienne à l'ensemble E se note : x 2E alors que le contraire se

/ E.
note x 2

Remarque. (Fondamentale) Un ensemble ne peut pas contenir plusieurs fois le même

objet. C'est un des principes fondamentaux de la théorie des ensemble.

Exemple.
! Ensemble des lettres de l'alphabet :

A := fa; b; c; d; ::::; z g:

1
 ! En compréhension, on a l'ensemble des naturels compris entre 1 et n :
[n] := fi 2 Nj1 6 i 6 ng
qui s'écrit, en extension :
[n] := f1; 2; :::; ng:
! En compréhension, on a :
A := fa 2 N tel que a divise 14g et B := fx 2 R tel que x2 + x ¡ 1 = 0g
qui s'écrivent, en extension :
 p p 
¡1 + 5 ¡1 ¡ 5
A := f1; 2; 7; 14g et B := ; :
2 2

Remarque.
! Passer d'une description en compréhension à une description en extension d'un
ensemble donné constitue l'une des tâches majeures de l'activité mathématique.
! Deux ensembles sont égaux si et seulement si ils ont les mêmes éléments. Ainsi on
a les descriptions en extension fa; b; cg = fc; a; bg = fb; c; ag d'un même ensemble
qui contient trois éléments : a, b et c.

Proposition 1. Si A et B sont décrits en compréhension par A := fx j P (x)g et B :=

fx j Q(x)g avec P (x) et Q(x) des propriétés formulées en terme d'énoncés logiques, on a :
A = B si et seulement si P (x) et Q(x) sont logiquement équivanlentes.

Démonstration. 

Définition. L'ensemble vide, noté ? ou fg, est l'ensemble ne contenant aucun élément.
Le cardinal d'un ensemble E, noté jE j ou card(E); est son nombre d'éléments.
Un ensemble fini est un ensemble de cardinal fini. Un ensemble de cardinal non fini
est dit infini.

Exemple. Ainsi, j?j = 0, jA := fa; b; c; d; ::::; z gj = 26 et j[n]: =f1; :::; ngj = n. Donc ?, A
et [n] sont des ensembles finis, alors que N et R sont des ensembles infinis.

1.2 Opérations de base sur les ensembles.

Définition. (Intersection) L'intersection de deux ensembles A et B, notée A \ B, est

l'ensemble des éléments qui sont communs à ces deux ensembles :
A \ B := fx j x 2 A et x 2 B g: (1)

Exemple. On a : fa; b; c; dg \ f1; b; 3; dg = fb; dg.

Définition. (Union) L'union de deux ensembles A et B, notée A [ B, est l'ensemble des

éléments qui sont dans A ou dans B :
A [ B := fx j x 2 A ou x 2 B g: (2)

Exemple. On a : fa; b; c; dg [ f1; b; 3; dg = fa; b; c; d; 1; 3g.

Proposition 2. Quel que soient les ensembles A; B et C, on a :

2
1. A \ ? = ?; 1'. A [ ? = A;
2. A\B =B \A 2'. A[B =B [A
3. A \ (B \ C) = (A \ B) \ C 3'. A [ (B [ C) = (A [ B) [ C
4. A \ (B [ C) = (A \ B) [ (A \ C) 4'. A [ (B \ C) = (A [ B) \ (A [ C)

Démonstration. 

Définition. (Union disjointe) L'union de deux ensembles A et B est dite disjointe

lorsque A \ B = ?. On écrit A + B pour désigner l'union disjointe des ensembles A et B :
Si A \ B = ? alors A + B := A [ B: (3)

Exemple. Pour A = fa; b; 1; 2g et B = fc; d; e; 3; 4g, comme A \ B = ?, alors

A [ B = A + B = fa; b; 1; 2; c; d; e; 3; 4g:

Définition. (Différence) La différence de deux ensembles A et B, notée AnB, est

l'ensemble des éléments de A qui ne sont pas dans B :
AnB := fx 2 A j x 2
/ B g: (4)

Exemple. Pour A = fa; b; c; d; 1; 2g et B = fc; d; e; 3; 4g, on a : AnB = fa; b; 1; 2g:

1.3 Sous-ensembles

Définition. (Sous-ensemble) Un sous-ensemble de A ou une partie de A est un ensemble

B dont tous les éléments sont aussi des éléments de A. On note alors B  A et on lit B
est inclus dans A.

Remarque. Observons que se donner un sous-ensemble B de cardinal k d'un ensemble A

de cardinal n, correspond à  choisir k éléments parmi n .

Proposition 3. Quel que soient les ensembles A; B et C, on a :

1. ?  A: 2. A  A:
3. (A  B et B  A) () A = B. 4. Si A  B et B  C alors A  C.

Démonstration. 

Remarque. Observons que :

! Si A et B sont décrits par A := fx j P (x)g et B := fx j Q(x)g, alors :

B  A si et seulement si l'énoncé logique Q(x) =) P (x)  est vrai.

! Quel que soient les ensembles A et B, on a : A \ B  A et A  A [ B:

! Si B est un sous-ensemble de A, alors A \ B = B et A [ B = A.

Proposition 4. Si A et B sont décrits en compréhension par A := fx j P (x)g et B :=

fx j Q(x)g, alors :
B  A si et seulement si l'énoncé logique  Q(x) =) P (x)  est vrai.

Démonstration. 

3
Définition. (Ensemble des parties) L'ensemble des parties d'un ensemble E, noté
P[E], est l'ensemble de tous les sous-ensembles de E :
P[E] := fAj A  E g: (5)

Exemple. Ainsi P[fa; b; cg] = f?; fag; fbg; fcg; fa; bg; fa; cg; fb; cg; fa; b; cgg et
jP[fa; b; cg]j = 8.

Définition. (Complémentaire) Le complémentaire de A dans E, noté A ou Ac ou encore

CEA, est l'ensemble des éléments de E qui ne sont pas éléments de A :
A: =Ac := CEA := fx 2 E j x 2
/ Ag: (6)

Exemple. Ainsi, pour E = fa; b; c; d; e; f g et A = fb; c; eg, on a : A = fa; d; f g.

Proposition 5. Si l'ensemble A est décrit en compréhension par A := fx 2 E j P (x)g alors

A = fx 2 E j:P (x)g: (7)

Démonstration. 

Proposition 6. Quel que soient A et B des sous-ensembles de E, on a :

1. A = A; 1'. A [ B
 =A\B

2. A \ A = ? 2'. A [ A = E ;
3. A \ B
 =A[B 3'. A [ A = A + A = E

Démonstration. 

1.4 Famille d'ensembles et opérations

Supposons que pour chaque élément i d'un ensemble I, on choisisse un sous-ensemble Ai
de E. On dit alors qu'on a une famille d'ensembles indexée par les éléments de I, et on
dénote fAigi2I cette famille d'ensembles (c'est simplement un ensemble d'ensembles). On
a souvent la situation I =[n] = f1; 2; :::; ng, et alors la famille est l'ensemble
fA1; A2; :::; Ang:
Grâce aux propriétés d'associativité évoquées dans la Proposition 2, on peut étendre sans
problème les notions d'union et d'intersection à de telles familles, en posant :
\
Ai := fx j pour tout i 2 I ; x 2 Aig:
i2I
[
Ai := fx j il existe i 2 I ; x 2 Aig:
i2I

Ainsi, pour I = [n], on écrit aussi :

\ n
\ [ n
[
Ai = Ai et Ai = Ai
i2[n] i=1 i2[n] i=1

et pour n = 3, on a :
3
\ 3
[
Ai = A1 \ A2 \ A3 et Ai = A1 [ A2 [ A3:
i=1 i=1

4
On a les identités : ! !
\ \ \
Ai = Ai \ Aj ;
k2I [J i2I j 2J
! !
[ [ [
Ai = Ai [ Aj ;
k2I [J i2I j 2J

en prenant la précaution de poser la convention :

\ [
Ai: =E et Ai := ?:
i2? i2?
De façon tout à fait similaire, on étend la notion d'unionP
disjointe aux familles d'ensembles
deux à deux disjoints. On utilise alors le symbole de  , et on écrit donc
X [
Ai := Ai;
i2I i2I

pour l'union en question. En particulier, on a les deux écritures équivalentes

n
X
Ai = A1 + A2 +


+ An:
i=1

Définition. (Partition) Une famille fAigi2I de sous-ensembles de E en est une partition,

si ses éléments sont tous non vide, deux à deux disjoints et vérifient :
X
Ai = E: (8)
i2I

Exemple. Pour toute partie A non vide et strictement incluse dans E, la famille à deux
éléments fA; A g est une partition de E.

1.5 Parties à k-éléments d'un ensemble fini

Pour chaque entier k > 0, on considère l'ensemble dénoté Pk[E] des parties à k-éléments
d'un ensemble fini E :
Pk[E] := fA j A  E et jAj = kg: (9)
Évidemment, on a : 
? si ; k > jE j;
Pk[E] = (10)
fE g si k = jE j:

Remarque. Observons que :

! Pk[E] est  l'ensemble des possibilités de choix de k éléments parmi les jE j éléments
de E.
! Plus concrètement, si E = fa; b; cg, alors on a : P0[E] = f?g, P1[E] = ffag; fbg; fcgg,
P2[E] = ffa; bg; fa; cg; fb; cgg, P3[E] = ffa; b; cgg:
! En fait, P0[E] = f?g, P1[E] = ffxg; x 2 E g, P2[E] = ffx; yg; x; y 2 E et x =
/ yg,...,
Pn[E] = fE g, pour n = jE j.

Théorème 7. La famille (Pk[E])kJ0;jE jK est une partition de P[E] :

jE j
X
P[E] = Pk[E]: (11)
k=0

5
Démonstration. 

On peut décrire en extension l'ensemble Pk[E] via la formule récursive de la proposition

suivante :

/ S:
Théorème 8. Pour tout ensemble S et tout élément y 2
Pk[S + fyg] = Pk[S] + fB + fygjB 2 Pk ¡1[S]g (12)

Démonstration. 

Exemple. Considérons le cas P2[fa; b; cg] pour illustrer l'utilisation du théorème pour
décrire en extension Pk[E].
On débute avec S = fa; bg et y = c. La récursion se déroule comme suit :
P2[fa; b; cg] = P2[fa; bg] + fB + fcgj B 2 P1[fa; bg]g
P2[fa; bg] = ffa; bgg et P1[fa; bg] = ffag; fbgg
Ainsi, en remontant la récursion, on a :
P2[fa; b; cg] = ffa; bgg + fB + fcgj B 2 ffag; fbggg
P2[fa; b; cg] = ffa; bgg + ffa; cg; fb; cgg
P2[fa; b; cg] = ffa; bg; fa; cg; fb; cgg:

1.6 Produit cartésien

Avant de décrire la prochaine construction, rappelons que deux couples (a; b) et (c; d) sont
égaux, si et seulement si on a les deux égalités a=c et b=d.

Définition. (Produit cartésien) Le produit cartésien des ensembles A et B, noté A  B,

est l'ensemble de tous les couples (x; y), avec x élément de A et y élément de B :
A  B := f(x; y)j x 2 A et y 2 B g: (13)

Exemple. On a : fa; b; c; dg  f1; 2g = f(a; 1); (b; 1); (c; 1); (d; 1); (a; 2); (b; 2); (c; 2); (d; 2)g.

Remarque. Observons que si l'un des ensembles A ou B est vide, alors le produit cartésien
A B est vide :
A  ? = ?  B = ?:

Proposition 9. Pour tout ensemble A, B et C (avec B et C disjoints), on a :

1. A  (B + C) = (A  B) + (A  C),
2. (A + B)  C = (A  C) + (B  C).

Démonstration. 

Remarque. Observons que :

! Pour un ensemble fini d'indices I, si nous dénotons par (ai)i2I les suites indexées
par les éléments de I, alors on a :
(ai)i2I = (bi)i2I () ai = bi pour tout i dans I.

6
 ! Si (Ai)i2I est une suite d'ensembles indexés par I, on dit de ai que c'est la i-ième
coordonnée de la suite. Le produit cartésien généralisé est l'ensemble
Y
Ai := f(ai)i2I jai 2 Ai; pour i 2 I g:
i2I

! Le cas particulier qui correspond à choisir I =[n] = f1; 2; :::; ng donne la construction
du produit cartésien
A1  A2 


 An = f(a1; a2; :::; an)jai 2 Ai; 1 6 i 6 ng:

! Et lorsque Ai =B, pour tous les i, on obtient la puissance cartésienne n-ième de

l'ensemble B :
B n := B  B 


 B:
|||||||||||||||||||||||{z}}}}}}}}}}}}}}}}}}}}}}}
n copies
1.7 Relations

Définition. (Relation) Une relation R, allant d'un ensemble A vers un ensemble B, est
un sous-ensemble du produit cartésien A  B :
R est une relation de A vers B si R  A  B (14)

Exemple. Pour A = fa; b; c; dg et B = f1; 2; 3g, R = f(a; 1); (a; 2); (b; 3); (c; 2); (d; 1)g est
une relation de A vers B.

Définition. (Relation transposée) La relation transposée d'une relation R de A vers

B est la relation de B vers A, dénotée RT, définie par le sous-ensemble de B  A :
RT := f(y; x) 2 B  Aj (x; y) 2 Rg: (15)

Exemple. Pour A = fa; b; c; dg et B = f1; 2; 3g et R = f(a; 1); (a; 2); (b; 3); (c; 2); (d; 1)g,
on a : RT = f(1; a); (2; a); (3; b); (2; c); (1; d)g.

Remarque. Observons que :

! Si Rel[A; B] est l'ensemble des relations de A vers B et Relk[A; B] est l'ensemble
des relations de A vers B contenant k couples, alors :
Rel[A; B] = P[A  B]: (16)
jAB
Xj
Rel[A; B] = Relk[A; B]: (17)
k=0

2 Fonctions
Bien que la notion de fonction soit l'une des plus importantes en mathématiques, ce n'est
qu'à la fin du dix-neuvième siècle qu'elle a pris la forme moderne qu'on lui connaît.

2.1 Définition et propriétés de base des fonctions

Définition. (Relation fonctionnelle ou fonction) Une relation fonctionnelle f ou une

fonction f, de l'ensemble A vers l'ensemble B, est une relation f  A  B, qui possède la
propriété que :
 pour tout x 2 A, il y'a un et un seul y 2 B tel que (x; y) 2 f .

7
Si (x; y) 2 f, alors on dit que y est l'image de x par la fonction f et x est un antécédant
de y par la fonction f.

Exemple. Pour A = fa; b; c; dg et B = f1; 2; 3g la relation R = f(a; 1); (a; 2); (b; 3); (c; 2);
(d; 1)g, n'est pas fonctionnelle car a 2 A est en relation avec deux éléments de B (1 et 2).
Par contre la relation f = f(a; 1); (b; 3); (c; 2); (d; 1)g est bien fonctionnelle.

Remarque.
! Si f est une relation fonctionnelle A vers B, un élément x dans A caractérise
uniquement l'élément correspondant y dans B. Il est habituel de désigner par f (x)
cet élément, et on a donc :

f(x) = y si et seulement si (x; y) 2 f:

! Formellement parlant, une fonction de A vers B est un triplet (f ; A; B), avec f une
relation fonctionnelle de A vers B. Il est habituel d'écrire f : A!B pour ce triplet.
! Ainsi, on a la fonction f : fa; b; c; dg ¡! f1; 2; 3g; telle que

f = f(a; 1); (b; 3); (c; 2); (d; 1)g:

Elle peut aussi se décrire en écrivant :
f(a) = 1; f(b) = 2; f (c) = 2 et f (d) = 1:
! On écrit parfois
x 7¡! f(x);
pour signifier que le couple (x; f(x)) fait partie de la relation fonctionnelle f . Ceci
est particulièrement utile lorsque l'ensemble f est décrite par une formule.
! On peut penser à une fonction comme étant un processus f qui
 choisit un seul élément f (x) de B pour chaque élément x de A .

! On peut également penser à une fonction comme étant une transformation f qui
 à chaque élément x de A associe un seul élément f (x) de B.

! Pour une fonction f : A ¡! B, on dit que l'ensemble A est la source ou l'ensemble

de départ de f, et l'ensemble B est le but ou l'ensemble d'arrivée de f .
! Une fonction f : [n] ¡! B est appelée un arrangement avec répétition de n
objets pris dans B.

Définition. On désigne par Fonct[A; B], l'ensemble des relations fonctionnnelles de

l'ensemble A vers l'ensemble B. C'est un sous-ensemble de A  B :
Fonct[A; B] := ff 2 P[A  B] j f: A ¡! B g: (18)

Remarque 10. Observons que :

! Fonct[A; B] est décrit en compréhension dans la définition précédente.
! Fonct[?; B] contient exactement un élément, quel que soit l'ensemble B. C'est la
relation vide (qui est fonctionnelle par défaut) :

Fonct[?; B] = f?g:

8
 On peut décrire en extension l'ensemble Fonct[A; B] des fonctions de A vers B via la
formule récursive du théorème suivant :

/E :
Théorème 11. Quel que soient les ensembles E et F et pour tout élément x 2
X
Fonct[E + fxg; F ] = ff + f(x; y)gjf 2 Fonct[E ; F ]g:
y 2F

Démonstration. 

Exemple. Considérons le cas Fonct[fa; b; cg; f0; 1g] pour illuster l'utilisation du théorème
précédent pour décrire en extension Fonct(A; B). On débute avec E = fa; bg et x = c.
X
Fonct[fa; b; cg; f0; 1g] = ff + f(c; y)gj f 2 Fonct[fa; bg; f0; 1g]g
y 2f0;1g
Or
X
Fonct[fa; bg; f0; 1g] = ff + f(b; y)gj f 2 Fonct[fag; f0; 1g]g;
y2f0;1g
puis
X
Fonct[fag; f0; 1g] = ff + f(a; y)gj f 2 Fonct[?; f0; 1g]g;
y 2f0;1g
et
Fonct[?; f0; 1g] = f?g:
Ainsi en remontant la recursion on obtient :
Fonct[fag; f0; 1g] = ff(a; 0)g; f(a; 1)gg:
Fonct[fa; bg; f0; 1g] = ff(a; 0); (b; 0)g; f(a; 1); (b; 0)g; f(a; 0); (b; 1)g; f(a; 1); (b; 1)gg:

Fonct[fa; b; cg; f0; 1g] = f

f(a; 0); (b; 0); (c; 0)g; f(a; 1); (b; 0); (c; 0)g;
f(a; 0); (b; 1); (c; 0)g; f(a; 1); (b; 1); (c; 0)g;
f(a; 0); (b; 0); (c; 1)g; f(a; 1); (b; 0); (c; 1)g;
f(a; 0); (b; 1); (c; 1)g; f(a; 1); (b; 1); (c; 1)g
g:

Remarque.
! On peut vérifier que :
Fonct[A; B \ C] = Fonct[A; B] \ Fonct[A; C]:

! On peut agréablement présenter les fonctions f : [n] ! B (lorsque les éléments de

B s'y prêtent), en exploitant l'ordre de présentation usuel des éléments de [n] = f1;
2; :::; ng. Ainsi, on simplifie
f = f(1; f (1)); (2; f (2)); :::; (n; f (n))g en écrivant f = f (1)f (2):::f (n):
On dit alors qu'on a présenté f sous forme de mot de longueur n et d'alphabet
B. Par exemple f = f(1; b); (2; a); (3; b); (4; a)g s'écrit encore comme f = baba.

Définition. (Restriction fonctionnelle) Pour f : A ¡! B et C  A, on a un relation

fonctionnelle, dénotée f jC, appelée la restriction de f à C, définie en posant :
f jC := f(x; f (x))jx 2 C g: (19)

9
Définition. (Composition fonctionnelle) Pour f : A ¡! B et g: B ¡! C (avec le but de
f égal à la source de g), on définit la fonction composée de g par f, dénotée g  f en posant :

g  f : A ¡! C
g  f: (20)
x 7¡! g(f(x)):

Remarque. Observons que :

! La composition de fonctions est associative : pour trois fonctions f : A ¡! B, g:
B ¡! C et h: C ¡! D, on a :
(h  g)  f = h  (g  f ):

! Pour chaque ensemble A, on a une fonction appelée identité, IdA: A ¡! A,

simplement définie en posant IdA(x) = x, pour tout x 2 A.
! Pour toute fonction f : A ¡! B, on a alors :
f  IdA = f = IdB  f :

Définition. (Fonction caractéristique) Pour un sous-ensemble B de A, la fonction

caractéristique de B dans A est la fonction B: A ¡! f0; 1g définie en posant :

1 si x 2 B ;
pour x 2 A; B(x) :=
0 sinon:

Dans le cas d'une relation R de A vers B, on parle de fonction caractéristique de la

relation R, comme étant la fonction caractéristique de R dans A  B :

1 si (x; y) 2 R;
pour (x; y) 2 A  B; R(x; y) :=
0 sinon:

Remarque. Observons que :

! La fonction caractéristique d'un sous-ensemble B de A (resp. d'une relation R de A
vers B), comme son nom l'indique, caractérise le sous-ensemble (resp. la relation)
ainsi que son complémentaire (resp. son complémentaire), puisque :
 = fx 2 Aj (x) = 0g:
B = fx 2 AjB(x) = 1g et B B

 = f(x; y) 2 A  B j (x; y) = 0g:

R = f(x; y) 2 A  B jR(x; y) = 1g et R R

! Si nous considérons le cas où R est une relation de [n] vers [k] alors :

1 si (i; j) 2 R;
R: [n]  [k] ¡¡ f0; 1g est définie par R(i; j) :=
0 si (i; j) 2
/ R;
et est ainsi un tableau de n lignes et k colonnes, encore dénoté R, dont les entrées
sont des 1 ou des 0.
! On dit alors que R est la matrice de la relation R.

Exemple. Avec n = 3 et k = 4, la relation R=f(1; 1); (1; 3); (1; 4); (2; 2); (2; 3); (3; 1); (3;
4)g a pour matrice : 0 1
1 0 1 1
R =@ 0 1 1 0 A:
1 0 0 1

10
Théorème 12. La relation R de [n] vers [k] est une relation fonctionnelle si et seulement
si sa matrice R contient un et un seul 1 sur chacune de ses lignes.

Démonstration. 

Définition 13. (Matrice transposée) La matrice transposée, d'une matrice A à n

lignes et k colonnes, est la matrice à k lignes et n colonnes, notée AT, dont les lignes sont
exactement les colonnes de A et les colonnes sont exactement les lignes de A.

Exemple.
0 1
0 1 1 0 1
1 0 1 1 B C
B 0 1 0 C
Si A =@ 0 1 1 0 A alors AT =B C
@ 1 1 0 A
1 0 0 1
1 0 1

Remarque. La matrice de la relation transposée de R est la transposée de la matrice de

la relatrion R :
RT = (R)T (21)

2.2 Image directe, image reciproque

Comme une fonction f: A ¡! B établie une relation entre les éléments de A et les éléments
de B, elle établie donc naturellement une relation entre les sous-ensembles de A et ceux
de B.
On introduit ainsi la fonction P[f]: P[A] ¡! P[B] définie, pour un sous-ensemble C de
A, en posant :
P[f](C) := ff (x)j x 2 C g (22)
ou de façon équivalente :
P[f](C) := fy 2 B j il existe x 2 C et f(x) = yg (23)

Définition. (Image directe) L'image directe du sous-ensemble C de A par la fonction

f : A ¡! B, notée f +(C),est le sous-ensemble P[f ](C) de B. Ainsi on a :
(
P[A] ¡! P[B]
f +: (24)
C 7¡! f +(C) := ff (x)j x 2 C g:

Dans le cas où on choisit C = A, l'ensemble de départ de f, on dit plus simplement que

f +(A) est l'image de f, et on dénote cet ensemble Im(f).
Im(f ): =ff(x)jx 2 Ag = fyj (x; y) 2 f g = fy 2 B j 9x 2 A; y = f (x)g (25)

Exemple. Pour la fonction f : fa; b; c; dg ¡! f1; 2; 3g définie par f = f(a; 1); (b; 3); (c; 2);
(d; 1)g, on a :
f +(fa; b; cg) = f1; 2; 3g; f +(fb; dg) = f1; 3g; Im(f ) = f1; 2; 3g:

Remarque. Pour une fonction f: A ¡! B, ll est également pertinent de considérer la

fonction f ¡: P[B] ¡! P[A] définie, pour un sous-ensemble D de B, en posant :
f ¡(D) := fx 2 Ajf (x) 2 Dg
= fx 2 Aj (x; y) 2 f et y 2 Dg

11
Définition. (Image réciproque) L'image réciproque ou l'image inverse du sous-ensemble
D de B par la fonction f : A ¡! B est le sous ensemble f ¡(D) de A. Ainsi on a :
(
P[B] ¡! P[A]
f ¡: (26)
D 7¡! f ¡(D) := fx 2 Ajf (x) 2 Dg:

Exemple. Pour la fonction f : fa; b; c; dg ¡! f1; 2; 3g définie par f = f(a; 1); (b; 3); (c; 2);
(d; 1)g; on a :
f ¡(f¡1g) = fa; bg et f ¡(f2; 3g) = fb; cg:

Proposition 14. Pour toute fonction f : A ¡! B, si fCigi2I est une famille de sous-
ensembles de B deux à deux disjoints, alors la famille ff ¡(Ci)gi2I est une famille de sous-
ensembles de A deux à deux disjoints.
En particulier la famille ff ¡(fyg)gy 2Im(f ) est une partition de A. Autrement dit c'est
une famille de sous-ensembles non vides de A, deux à deux disjoints et on a :
X
A= f ¡(fyg):
y 2Im(f )

Démonstration. 

Définition. (Fibres d'une fonction) Pour une fonction f : A ¡! B, les sous-ensem-

bles f ¡(fyg), pour y dans B, sont appelés les fibres de la fonction f. On dit alors que
f ¡(fyg) est la fibre de f en y.

2.3 Bijections, injections et surjections

Rappelons que la relation transposée d'une relation R de A vers B est la relation de B
vers A, dénotée RT et définie par le sous-ensemble de B  A
RT := f(y; x) 2 B  Aj (x; y) 2 Rg:

Définition. (Bijection) Soit f : A ¡! B une relation fonctionnelle. On dit que la fonction

f est une bijection lorsque sa relation transposée f T est fonctionnelle.
Si f est bijective alors on dénote f ¡1: B ¡! A sa relation fonctionnelle transposée f T
et on l'appelle fonction inverse ou fonction reciproque de f.

Exemple. La fonction f : fa; b; c; dg ¡! f1; 2; 3g définie par la relation f = f(a; 1); (b; 3);
(c; 2); (d; 1)g n'est pas bijective car sa relation transposée f T = f(1; a); (3; b); (2; c); (1; d)g
n'est pas fonctionnelle. En effet il y'a deux couples commençant par l'élément 1 : (1; a) et
(1; d).

Proposition 15. Si f : A ¡! B est bijective, alors :

f ¡1  f = IdA et f  f ¡1 = IdB :

Démonstration. 

Proposition 16. Pour toute fonction f: A ¡! B, si la fonction g: B ¡! A est telle que

g  f = IdA et f  g = IdB ;
alors g = f ¡1.

12
Démonstration. 

Notation. Le symbole  ! ~  dénote le fait qu'on ai une bijection, et on écrit f: A !

~ B
pour dire que f est une bijection de A vers B.

Le théorème suivant est fondamental en analyse combinatoire.

Théorème 17. Il existe une bijection entre deux ensembles finis A et B, si et seulement
si A et B ont même cardinal, i:e: : jAj=jB j.

Démonstration. 

Remarque.
! Dans le section suivante, nous allons l'utiliser plusieurs fois pour établir des identités
intéressantes.
! On désigne par Bij[A; B] l'ensemble des fonctions bijectives de A vers B , i.e :
Bij[A; B] := ff 2 Fonct[A; B]jf: A ¡!
~ B g: (27)

! Observons que si A ou B est fini alors Bij[A; B] est fini.

! Il découle du théorème précédent qu'on a Bij[A; B] = ? lorsque jAj =
/ jB j.
! Observons que Bij[?; ?] = f?g est de cardinal 1.

On peut décrire en extension l'ensemble Bij[A; B] des fonctions bijectives de A vers B

via la formule récursive du théorème suivant :

Théorème 18. Quel que soient les ensembles A et B tels que jB j = jAj + 1, et pour tout
/A :
élément x 2
X
Bij[A + fxg; B] = ff + f(x; y)gjf 2 Bij[A; B nfyg]g: (28)
y2B

Démonstration. 

Exemple. Considérons le cas Bij[fa; b; cg; f1; 2; 3g] pour illustrer l'usage du théorème
précédent pour décrire en extension Bij[A; B].
On débute avec A = fa; bg et x = c. La récursion se déroule comme suit :
X
Bij[fa; b; cg; f1; 2; 3g] = ff + f(c; y)gjf 2 Bij[fa; bg; f1; 2; 3gnfyg]g
y2f1;2;3g
X
Bij[fa; bg; f2; 3g] = ff + f(b; y)gjf 2 Bij[fag; f2; 3gnfyg]g
y2f2;3g

Bij[fa; bg; f2; 3g] = ff + f(b; 2)gjf 2 Bij[fag; f3g]g + ff + f(b; 3)gjf 2 Bij[fag; f2g]g
Bij[fa; bg; f2; 3g] = ff(a; 3); (b; 2)gg + ff(a; 2); (b; 3)gg
Bij[fa; bg; f2; 3g] = ff(a; 3); (b; 2)g; f(a; 2); (b; 3)gg
De la même manière on établie que :
Bij[fa; bg; f1; 3g] = ff(a; 3); (b; 1)g; f(a; 1); (b; 3)gg
Bij[fa; bg; f1; 2g] = ff(a; 2); (b; 1)g; f(a; 1); (b; 2)gg

13
Ainsi :
ff + f(c; 1)gjf 2 Bij[fa; bg; f2; 3g]g = ff(c; 1); (a; 3); (b; 2)g; f(c; 1); (a; 2); (b; 3)gg

ff + f(c; 2)gjf 2 Bij[fa; bg; f1; 3g]g = ff(c; 2); (a; 3); (b; 1)g; f(c; 2); (a; 1); (b; 3)gg

ff + f(c; 3)gjf 2 Bij[fa; bg; f1; 2g]g = ff(c; 3); (a; 2); (b; 1)g; f(c; 3); (a; 1); (b; 2)gg
En remontant la récursion, on obtient :

Bij[fa; b; cg; f1; 2; 3g] = f f(c; 1); (a; 3); (b; 2)g; f(c; 1); (a; 2); (b; 3)g;
f(c; 2); (a; 3); (b; 1)g; f(c; 2); (a; 1); (b; 3)g;
f(c; 3); (a; 2); (b; 1)g; f(c; 3); (a; 1); (b; 2)g
g

Remarque.
! Le composé de fonctions bijectives est une fonction bijective, et l'inverse d'une
fonction bijective est une fonction bijective.
! On dit habituellement d'une bijection de A vers A que c'est une permutation de
A, et on désigne souvent par S[A] l'ensemble des permutations de A.
! Lorsque A=[n], on écrit simplement S[n]. Les permutations sont souvent dénotées
par des lettres grecques minuscules : ;  ; ; etc:
! La matrice  associée à une permutation  de [n] est la matrice de la relation
fonctionnelle : [n] ¡! [n]. C'est une matrice carrée n  n de 0 et de 1, ayant un 1
dans chaque ligne, et un 1 dans chaque colonne.

Parmi les propriétés particulières des fonctions, l'injectivité et la surjectivité sont

très certainement des notions importantes.

Définition. (Injection) Une fonction f : A ¡! B est une injection lorsque :

 pour chaque élément y de B, il existe au plus un élément x de A tel que f (x)= y .

Remarque. Observons que :

! Une fonction f : A ¡! B est injective si et seulement si, pour tout x1 et tout x2 dans
A:
x1 =
/ x2 =) f(x1) =
/ f (x2)

ce qui équivaut (logiquement) à dire aussi que :

f (x1) = f(x2) =) x1 = x2:

! Une fonction f : A ¡! B est injective si et seulement si f admet un inverse à

gauche, c.-à-d. : il existe g : B ¡!A tel que g  f =IdA. En général, un tel inverse
à gauche n'est pas unique, et il n'est pas un inverse à droite.
! Lorsque A=[n], une fonction injective f: [n] ¡! B est encore appelée un arrange-
ment sans répétition de n objets pris dans B.

Notation. On dénote souvent par le symbole  ,¡!  le fait qu'une fonction soit injective.
On écrit donc f : A,¡!B, pour dire que f est une injective.

14
Remarque.
! On désigne par Inj[A; B] l'ensemble fonctions f injectives de A vers B :
Inj[A; B] := ff 2 Fonct[A; B]jf : A,¡!B g: (29)
! Pour qu'il existe une injection f : A,¡!B, le nombre d'éléments de A doit nécessaire-
ment être plus petit ou égal à celui de B, c.-à-d. : jAjjB j. On a donc Inj(A; B) =;;
lorsque jAj>jB j.

Proposition 19. Une injection entre deux ensembles finis de même cardinal est une
bijection.

Démonstration. 

On peut décrire en extension l'ensemble Inj[A,B] des fonctions de A vers B injectives

via la formule récursive du théorème suivant :

/A :
Théorème 20. Quel que soient les ensembles A et B, et pour tout élément x 2
X
Inj[A + fxg; B] = ff + f(x; y)gjf 2 Inj[A; B nfyg]g (30)
y2B

Démonstration. 

Exemple. Pour A = fa; bg et B = f1; 2; 3g, on a :

Inj[A; B] = f f(a; 1); (b; 2)g; f(a; 1); (b; 3)g;
f(a; 2); (b; 3)g; f(a; 2); (b; 1)g;
f(a; 3); (b; 1)g; f(a; 3); (b; 2)g
g:

Définition. (Surjection) Une fonction f : A ¡! B est une surjection lorsque :

 pour chaque élément y de B, il existe au moins un élément x de A tel que f (x)= y. 

Remarque. Observons que :

! Une fonction f : A ¡! B est surjective si et seulement si, pour tout y dans B la fibre
de f en y est non vide. On a :
X
A= f ¡(fyg):
y2B

! Une fonction f: A ¡! B est surjective si et seulement si f admet un inverse à

droite, c.-à-d. : il existe g : B ¡!A tel que f  g =IdB. En général, un tel inverse à
droite n'est pas unique, et il n'est pas un inverse à gauche.

Notation. On dénote souvent par le symbole  ¡  le fait qu'une fonction soit surjective.
On écrit donc f : A ¡ B, pour dire que f est surjective.

Remarque.
! On désigne par Surj(A; B) l'ensemble des fonctions surjectives de A vers B :
Surj[A; B] := ff 2 Fonct[A; B]jf : A ¡ B g: (31)

15
 ! Pour qu'il existe une surjectionf : A ¡ B, le nombre d'éléments de A doit néces-
sairement être plus grand ou égal à celui de B, c.-à-d. : jAj> jB j. On a donc
Surj(A; B) =;; lorsque jAj<jB j.

Proposition 21. Une surjection entre deux ensembles finis de même cardinal est une
bijection.

Démonstration. 

On peut décrire en extension l'ensemble Surj[A; B] des fonctions de A vers B surjectives

via la formule récursive du théorème suivant :

Théorème 22. Quel que soient les ensembles A et B, et pour tout élément y 2 /B :
X
Surj[A; B + fyg] = ff + g jf 2 Surj[AnC ; B] et g 2 Fonct[C ; fyg]g:
C A

Démonstration. 

Théorème 23. f : A ¡! B est bijective si et seulement si f est à la fois injective et

surjective. Autrement dit :
Bij[A; B] = Inj[A; B] \ Surj[A; B] (32)

Démonstration. 

Proposition 24. Lorsque jAj = jB j, on a Bij[A; B] = Inj[A; B] = Surj[A; B].

Démonstration. 

Proposition 25. Pour toute fonction f : A ¡! B, la fonction

(
P[A] ¡! P[B]
f :
+
C 7¡! f +(C) := ff (x)j x 2 C g
vérifie :
a) f + est une injection si f est une injection,
b) f + est une surjection si f est une surjection,
c) f + est une bijection si f est une bijection.

Démonstration. 

Proposition 26. Pour toute fonction f : A ¡! B,

(
P[B] ¡! P[A]
f ¡:
D 7¡! f ¡(D) := fx 2 Ajf (x) 2 Dg
vérifie :
a) f ¡ est une surjection si f est une injection,
b) f ¡ est une injection si f est une surjection,
c) f ¡ est une bijection si f est une bijection (en fait, dans cette situation c'est l'inverse
de f + ).

Démonstration. 

16
3 Compter les éléments d'un ensemble
Lorsqu'on veut calculer la dérivée d'une fonction, le problème se décompose en un ou des
problèmes plus simples, selon que la fonction à dériver est la somme, le produit, ou encore
le composé de deux fonctions plus simples. Il en est souvent de même pour l' énumération
des éléments d'un ensemble A. Le problème donné se décompose souvent en des problèmes
plus simples, selon que l'ensemble à énumérer peut se décrire en terme des constructions
de base sur les ensembles.

3.1 Le principe d'addition

Théorème 27. Si A et B sont des ensembles finis, respectivement de cardinal n et k, alors

jA + B j = jAj + jB j = n + k (33)
Plus généralement, Si fAigi2I est une famille finie d'ensembles finis, respectivement de
cardinal ni, alors
X X X
Ai = jAij = ni (34)
i2I i2I i2I

Démonstration. 

3.2 Le principe de multiplication

Théorème 28. Si A et B sont des ensembles finis, respectivement de cardinal n et k, alors

jA  B j = jAj  jB j = n  k (35)
Plus généralement, Si fAigi2I est une famille finie vd'ensembles finis, respectivement de
cardinal ni, alors
Y Y Y
Ai = jAij = ni (36)
i2I i2I i2I

Démonstration. 

Corollaire 29. Le cardinal de la puissance cartésienne n-ième d'un ensemble fini B de

cardinal k est :
jB nj = jB jn = k n (37)

3.3 Cardinal de l'ensemble P[E]

On cherche à compter les éléments de l'ensemble P[E], pour un ensemble E de cardinal n.
Commençons par observer le fait suivant :

Lemme 30. Si E et E 0 sont deux ensembles de même cardinal, alors P[E] et P[E 0] sont
également de même cardinal. Autrement dit :
jE j = jE 0j =) jP[E]j = jP[E 0]j (38)

Démonstration. 

Ainsi, pour un ensemble E de cardinal n, le cardinal de P[E] est une fonction de n, et

on dénote p(n) ce nombre d'éléments. Notre objectif est donc de trouver une formule pour
p(n) := jP[E]j. Observons le fait suivant :

17
Proposition 31. Quel que soit les ensembles disjoints E1 et E2 :
i. la fonction 
P[E1 + E2] ¡!
~ P[E1]  P[AE2]
: (39)
B 7¡! (B \ E1; B \ E2)
est bijective,
ii. si jE1j = n1 , jE2j = n2 , alors
p(n1 + n2) = p(n1)  p(n2): (40)

Démonstration. 

Théorème 32. Pour un ensemble fini E de cardinal n, l'ensemble P[E] est de cardinal 2n.
jP[E]j = 2jE j = 2n (41)

Démonstration. 

Corollaire 33. Si jAj=n et jB j=k, alors le nombre de relations de A vers B est égal à
2nk.
jRel[A; B]j = 2jAjjB j = 2nk (42)

Démonstration. Par définition Rel[A; B] := P[A  B]. Ainsi

jRel[A; B]j = jP[A  B]j = 2jAB j = 2jAjjB j = 2nk: 

3.4 Cardinaux des ensembles Fonct[A; B], Inj[A; B] et Bij[A; B].

Théorème 34. Si A et B sont des ensembles finis, respectivement de cardinal n et k, alors

jFonct[A; B]j = jB jjAj = k n: (43)

Démonstration. 

Remarque. Rapelons que lorsque A=[n], une fonction f: [n] ¡! B est encore appelée un
arrangement avec répétition de n objets pris dans B.
! Ainsi Fonct[[n]; B] est l'ensemble des arrangements avec répétition de n objets pris
dans B.
! Par suite, jFonct[[n]; B]j = jB jn est le nombre d'arrangements avec répétition de n
objets pris dans B.

Définition. Pour des entiers positifs n et k, on a les notions de :

Factoriel.
n! := n
(n ¡ 1)


2
1 avec 0! = 1:
Factoriel décroissante.
t(k): =t
(t ¡ 1)


(t ¡ k + 1); pour t une variable quelconque.

Factorielle croissante.
t(k): =t
(t + 1)


(t + k ¡ 1); pour t une variable quelconque.

18
 Coefficient binomial.  
n n!
:= :
k k!(n ¡ k)!

Théorème 35. Si A et B sont des ensembles finis, respectivement de cardinal n et k, alors

jInj[A; B]j = jB j(jAj) = k(n) (44)

Démonstration. 

Remarque. Rapelons que lorsque A=[n], une fonction injective f : [n] ¡! B est encore
appelée un arrangement sans répétition de n objets pris dans B.
! Ainsi Inj[[n]; B] est l'ensemble des arrangements sans répétition de n objets pris
dans B.
! Par suite, jInj([n]; B)j = jB j(n) est le nombre d'arrangements sans répétition de n
objets pris dans B.

Corollaire 36. Si A et B sont des ensembles finis de même cardinal n alors

jBij[A; B]j = n(n) = n! (45)
En particulier,
jS[A]j = jAj! = n! (46)

Démonstration. 

3.5 Cardinal de l'ensemble Pk[E]

 
Théorème 37. Pour un ensemble fini E de cardinal n, Pk[E] est de cardinal n
k
:
   
jE j n
jPk[E]j = = : (47)
k k

Démonstration. 

Corollaire 38. Pour tout n 2 N, on a :

n  
X n
= 2n: (48)
k
k=0

Démonstration. 

Proposition 39. Pour tout n 2 N , on a :

i.
n
X  
n
(¡1)k = 0: (49)
k
k=0
ii.
n
X  
n
k = n2n¡1: (50)
k
k=1
3.6 Le principe des tiroirs
Le principe des tiroirs (ou principe des pigeons ou principe de Dirichlet) facilite souvent
l'analyse d'une situation complexe. Dans sa version la plus simple, il est formulé en disant
que :

19
Principe des tiroirs. Si n  objets  sont  placés  dans k  boîtes , avec n > k ,alors
il y a au moins une boîte contenant plus d'un objet.

On gagne à reformuler ce principê dans le langage de la théorie des ensembles. Les n

objets dont il est question sont les n éléments d'un ensemble A. Les k  boîtes  sont les k
éléments d'un ensemble B, et  placer  ces objets dans les boîtes, consiste simplement à
choisir une fonction f : A ¡! B. On interprète donc f (x)= y comme signifiant que l'objet
x a été placé dans la boîte y. Le contenu d'une boîte y est la fibre de f en y. Le principe
des tiroirs devient donc :

Théorème 40. Si jAj est plus grand que jB j, alors pour toute fonction f : A ¡! B, on a
au moins un élément y de B pour lequel jf ¡(fyg)j>1.

Démonstration. 

3.7 Le principe d'inclusion-exclusion

Le principe d'inclusion-exclusion permet de calculer indirectement le cardinal de certains
ensembles. En particulier, il va nous permettre, dans la sous-section suivante, de calculer
le cardinal de l'ensemble Surj[A; B] des surjections de A dans B. Dans sa version la plus
simple, le principe d'inclusion-exclusion prend la forme suivante.

Proposition 41. Si A est un sous-ensemble d'un ensemble fini E, alors

jA j = jE j ¡ jAj: (51)

Démonstration. Le résultat découle du principe d'addition. En effet, si A est un sous-

ensemble de E, on a E = A + A: Ainsi jE j = jAj + jA j, d'où jA j = jE j ¡ jAj. 

Remarque. Par le principe d'inclusion-exclusion, on obtient donc indirectement le car-

dinal de A via le calcul du nombre d'éléments de A.

Corollaire 42. Si A et B sont deux ensembles finis, alors

jA [ B j = jAj + jB j ¡ jA \ B j (52)

Démonstration. En effet, de la decomposition disjointe

A [ B = (An(A \ B)) + (B n(A \ B)) + (A \ B);
on tire, par le principe d'addition, que
jA [ B j = jAn(A \ B)j + jB n(A \ B)j + jA \ B j:
Or, par le principe d'inclusion-exclusion
jAn(A \ B)j = jAj ¡ jA \ B j et jB n(A \ B)j = jB j ¡ jA \ B j;
donc :
jA [ B j = jAj ¡ jA \ B j + jB j ¡ jA \ B j + jA \ B j = jAj + jB j ¡ jA \ B j: 

Remarque. Observons que pour des sous-ensembles quelconques A, B, et C de E on a :

jA \ B
 j = jE j ¡ jAj ¡ jB j + jA \ B j:

jA \ B
 \ C j = jE j ¡ jAj ¡ jB j ¡ jC j + jA \ B j + jA \ C j + jB \ C j ¡ jA \ B \ C j:

Ainsi, dans sa forme générale, le principe d'inclusion-exclusion est :

20
Théorème 43. Si E est un ensemble fini et fAigi2I une famille finie de sous-ensembles
de E, on a :
\ jI j
X X \

Ai = (¡1)k Aj (53)
i2I k=0 J 2Pk(I) j 2J

Démonstration. Par recurrence sur jI j. 

Remarque. Observons que, si I = [n], le principe d'inclusion-exclusion s'écrit :
n
\ n
X X \
Ai = (¡1)` Aj ;
i=1 `=0 J 2P`([n]) j 2J

ou encore plus explicitement :

n
\ n
X X X
Ai = jE j ¡ jAij + jAi \ Aj j ¡ jAi \ Aj \ Ak j +
i=1 i=1 (i;j)2P2([n]) (i;j ;k)2P3([n])
X X
+ jAi \ Aj \ Ak \ A`j ¡ jAi \ Aj \ Ak \ A` \ Amj
(i;j ;k;`)2P4([n]) (i;j ;k;`;m)2P5([n])
+ ::: + (¡1)n jA1 \


\ Anj:

Remarque.
! L'une des formes typiques d'utilisation du principe d'inclusion-exclusion correspond
au cas où les sous-ensembles Ai sont décrits via des propriétés Pi :
Ai := fx 2 E jPi(x)g
Le principe d'inclusion-exclusion permet alors d'énumérer l'ensemble des éléments
de E qui n'ont aucune des propriétés Pi.
! Pour illustrer ce type de situation, comptons le nombre d'entiers entre 1 et 1000 qui
ne sont divisibles ni par 5, ni par 6, ni par 8.
¡ Posons : E = [1000]; A = fa 2 E tel que 5|ag; B = fa 2 E tel que 6|ag;
C = fa 2 E tel que 8|ag. Nous cherchons donc le cardinal de A \ B
 \ C . Par
le principe d'inclusion-exclusion, on a :
jA \ B
 \ C j = jE j ¡ jAj ¡ jB j ¡ jC j + jA \ B j + jA \ C j + jB \ C j ¡ jA \ B \ C j:

¡ Observonsquele nombre d'entiers n qui sont divisibles à la fois par k1; k2; :::,
n
et km est m , où m est le plus petit commun multiple de k1; k2; : :: ; km.
Ici bxc dénote la partie entière de x.
j k j k j k
1000 1000 1000
¡ Ainsi : jAj = = 200, jB j = = 166, jC j = = 125,
j k5 j 6k j8 k
1000 1000 1000
jA \ B j = 5  6 = 33, jA \ C j = 5  8 = 25, jB \ C j = 3  8 = 41,
j k
1000
jAj = 5  3  8 = 8.

¡ D'où jA \ B
 \ C j = 1000 ¡ 200 ¡ 166 ¡ 125 + 33 + 25 + 41 ¡ 8 = 600:

3.8 Cardinal de l'ensemble Surj[A; B]

Fort du principe d'inclusion-exclusion, nous sommes maintenant en mesure de déterminer
le cardinal de Surj(A; B), le nombre de surjections de A vers B.

21
Théorème 44. Pour des ensembles finis A et B, respectivement de cardinal n et k,
jBj
X   k
X  
jB j k
jSurj[A; B]j = (¡1) j (jB j ¡ j) =
jAj
(¡1) j (k ¡ j)n (54)
j j
j=0 j =0

Démonstration. 

4 Multi-sous-ensembles et monômes.
La notion de  multi-sous-ensemble  apparaît lorsqu'on désire permettre (contrairement
aux principes de la théorie des ensembles) la répétition d'éléments d'un ensemble.

4.1 Définition et propriétés de base

Pour atteindre cet objectif, on procède comme suit. Pour chaque élément x, d'un ensemble
fini A donné de cardinal k, on se donne un entier naturel x. C'est la multiplicité de x.

Définition. (Multi-sous-ensemble) Un multi-sous-ensemble de A est un couple (A;

) d'un ensemble A avec une fonction  : A ¡! N qui associe à chaque élément de A une
multiplicité.
Si la multiplicité d'un élément est 0, alors on considère qu'il ne fait pas partie du multi-
sous-ensemble.
Le multi cardinal de (A; ) est la somme des multiplicités de ses éléments :
X
jAj := x; x := (x): (55)
x2A
Notation.
! On dénote par Mn[A] l'ensemble des multi-sous-ensembles de A de multi cardinal n.
! Pour présenter agréablement les multi-sous-ensembles de A, on se sert d'une nota-
tion sous forme de monôme. Pour ce faire, on considère les éléments de A comme
des variables commutatives, c.-à-d. : xy = yx, si x et y sont dans A. On associe
alors à un multi-sous-ensemble (A; ), le monôme
Y
x(x):
x2A

L'exposant de x est donc sa multiplicité dans le multi-sous-ensemble, et le multi

cardinal jAj est le degré du monôme.
! Ainsi, les 7 multi-sous-ensembles de multi cardinal 6 de l'ensemble A=fa; bg cor-
respondent aux 7 monômes de degré 6 de l'ensemble :
M6[A] = fa6; a 5b; a4 b2; a3 b3; a2 b4; ab5; b6g:

Remarque.
! Dans le cas A = [k], un monôme est caractérisé par un vecteur d'exposants
v =(1; 2; :::; k) 2 Nk , avec norme
kv k1 := 1 + 2 + ::: + k = n; (avec i > 0): (56)

! Considèrons l'ensemble Compk[n] défini par :

Compk[n] := fv 2 (N)k tel que kv k1 = ng: (57)

22
 ! Compk(n) est l'ensemble des compositions de n en k parts (non nulles). Autrement
dit, ses éléments sont les solutions de l' équation
1 + 2 + ::: + k = n; (avec i > 0): (58)

Proposition 45.
i. On a une bijection entre Compk[n] et Pk¡1[n ¡ 1].
 
n¡1
ii. jCompk[n]j = k¡1
.

Démonstration. 

Proposition 46.
i. On a une bijection entre Mk[n]) et Compk[n + k ¡ 1] .
 
n+k ¡1
ii. jMk[n]j = k
.

Démonstration. 

Définition. (Coefficient binomial 

de 2-ième sorte) On appelle coefficient binomial
de 2-ième sorte l'entier naturel n + kk ¡ 1 .

4.2 Fonctions et opérations

Définition. (Bijection) Une fonction f : A ¡! B est une bijection entre deux multi-sous-
ensembles (A; ) et (B ; ) si f est bijective et pour tout x 2 A, (f(x)) = (x).

Proposition 47. Deux multi-sous-ensembles ont même multi cardinal, si et seulement si

il existe une bijection entre les deux.

Démonstration. 

Les opérations sur les ensembles s'étendent aux multi-sous-ensembles de façon assez
directe. En fait, la situation est même parfois plus simple. Ainsi, la somme est plus naturelle
dans ce contexte, puisqu'on pose
(A; ) + (B ; ) := (A [ B;  ) (59)
avec la fonction de multiplicité  définie comme
8
>
< (x) + (x) si x 2 A \ B ;
 (x) := (x) si x 2 A et x 2 / B; (60)
>
: (x) si x 2
/ A et x 2 B:

D'autre part, le produit cartésien se définit en posant

(A; )  (B ; ) := (A  B;  ) (61)
avec la fonction de multiplicité  définie comme
 (x; y) := (x)(y): (62)

Proposition 48. Si (A; ) et (B; ) sont des multi-sous ensembles finis, alors on a les
égalités suivantes :
i. jA + B j = jAj + jB j,
ii. jA  B j = jAj  jB j

23
Démonstration. 

Remarque. Bien entendu les définitions de somme généralisée et produit cartésien géné-
ralisé s'adaptent de façon analogue au contexte des multi-sous-ensembles.

5 Séries génératrices
Lorsqu'on cherche à trouver une formule pour le nombre an de structures construites sur
un ensemble à n éléments, des outils adéquats facilitent grandement P le travail. L'objectif
visé par l'introduction de la série génératrice (ordinaire) n>0 anz n, et de la série
P zn
génératrice exponentielle n>0 an n! , d'une suite de nombres (an)n2N est de faciliter
ces manipulations. En effet, un phénomène fascinant se produit alors, puisque des calculs
très classiques sur les séries (et les fonctions associées) correspondent à des manipulations
combinatoires très naturelles. Nous aurons plusieurs fois l'occasion de le constater, mais ce
n'est qu'au chapitre sur la théorie des  espèces de structures  qu'on pourra véritablement
bien mettre en évidence cette relation intime entre l'algèbre des fonctions et celle des
opérations combinatoires.
Pour cette approche, l'un des principes fondamentaux est le critère d' égalité est que
deux séries ne peuvent être égales que si leurs coefficients coïncident. Autrement dit,
X X
anz n = bnz n si et seulement si an = bn; pour tout n 2 N.
n>0 n>0

Lorsque le développement en série de Taylor d'une fonction f(z) (sur les réels) est f (z) =
P P zn
n>0 anz (resp. f(z) = n>0 an n! ), on dit que f(z) est la fonction généraltrice
n

ordinaire (resp. la fonction génératrice exponentielle) de la suite de nombres (an)n2N. Pour

bien mettre en évidence l'intérêt de travailler avec de tels outils, nous allons commencer
par étudier un exemple.

Exemple. Considérons l'identité bien connue e(s+t)z = esz :etz : En développant en série
chaque membre de l' égalité, on obtient le calcul :
! !
X zn X zn X zn
(s + t) n = s n t n
n! n! n!
n>0 n>0 n>0
n  
!
X X n k n¡k z n
= s t :
k n!
n>0 k=0

Selon le critère d'égalité de séries, on doit a l'identité du binôme de Newton

n  
!
X n
(s + t)n = skt n¡k : (63)
k
k=0

Pour faciliter les calculs à venir,nous rappelons également que :

X zn
(1 + z)t = t(n) : (64)
n!
n>0

5.1 Opérations sur les séries génératrices.

Les séries que nous considérons ici sont des séries formelles, c'est-à-dire que les préoc-
cupations habituelles (convergence, etc) de l'Analyse ne s'appliquent pas. Le point de vue
est celui de l'Algèbre, et nous nous préoccupons plutôt des manipulations qu'il est possible
d'effectuer sur ces séries (qu'on conçoit plus comme étant des polynômes de degré infini).

24
 P P
Étant données deux séries formelles f(z) = n>0 anz
n et g(z) = n>0 bnz
n, on définit
les opérations :
La somme.
X
f (z) + g(z) := (an + bn)z n: (65)
n>0

Le produit de Cauchy.
n
!
X X
f (z)g(z) := akbn¡k z n (66)
n>0 k=0

Dans le cas exponentiel, on a plutôt :

n  
!
X X n zn
f(z)g(z) := akbn¡k : (67)
k n!
n>0 k=0

La puissance n-ième.
(
f (z)(f(z))n¡1 si n > 0
(f (z))n := (68)
1 si n = 0:
La dérivée.
X
f 0(z) := (n + 1)an+1z n: (69)
n>0

Dans le cas exponentiel , on a :

X zn
f 0(z) := an+1 (70)
n!
n>0
L'intégrale. Z z X an n+1
f (t)dt := z : (71)
0 n+1
n>0

Dans le cas exponentiel , on a :

Z z X z n+1
f (t)dt := an (72)
0 (n + 1)!
n>0

L'inverse. pour le produit définie dans le cas où a0 = 1 dans f (z)

X n¡1
X
(f (z))¡1 := cnz n avec cn = ckan¡k: (73)
n>0 k=0

La substitution. définie que lorsque g(0) = b0 = 0

X
f (g(z)): = an(g(z))n (74)
n>0

25