suite d’entiers positifs ou nuls ; pour tout entier k tel que 1 k p, on a
x 1 + · · · + x k = v(1) +
v(2) − v(1)
+ · · · +
v(k) − v(k − 1)
= v(k) n .
La suite s = (x 1 , . . . , x p ) est donc une solution de (2) et l’on a v = u s .
B) Il y a une bijection entre les solutions de l’inéquation (1) et les applications
strictement croissantes {1, . . . , p} → {1, . . . , n}.
Remarquons que toute solution de (1) est aussi une solution de (2). Supposons que
s=(x 1 ,. . .,x p ) est une solution de (1). Puisque les entiers x k sont tous au moins égaux
à 1, on a n x 1 + · · · + x p p, donc n p 1. L’application u s est strictement croissante et comme on a u s (1) = x 1 1, u s prend ses valeurs dans l’ensemble {1,. . .,n}.
Réciproquement, si u s prend ses valeurs dans {1, . . . , n} et est strictement croissante,
alors on a x 1 = u s (1) 1 et x k = u s (k) − u s (k−1) 1 pour tout entier k compris
entre 2 et p.
Proposition
i) L’inéquation (1) possède
n
p
solutions.
ii) L’inéquation (2) possède
p+n
p
solutions.
iii) Si n 1, le nombre d’applications croissantes de {1,. . .,p} dans {1,. . .,n} est
p+n−1
p
.
Démonstration. On sait qu’il y a
n
p
applications strictement croissantes de {1,. . .,p} dans
{1, . . . , n}, donc l’inéquation (1) possède
n
p
solutions.
On peut facilement passer d’une solution de (1) à une solution de (2) et vice-versa :
si (x 1 , . . . , x p ) est une suite d’entiers, posons y i = 1 + x i pour 1 i p. On a alors
y 1 + · · · + y p = p + (x 1 + · · · + x p ), d’où l’équivalence
x 1 + · · · + x p n et x i 0 pour tout i
⇐⇒ y 1 + · · · + y p p + n et y i 1 pour tout i.
Les solutions de l’inéquation (2) sont donc en bijection avec les solutions de l’inéquation
y 1 + · · · + y p p + n telles que y i 1 pour tout i. C’est une inéquation du type (1) (où n
est remplacé par p + n) : d’après (i), il y a donc
p+n
p
solutions à l’inéquation (2).
Ainsi le nombre d’applications croissantes de {1, . . . , p} dans {0, . . . , n} est aussi
p+n
p
.
Puisque {0, . . . , n} possède n+1 éléments, le nombre d’applications croissantes de {1, . . . , p}
dans {1, . . . , n} est
p+(n−1)
p
.
Exemples
® Les triplets (x, y, z) d’entiers tels que x 1, y 1, z 1 et x + y + z 5 sont :
(1, 1, 3), (1, 3, 1), (3, 1, 1), (2, 2, 1), (2, 1, 2), (1, 2, 2) pour lesquels x + y + z = 5,
(1, 1, 2), (1, 2, 1), (2, 1, 1) pour lesquels x + y + z = 4,
et (1, 1, 1) pour lequel x + y + z = 3.
Il y en a au total
5
3
=
5 × 4
2
= 10.
® Les applications croissantes de {1,2,3} dans {1, 2} sont : l’application c 1 constante
de valeur 1, définie par c 1 (1) = c 1 (2) = c 1 (3) = 1 ; l’application c 2 constante de
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 63
x 1 + · · · + x k = v(1) +
v(2) − v(1)
+ · · · +
v(k) − v(k − 1)
= v(k) n .
La suite s = (x 1 , . . . , x p ) est donc une solution de (2) et l’on a v = u s .
B) Il y a une bijection entre les solutions de l’inéquation (1) et les applications
strictement croissantes {1, . . . , p} → {1, . . . , n}.
Remarquons que toute solution de (1) est aussi une solution de (2). Supposons que
s=(x 1 ,. . .,x p ) est une solution de (1). Puisque les entiers x k sont tous au moins égaux
à 1, on a n x 1 + · · · + x p p, donc n p 1. L’application u s est strictement croissante et comme on a u s (1) = x 1 1, u s prend ses valeurs dans l’ensemble {1,. . .,n}.
Réciproquement, si u s prend ses valeurs dans {1, . . . , n} et est strictement croissante,
alors on a x 1 = u s (1) 1 et x k = u s (k) − u s (k−1) 1 pour tout entier k compris
entre 2 et p.
Proposition
i) L’inéquation (1) possède
n
p
solutions.
ii) L’inéquation (2) possède
p+n
p
solutions.
iii) Si n 1, le nombre d’applications croissantes de {1,. . .,p} dans {1,. . .,n} est
p+n−1
p
.
Démonstration. On sait qu’il y a
n
p
applications strictement croissantes de {1,. . .,p} dans
{1, . . . , n}, donc l’inéquation (1) possède
n
p
solutions.
On peut facilement passer d’une solution de (1) à une solution de (2) et vice-versa :
si (x 1 , . . . , x p ) est une suite d’entiers, posons y i = 1 + x i pour 1 i p. On a alors
y 1 + · · · + y p = p + (x 1 + · · · + x p ), d’où l’équivalence
x 1 + · · · + x p n et x i 0 pour tout i
⇐⇒ y 1 + · · · + y p p + n et y i 1 pour tout i.
Les solutions de l’inéquation (2) sont donc en bijection avec les solutions de l’inéquation
y 1 + · · · + y p p + n telles que y i 1 pour tout i. C’est une inéquation du type (1) (où n
est remplacé par p + n) : d’après (i), il y a donc
p+n
p
solutions à l’inéquation (2).
Ainsi le nombre d’applications croissantes de {1, . . . , p} dans {0, . . . , n} est aussi
p+n
p
.
Puisque {0, . . . , n} possède n+1 éléments, le nombre d’applications croissantes de {1, . . . , p}
dans {1, . . . , n} est
p+(n−1)
p
.
Exemples
® Les triplets (x, y, z) d’entiers tels que x 1, y 1, z 1 et x + y + z 5 sont :
(1, 1, 3), (1, 3, 1), (3, 1, 1), (2, 2, 1), (2, 1, 2), (1, 2, 2) pour lesquels x + y + z = 5,
(1, 1, 2), (1, 2, 1), (2, 1, 1) pour lesquels x + y + z = 4,
et (1, 1, 1) pour lequel x + y + z = 3.
Il y en a au total
5
3
=
5 × 4
2
= 10.
® Les applications croissantes de {1,2,3} dans {1, 2} sont : l’application c 1 constante
de valeur 1, définie par c 1 (1) = c 1 (2) = c 1 (3) = 1 ; l’application c 2 constante de
Chapitre 3 – D ´
ENOMBREMENT, PERMUTATIONS, GRAPHES – 63