de l’équation x 1 + x 2 + · · · + x n = p, où les x i sont entiers positifs ou nuls. Le
nombre de p combinaisons avec répétitions de n éléments est
n+p−1
n−1
.
C’est aussi le nombre de rangements de n objets dans p boîtes.
Nombre de chemins sur un quadrillage
0 1
1
0
2
3
4
5
6
7
8
2 3 4 5 6 7 8 9
P 1
P 2 P 3
P 4
A
Repérons les points du plan par leurs coordonnées dans un repère (O;
→
i,
→
j) et
considérons le quadrillage formé des droites parallèles aux axes. Appelons chemin issu de O toute suite
P 0 = O, P 1 , . . . , P m de points tels que, pour tout k, le
vecteur
− − − − − − − − − − − − − − →
P k P k+1 est égal à
→
i ou à
→
j . Les coordonnées
des points P k sont donc des entiers positifs ou nuls.
La suite O, P 1 , . . . , P m définit une ligne brisée portée
par le quadrillage.
Un chemin issu de O est parfaitement déterminé
quand on connaît, pour tout k, le nombre x k de segments unité verticaux situés à l’abscisse k.
Par exemple, le chemin de O à A représenté sur la figure correspond à la suite
x 0 = x 1 = 0, x 2 = 1, x 3 = 2, x 4 = x 5 = 0, x 6 = 2, x 7 = 1, x 8 = 0, x 9 = 2 .
Soit A le point de coordonnées (p, q), où p et q sont des entiers positifs ou nuls.
Pour qu’un chemin issu de O ait le point A comme extrémité, il faut et il suffit que
l’on ait x 0 + x 1 + · · · + x p = q. Les chemins issus de O et d’extrémité A sont donc
en bijection avec les solutions de l’équation x 0 + · · · + x p = q, où x k ∈ N. D’après le
corollaire précédent, il y a
(p+1)+q−1
(p+1)−1
=
p+q
p
chemins issus de O et d’extrémité A.
Applications ayant pour image leur ensemble d'arrivée
Soient E et F des ensembles finis. Pour qu’il existe une application f : E → F telle
que f (E) = F , il faut que le nombre d’éléments de E soit supérieur ou égal au
nombre d’éléments de F (voir page 58).
Réciproquement, si l’on a |E| |F |, il est facile de construire une application f : E → F
telle que f (E) = F : par exemple, si E = {a 1 , . . . , a p }, F = {b 1 , . . . , b n } et p n, on
peut poser f (a i ) = b i si 1 i n et f (a i ) = b n si n < i p.
Supposons désormais |E| |F | et comptons le nombre d’applications de E dans F
dont l’image f (E) est l’ensemble d’arrivée F tout entier :
une telle application permet de parcourir tous les éléments y = f (x) de
l’ensemble d’arrivée en faisant varier x dans l’ensemble de départ.
On dit que c’est une application surjective.
Préliminaire. Si A est un ensemble fini non vide, il y a autant de parties de A ayant
un nombre pair d’éléments que de parties de A ayant un nombre impair d’éléments.
Démonstration. L’ensemble A étant par hypothèse non vide, on peut choisir un élément
a ∈ A. Posons B = A \ {a}. Les parties de A qui ne contiennent pas a sont les parties de
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 65
nombre de p combinaisons avec répétitions de n éléments est
n+p−1
n−1
.
C’est aussi le nombre de rangements de n objets dans p boîtes.
Nombre de chemins sur un quadrillage
0 1
1
0
2
3
4
5
6
7
8
2 3 4 5 6 7 8 9
P 1
P 2 P 3
P 4
A
Repérons les points du plan par leurs coordonnées dans un repère (O;
→
i,
→
j) et
considérons le quadrillage formé des droites parallèles aux axes. Appelons chemin issu de O toute suite
P 0 = O, P 1 , . . . , P m de points tels que, pour tout k, le
vecteur
− − − − − − − − − − − − − − →
P k P k+1 est égal à
→
i ou à
→
j . Les coordonnées
des points P k sont donc des entiers positifs ou nuls.
La suite O, P 1 , . . . , P m définit une ligne brisée portée
par le quadrillage.
Un chemin issu de O est parfaitement déterminé
quand on connaît, pour tout k, le nombre x k de segments unité verticaux situés à l’abscisse k.
Par exemple, le chemin de O à A représenté sur la figure correspond à la suite
x 0 = x 1 = 0, x 2 = 1, x 3 = 2, x 4 = x 5 = 0, x 6 = 2, x 7 = 1, x 8 = 0, x 9 = 2 .
Soit A le point de coordonnées (p, q), où p et q sont des entiers positifs ou nuls.
Pour qu’un chemin issu de O ait le point A comme extrémité, il faut et il suffit que
l’on ait x 0 + x 1 + · · · + x p = q. Les chemins issus de O et d’extrémité A sont donc
en bijection avec les solutions de l’équation x 0 + · · · + x p = q, où x k ∈ N. D’après le
corollaire précédent, il y a
(p+1)+q−1
(p+1)−1
=
p+q
p
chemins issus de O et d’extrémité A.
Applications ayant pour image leur ensemble d'arrivée
Soient E et F des ensembles finis. Pour qu’il existe une application f : E → F telle
que f (E) = F , il faut que le nombre d’éléments de E soit supérieur ou égal au
nombre d’éléments de F (voir page 58).
Réciproquement, si l’on a |E| |F |, il est facile de construire une application f : E → F
telle que f (E) = F : par exemple, si E = {a 1 , . . . , a p }, F = {b 1 , . . . , b n } et p n, on
peut poser f (a i ) = b i si 1 i n et f (a i ) = b n si n < i p.
Supposons désormais |E| |F | et comptons le nombre d’applications de E dans F
dont l’image f (E) est l’ensemble d’arrivée F tout entier :
une telle application permet de parcourir tous les éléments y = f (x) de
l’ensemble d’arrivée en faisant varier x dans l’ensemble de départ.
On dit que c’est une application surjective.
Préliminaire. Si A est un ensemble fini non vide, il y a autant de parties de A ayant
un nombre pair d’éléments que de parties de A ayant un nombre impair d’éléments.
Démonstration. L’ensemble A étant par hypothèse non vide, on peut choisir un élément
a ∈ A. Posons B = A \ {a}. Les parties de A qui ne contiennent pas a sont les parties de
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 65