Les applications.

Brahim ABBACI
31 octobre 2023

1 Notion d’application.
Définition 1.1 Soient E et F deux ensembles. Une application (ou fonction) f de E dans F
(notée f : E → F ) est un procédé qui associe, à chaque élément x de E, un unique élément
y de F , que l’on note f (x) et que l’on appelle image de x par f . L’ensemble E est appelé
ensemble de départ ou source de f et l’ensemble F est appelé ensemble d’arrivée ou but de f .
Si y est un élément de F , un antécédent de y par f est un élément x de E tel que f (x) = y.
Pour définir une application f , on utilise parfois la notation f : E → F ; x 7→ f (x), ce qui
est pratique quand f (x) est donné par une formule en la variable x.

Exemple 1.1 1. Soit E un ensemble. Il existe une unique application ∅ → E et on l’appelle

l’application vide. Il n’existe aucune application E → ∅, à moins que E soit vide.
2. On appelle identité de E l’application idE : E → E; x 7→ idE (x) = x.
3. Si A ⊂ E est une partie de E, on appelle injection canonique de A dans E l’application
iA : A → E; x 7→ iA (x) = x.
4. Si F est un autre ensemble, l’application pr1 : E × F → E; (x, y) 7→ pr1 (x, y) = x
(respectivement pr2 : E × F → F ; (x, y) 7→ pr2 (x, y) = y) est appelée projection sur le
premier (respectivement deuxième) facteur.
Remarque 1.1 Attention, une application n’est pas toujours définie par une formule expli-
cite. Par exemple, l’application f : N r {0} → N r {0} qui à un entier n ≥ 1 associe le n-ième
nombre premier.
Définition 1.2 Soient E, F des ensembles et f : E → F une application. Le graphe de f
est la partie Gr(f ) de E × F constituée des couples (x, f (x)) ou x ∈ E, autrement dit
Gr(f ) := {(x, y) ∈ E × F ; y = f (x)} = {(x, f (x)); x ∈ E}.
Dans tous les cas, il est important de souligner que la donnée de l’ensemble de départ et
de l’ensemble d’arrivée font partie de la donnée d’une application, ce qui se traduit par la
propriété suivante :
Propriété 1.1 Deux applications sont égales si et seulement si elles ont même ensemble de
départ, même ensemble d’arrivée, et même graphe.
L’ensemble des applications de E dans F est noté F E . Cette notation correspond au point
de vue suivant : la donnée d’une application f : {1, 2} → R équivaut à la donnée du couple
(f (1), f (2)), ce qui signifie que R{1,2} s’identifie à R2 .

1
2 Image directe, image réciproque.
Définition 2.1 Soit f : E → F une application.
— Si A est une partie de E, on appelle image directe de A par f , et on note f (A), le
sous-ensemble de F défini par :
f (A) := {y ∈ F ; ∃x ∈ A, y = f (x)} = {f (x); x ∈ A}.
On appelle image de f , et on note Imf , l’ensemble f (E).
— Si B est une partie de F , on appelle image réciproque de B par f , et on note f −1 (B), le
sous-ensemble de E défini par :
f −1 (B) := {x ∈ E; f (x) ∈ B}.
Attention ! La notation f −1 (A) prête à confusion : on dirait que l’on a « inversé » l’appli-
cation f , ce qui n’est pas du tout le cas. On prendra donc bien garde à ne pas confondre
l’application f −1 : P(F ) → P(E) ainsi définie (qui existe pour toute fonction f ) avec la
bijection réciproque f −1 : F → E (qui n’existe que si f est bijective).
Exercice 2.1 On considère l’application f : R → R définie par : f (x) = |x|.
1. Déterminer les images directes : f ({−1, 2}), f ([−3, −1]) et f ([−3, 1]).
2. Déterminer les images réciproques : f −1 ({4}) f −1 ({−1}) et f −1 ([−1, 4]).
Propriétés 2.1 Soit f : E → F une application.
1. Pour toute partie A de E, on a A ⊂ f −1 (f (A)).
2. Pour toute partie B de F , on a f (f −1 (B)) ⊂ B.

3 Composition des applications.

Définition 3.1 Soient E, F , G des ensembles, f : E → F et g : F → G des applications.
La composée de f est g, notée g ◦ f (ce qui se lit « g rond f »), est l’application de E dans
G définie par (g ◦ f )(x) = g(f (x)) pour tout x ∈ E.
On ne peut donc composer f et g que si l’ensemble de départ de g est égal à l’ensemble
d’arrivée de f .
Exemples 3.1 1. Si f : E → F est une application, alors f ◦ idE = f et idF ◦ f = f .
2. Soient f :]0, +∞[→]0, +∞[ et g :]0, +∞[→ R les applications données par x 7→ f (x) = 1
x
et x 7→ g(x) = x−1
x+1
. Alors on a
(1/x) − 1 1−x
(g ◦ f )(x) = g(1/x) = = = −g(x) pour tout x > 0.
(1/x) + 1 1+x
Proposition 3.1 Soient E, F , G, H des ensembles et f : E → F , g : F → G, h : G → H
des applications. Alors on a h ◦ (g ◦ f ) = (h ◦ g) ◦ f et cette application se note h ◦ g ◦ f .
Preuve. Par définition de la composition des applications, il vient
(h ◦ (g ◦ f )) (x) = h ((g ◦ f )(x)) = h (g(f (x)))
et
((h ◦ g) ◦ f ) (x) = (h ◦ g)(f (x)) = h (g(f (x)))
pour tout x ∈ E, d’où l’égalité cherchée.

2
4 Restriction, prolongement.
Définition 4.1 Soit f : E → F une application, et soit A une partie de E. La restriction de
f à A, notée f|A , est l’application de A dans F qui à tout élément x de A associe l’élément
f (x) de F .

La restriction de f à A est donc l’application qui prend les mêmes valeurs que f , mais avec
A comme ensemble de départ au lieu de E. On observe que f|A est la composée de l’injection
canonique iA : A → E et de f , autrement dit f|A = f ◦ iA . Le graphe de f|A se déduit donc
du graphe de f par la formule : Gf|A = Gf ∩ (A × F ).

Définition 4.2 Soit f : E → F une application, et soit B une partie de F contenant l’image
Imf := f (E) de f . La restriction au but de f à B, notée f |B , est l’application de E dans B
qui à tout élément x de E associe l’élément f (x) de B.
On obtient alors une application qui a même ensemble de départ et même graphe, mais pas
même ensemble d’arrivée.
Définition 4.3 Soient deux applications f : E →F et g : A → B. On dit que f est un
prolongement de g si A est une partie de E, B est une partie de F , et Gg ⊂ Gf .
On a donc en particulier f (x) = g(x) pour tout x ∈ A.

5 Injection, surjection et bijection.

Soit f : E → F une application. On est amené naturellement à se poser deux questions :
la donnée de f (x) permet-elle de retrouver x ? Un élément de F est-il l’image par f d’un
élément de E ? Plusieurs cas peuvent se présenter.
Définition 5.1 Une application f : E → F est injective (ou est une injection) si pour tous
x, y ∈ E, l’égalité f (x) = f (y) entraîne x = y. En d’autres termes tout élément de F a au
plus un antécédent ou encore est l’image d’au plus un élément de E.
Exemples 5.1 1. Les applications f : R → R ; x 7→ f (x) = x + 2 et g : R∗+ → R ;
x 7→ g(x) = ln(x) sont injectives.
2. Les applications h : R → R ; x 7→ h(x) = x2 et ` : R → R ; x 7→ `(x) = sin x ne sont
pas injectives, par contre les restrictions h|R+ : R+ → R de h et `|I : I = [− π2 , π2 ] → R de
` sont injectives. On voit donc qu’il faut bien préciser les ensembles de départ et d’arrivée
pour parler d’injectivité.

Définition 5.2 Une application f : E → F est surjective (ou est une surjection) si, pour
tout y ∈ F il existe x ∈ E tel que y = f (x). En d’autres termes tout élément de F a au
moins un antécédent dans E.

Exemples 5.2 1. La fonction f : R → R définie par f (x) = x + 2 est surjective.

2. La fonction g : R → R définie par g(x) = x2 n’est pas surjective, par contre sa restriction
au but g |R+ : R → R+ est surjective. On voit donc qu’il faut bien préciser les ensembles de
départ et d’arrivée pour parler de surjectivité.

3
Définition 5.3 Une application f : E → F est bijective (ou est une bijection) si elle est à la
fois injective et surjective. En d’autres termes tout élément de F a exactement un antécédent.
Exemples 5.3 1. La fonction f : R → R donnée par x 7→ f (x) = x + 2 est une bijection.
2. De même la fonction x 7→ ln(x) est une bijection de R∗+ dans R.
Lorsque f : E → F est une bijection, on peut définir une application de F dans E par la loi
qui à y associe l’unique élément x ∈ E tel que y = f (x) (le fait que f soit bijective garantit
exactement l’existence et l’unicité d’un tel x).
Définition 5.4 On appelle bijection réciproque d’une bijection f : E → F et on note f −1 :
F → E, l’application caractérisée par : x = f −1 (y) ⇐⇒ y = f (x). Il est clair que f −1 est
aussi une bijection.
Exemples 5.4 1. La bijection réciproque de f : R → R ; x 7→ f (x) = x + 2 est donnée par
f −1 : R → R ; x 7→ f −1 (x) = x − 2.
2. La bijection réciproque de x 7→ ln(x) de R∗+ dans R est la fonction x 7→ ex de R dans R∗+ .
3. La symétrie par rapport à un point du plan est sa propre bijection réciproque.
Proposition 5.1 Soit f : E → F une application. Si f est bijective, alors f ◦ f −1 = idF et
f −1 ◦ f = idE .
Preuve. Soit y ∈ F . Alors f −1 (y) est l’unique x ∈ E tel que f (x) = y, donc on a :
f (f −1 (y)) = f (x) = y, c’est-a-dire f ◦ f −1 = idF . Soit x ∈ E. Alors f −1 (f (x)) est l’unique
antécédent de f (x) par f , donc est égal à x, c’est-a-dire f −1 ◦ f = idE .
Remarque 5.1 Si f : E → F est bijective, et si B est une partie de F , alors l’image
réciproque de B par f est égale à l’image directe de B par f −1 . La notation f −1 (B) peut
donc être utilisée sans ambiguïté.
Théorème 5.1 Soient f : E → F et g : F → E deux applications telles que g ◦ f = idE et
f ◦ g = idF . Alors f et g sont bijectives et réciproques l’une de l’autre.
Preuve. Par symétrie du problème, il suffit de montrer que f est bijective et que g est sa
réciproque. Montrons que f est injective : soient x et x0 dans E tels que f (x) = f (x0 ), alors
g(f (x)) = g(f (x0 )), donc x = x0 puisque g ◦ f = idE . Montrons que f est surjective : soit
y ∈ F , alors f (g(y)) = y, ce qui montre que g(y) est un antécédent de y par l’application f .
On a donc bien montré que f est bijective, et que g est sa réciproque car, f (g(y)) = y ⇐⇒
g(y) = f −1 (y) par définition de f −1 .
Corollaire 5.1 Si f : E → F est bijective, alors f −1 : F → E est également bijective, et on
a (f −1 )−1 = f .
Preuve. En effet, on sait que f −1 ◦ f = idE et f ◦ f −1 = idF , donc d’après le théorème
précédent f −1 est bijective, de réciproque f
Proposition 5.2 Soient f : E → F et g : F → G des bijections. Alors l’application g ◦ f
est bijective et sa réciproque est (g ◦ f )−1 = f −1 ◦ g −1 .
. Preuve. D’après la proposition précédente, il existe u : F → E et v : G → F telles que
f ◦ u = idF , u ◦ f = idE , g ◦ v = idG et v ◦ g = idF . On a (g ◦ f ) ◦ (u ◦ v) = g ◦ (f ◦ u) ◦ v =
g ◦ idF ◦ v = g ◦ v = idG et (u ◦ v) ◦ (g ◦ f ) = u ◦ (v ◦ g) ◦ f = u ◦ idF ◦ f = u ◦ f = idE . On
en déduit, également d’après la proposition précédente, que l’application g ◦ f est bijective
et que l’on a (g ◦ f )−1 = u ◦ v = f −1 ◦ g −1 .

4
6 Combinatoire, dénombrements.
6.1 Ensembles finis, ensembles infinis.
Définition 6.1 Soit E un ensemble. On dit que E est fini s’il est vide ou s’il existe p ∈ Nr{0}
et une bijection de J1, pK := {1, 2, . . . , p} sur E. On dit que E est infini si E n’est pas fini.

Les ensembles finis de référence sont donc ∅ et les J1, pK où p est un élément non nul de N.
Nous allons utiliser la notion de bijection pour définir le cardinal d’un ensemble fini. Intui-
tivement, deux ensembles ont le même nombre d’éléments si et seulement si on peut définir
une bijection entre ces ensembles. Les propositions qui suivent formalisent cette intuition.
Théorème 6.1 Soient p, q ∈ N∗ deux entiers naturels non nuls.
1. Il existe une application injective de J1, pK vers J1, qK si et seulement si p 6 q.
2. Il existe une application surjective de J1, pK vers J1, qK si et seulement si p > q.
3. Il existe une application bijective de J1, pK vers J1, qK si et seulement si p = q.
La démonstration rigoureuse de ce théorème est technique. On se contentera pour l’instant
de remarquer que les implications de droite à gauche sont faciles à prouver.
Corollaire 6.1 Soit E un ensemble fini et non vide. Il existe un unique élément p ∈ N r {0}
pour lequel il existe une bijection de J1, pK sur E.
Preuve. Comme E est un ensemble fini non vide, d’après la définition, il existe p ∈ Nr{0} et
une bijection de J1, pK sur E. Pour montrer que p est unique on va supposer qu’il existe deux
éléments p, q ∈ N r {0} pour lesquels il existe des bijections f : J1, pK → E et g : J1, qK → E.
Alors, l’application g −1 ◦ f est une bijection de J1, pK sur J1, qK. Le théorème ci-dessus assure
donc que p = q. Donc p est bien unique.
Définition 6.2 Soit E un ensemble fini et non vide. L’unique élément p ∈ N r {0} pour
lequel il existe une bijection de J1, pK sur E est appelé le cardinal de E. Il est noté card(E).
En outre, on pose card(∅) = 0.
Les ensembles finis vérifient de nombreuses propriétés très intéressantes.
Théorème 6.2 Soit p ∈ N r {0} et f : J1, pK → J1, pK une application. Les assertions
suivantes sont équivalentes :
(i) f est bijective ;
(ii) f est injective ;
(iii) f est surjective.
Preuve. Par définition, (i) implique (ii) et (iii). Prouvons que (ii) implique (iii), par l’absurde.
Supposons que f soit injective mais pas surjective, il existe alors un élément k de J1, pK qui
n’est pas dans l’image de f . On définit alors g : J1, pK → J1, p − 1K par g(i) = f (i) si f (i) < k
et g(i) = f (i) − 1 si f (i) > k. L’application ainsi définie est injective et, d’après le théorème
2.1, on devrait avoir p 6 p − 1, ce qui est impossible. Comme une application injective et
surjective est bijective, on a obtenu aussi que (ii) implique (i). L’implication de (iii) vers (ii)
se montre de façon similaire, en supposant qu’un élément a deux antécédents.
Les théorèmes 2.1 et 2.3 se généralisent facilement aux ensembles fini. Les énoncés cor-
respondants sont les suivants.

5
Corollaire 6.2 Soient E et F deux ensembles finis non-vides de cardinaux respectifs p et q.
1. Il existe une application injective de E vers F si et seulement si p 6 q.
2. Il existe une application surjective de E vers F si et seulement si p > q.
3. Il existe une application bijective de E sur F si et seulement si p = q.
Corollaire 6.3 Soient E un ensemble fini non-vide et f : E → E une application. Les
assertions suivantes sont équivalentes :
(i) f est bijective ;
(ii) f est injective ;
(iii) f est surjective.
Remarque. Le corollaire 2.3 est faux pour les ensembles infinis. Il permet d’ailleurs de
démontrer qu’un ensemble est infini. Par exemple, l’application s : N → N, n 7→ n + 1 est
injective, mais pas surjective. On en déduit que N est infini.
Corollaire 6.4 Soient E et F deux ensembles finis non-vides de même cardinal et f : E → F
une application. Les assertions suivantes sont équivalentes :
(i) f est bijective ;
(ii) f est injective ;
(iii) f est surjective.
Proposition 6.1 Soit E un ensemble fini et F un sous-ensemble de E. Alors, F est fini et
card(F ) 6 card(E).
La preuve se fait par récurrence sur le cardinal de E. Elle ressemble aux preuves précédentes
et est laissée en exercice.
Soit E un sous-ensemble de N. On appelle majorant de E dans N un nombre M ∈ N tel
que n 6 M pour tout n dans E. On dit que E est majoré s’il existe un majorant.
Proposition 6.2 Une partie de N est finie si et seulement si elle est majorée.
Preuve. Si A est majorée par M , alors A est inclus dans J0, M K, donc est fini. Pour prouver
la réciproque, on utilise un raisonnement par contraposée : A non majorée implique A infini.
On construit par récurrence une suite strictement croissante d’éléments de A. On a donc un
ensemble infini inclus dans A.

6.2 Dénombrement.
Proposition 6.3 Soient E et F deux ensembles finis.
1. L’ensemble E ∪ F est fini et card(E ∪ F ) = card(E) + card(F ) − card(E ∩ F ).
2. L’ensemble E × F est fini et card(E × F ) = card(E) × card(F ).
Preuve. 1. On suppose d’abord E et F non vides (la formule est vraie si l’un est vide) et
disjoints. Dans ce cas, à partir des bijections de J1, card(E)K vers E et de J1, card(F )K vers
F , on peut construire une bijection de J1, card(E) + card(F )K vers E ∪ F . Ceci prouve la
formule dans le cas où E et F sont disjoints. Pour E ∩ F non vide, on décompose E ∪ F en
(E r (E ∩ F )) ∪ (E ∩ F ) ∪ (F r (E ∩ F )). Cette décomposition de E ∪ F est constituée de trois
ensembles disjoints ; on peut donc utiliser la formule dans ce cas, et prouver le cas général.
2. On remarque que E × F est l’union de tous les E × {x} ; x ∈ F , qui sont finis, disjoints et
chacun de cardinal card(E). Cette union est composée de card(F ) termes et on peut appliquer
card(F ) fois l’égalité précédente.

6
Proposition 6.4 Soit E un ensemble de cardinal n et F un ensemble de cardinal p. Alors
le nombre d’applications de E dans F est pn .
Preuve. Une application est exactement déterminée par le choix des n images, et il y a p
possibilités pour le choix de chaque image.

Remarque 6.1 Ceci est vrai aussi pour n = 0. Ceci permet de justifier la convention 00 = 1
(il y a une unique application ∅ → ∅, de graphe vide).
Proposition 6.5 Soit E un ensemble de cardinal n. L’ensemble des parties de E est fini et
de cardinal : card(P(E)) = 2n .

Pour s’en convaincre, on peut remarquer que pour chaque élément de E, il y a deux possibi-
lités : être ou ne pas être dans un sous-ensemble A.
Preuve de la proposition. On va montrer cette proposition par récurrence sur le cardinal
n de E. Soit P la propriété portant sur les éléments de N définie par : P (n) est vraie si et
seulement si pour tout ensemble E de cardinal n on a card(P(E)) = 2n .
- Si n = 1, E = {a} est un singleton, les deux sous-ensembles de E sont ∅ et E, donc P (1)
est vraie.
- Supposons que la proposition soit vraie pour k > 1, montrons qu’alors P (k + 1) est vérifiée.
Soit E un ensemble à k + 1 éléments. Il n’est pas vide, donc il existe un éléments a ∈ E. Il y
a alors deux sortes de sous-ensembles de E :
• les sous-ensembles de E qui ne contiennent pas a, ils sont inclus dans E r {a} qui contient
k éléments. Il y a donc (par l’hypothèse de récurrence) 2k sous-ensembles de E de ce type.
• les sous-ensembles de E qui contiennent a, ils sont de la forme A = {a} ∪ B où B est
inclus dans E r {a} qui possède k éléments. Il y a donc (par l’hypothèse de récurrence) 2k
sous-ensembles de E de ce type.
Il y a donc 2k + 2k = 2k+1 sous-ensembles de E. L’ensemble des parties de E a donc pour
cardinal 2k+1 , c’est-à-dire P (k + 1) est vérifiée. On a prouvé que si card(E) = n alors
card(P(E)) = 2n .
Remarque 6.2 Pour E de cardinal n, 2n est le nombre d’applications de E dans {0, 1}.
Construire une partie A de E revient à construire une application de E dans {0, 1}, chaque
élément de E est ou n’est pas dans A.
Exemple 6.1 Sélectionner l’ensemble A constitué des nombres divisibles par 3 dans J1, 10K,
c’est associer par une application f de J1, 10K dans {0, 1} les nombres 3, 6 et 9 à 1 et les
nombres 1, 2, 4, 5, 7, 8 et 10 à 0.

6.3 Arrangements, combinaisons.

Définition 6.3 Soient E et F deux ensembles finis, de cardinaux respectifs p et n. On appelle
arrangement de p objets pris parmi n toute injection de E dans F . On note Apn le nombre de
ces injections.

Exercice 6.1 On considère les ensembles E = {A, B, C} et F = {1, 2, 3, 4}. Donner une
injection g de E dans F , c’est donner un arrangement de trois éléments pris parmi quatre.
Par exemple g(A) = 1, g(B) = 4 et g(C) = 2. Si on ordonne les éléments de l’ensemble de

7
départ, il suffit de donner les images dans le même ordre : (1; 4; 2).
1. Donner toutes les injections g de E dans F tel que g(A) = 2.
2. Existe-t-il une surjection de E dans F ? Si oui, donner un exemple d’une telle surjection.
3. Existe-t-il une injection de F dans E ? Si oui, donner un exemple d’une telle injection.
Proposition 6.6 1. Si p 6 n, alors Apn = n!
(n−p)!
= n(n − 1) · · · (n − p + 1).
2. Si p > n, alors Apn = 0.
Preuve. On peut supposer que E est l’ensemble J1, pK. Choisir une injection de E dans F
revient à choisir un premier élément dans F , puis un second (différent du premier), puis un
troisième (différents des deux premiers), etc, jusqu’à un p-ième, en retenant dans quel ordre
les éléments ont été choisis. Pour p > n, il est impossible de trouver une telle injection, car
au moins un élément de F aurait deux antécédents. Pour p 6 n, on a n choix pour l’image
de 1, puis n − 1 choix pour l’image de 2, etc, et n − p + 1 choix pour l’image de p. Ceci dit, il
y a donc n(n − 1)(n − 2) · · · (n − p + 1) injections de E dans F . Or ce nombre est aussi égal
à (n−p)!
n!
.
Exemple 6.2 Pour une course avec 8 coureurs, il y a A38 = 8 × 7 × 6 = 336 podiums
possibles (sans ex-æquo possible). La donnée d’un podium est la même donnée que celle
d’une injection de l’ensemble {1, 2, 3} dans l’ensemble A, B, C, D, E, F, G, H des coureurs
(appelés ainsi pour simplifier). Le gagnant est l’image de 1 par l’injection, le deuxième est
l’image de 2, le troisième est l’image de 3. Le fait d’avoir une injection assure bien qu’un
même coureur ne peut pas être à la fois premier et deuxième par exemple.
Définition 6.4 On appelle une permutation d’un ensemble E une bijection de E dans E.
Proposition 6.7 Si E est un ensemble fini à n éléments, il y a n! permutations de E.
Preuve. Par le corollaire 2.4, comme E est un ensemble fini, une application de E dans E
est bijective si et seulement si elle est injective. Il y a donc autant de bijections de E dans E
que d’injections de E dans E. Ce nombre est Ann = n!.
Remarque 6.3 Compter les surjections est beaucoup plus compliqué, il n’y a pas de formule
simple.
Définition 6.5 Une combinaison de pobjets pris parmi n est un sous-ensemble à p éléments
d’un ensemble à n éléments. On note p le nombre de combinaisons de p objets pris parmi
n

n. On appelle ces nombres les coefficients binomiaux.

Remarque 6.4 Contrairement à l’arrangement, l’ordre n’est  pas important. Dans certains
livres, on peut trouver la notation Cnp au lieu de la notation np .
 
Proposition 6.8 1. Si p 6 n, alors n
p
= n!
p!(n−p)!
.
 
2. Si p > n, alors n
p
= 0.
Preuve. Dans le cas p > n, la définition donne directement le résultat. Dans le cas p 6 n, on
peut compter le nombre de listes ordonnées de p éléments différents dans un ensemble E à n
éléments. Se donner une telle liste revient à se donner une injection de J1, pK dans E. Il y a
donc (n−p)!
n!
listes ordonnés de p éléments. Une autre façon de se donner une telle liste revient
à se donner un sous-ensemble à p éléments, puis à choisir un ordre parmi ces p éléments. On
a vu dans
  la proposition 2.7 qu’ilya p! ordres possibles. Le nombre de listes est donc aussi
égal à np p!. On obtient (n−p)!
n!
= np p!, ce qui donne la formule cherchée.

8
  
Exemple 6.3 Pour une course avec dix chevaux, il y a 10
3
tiercés possibles dans le désordre.
   
Proposition 6.9 1. (Symétrie) Si 0 6 p 6 n, alors n
p
= n
n−p
.
     
2. (Formule de Pascal) n+1
p+1
= n
p+1
+ n
p
.
 
3. (Binôme de Newton) ∀(a, b) ∈ R , ∀n ∈ N∗ , (a + b)n = n
ak bn−k .
2 Pn
k=0 k

Preuve. On peut bien-sur déduire la symétrie directement de la proposition précédente,

mais nous trouvons   plus instructive une démonstration en termes d’ensembles à partir de
la définition des np . Soit E un ensemble de cardinal n. L’application A 7→ {A définit une
bijection entre l’ensemble des parties de E à p éléments et l’ensemble des parties de E à n − p
éléments, d’où la formule de symétrie.
Montrons la formule de Pascal . Soit E un ensemble à n + 1 éléments, et soit a un élément
de E. Alors une partie à p + 1 éléments de E est ou bien une partie de E r {a}, ou bienune
partie de E contenant a. Or, le nombre de parties à p + 1 éléments de E r {a} est p+1 n
, et
le nombre de parties à p +  1
 éléments contenant a est égal au nombre de parties à p éléments
de E r {a}, c’est-à-dire np , d’où le résultat.
Il existe deux façons de prouver la formule du binôme. On peut faire une récurrence sur n
(il faut alors utiliser la formule de Pascal pour le passage du rang n au rang n + 1). On peut
sinon utiliser une méthode de dénombrement. On écrit (a + b)n sous la forme du produit
(a + b)(a + b) · · · (a + b). Le coefficient de ak bn−k est exactement le nombre de fois dans le
développement de ce produit où on choisit k fois le nombre a dans les parenthèses et n − k
fois le nombre b. Ce coefficient est donc lenombre
 de choix possibles de k éléments parmi n.
Or ce nombre de choix est par définition nk .