4. FORMULES CLASSIQUES DE D ´
ENOMBREMENT
33
4.5. Suites croissantes. — Dans la proposition suivante, on construit
explicitement une bijection entre un ensemble de suites croissantes (au sens
large) et un ensemble de suites strictement croissantes. On applique enfin le
corollaire pr´ ec´ edent.
Proposition 4.5.1. — Soient n et p deux entiers positifs et B un ensemble totalement ordonn´ e de cardinal p. Alors le nombre de suites croissantes
(c 1 ≤ c 2 ≤ · · · ≤ c n ) (au sens large), de longueur n, dont les c i sont extraits
de B est ´ egal `
a
p+n−1
n
.
D´ emonstration. — Sans restreindre la g´ en´ eralit´ e, on peut prendre B
comme ´ etant l’intervalle [ p ]. Soit (c 1 ≤ c 2 ≤ · · · ≤ c n ) une telle suite
croissante. On lui fait correspondre la suite d = (d 1 < d 2 < · · · < d n ),
d´ efinie par :
d 1 = c 1 ; d 2 = c 2 + 1 ; d 3 = c 3 + 2 ; . . . ; d n = c n + n − 1.
La suite d ainsi form´ ee est naturellement strictement croissante. De plus,
1 ≤ d 1 < d 2 < · · · < d n ≤ p + n − 1.
L’application c → d envoie bijectivement l’ensemble des suites croissantes
d´ ecrites dans l’´ enonc´ e de la proposition sur l’ensemble des suites strictement
croissantes, de longueur n, dont les termes sont pris dans l’intervalle [ p +
n − 1 ]. Comme le cardinal de l’ensemble de ces derni` eres suites est ´ egal ` a
p+n−1
n
d’apr` es le pr´ ec´ edent corollaire, ce nombre est aussi le nombre des
suites croissantes, de longueur n, dont les termes sont pris entre 1 et p.
On trouve encore un coefficient binomial dans le d´ enombrement suivant,
mais les param` etres sont diff´ erents.
Proposition 4.5.2. — Le nombre de suites (x 1 , x 2 , . . . , x n ) qui sont
solutions en nombres entiers positifs de l’´ equation
(4.5.1)
x 1 + x 2 + · · · + x n = p
(n et p fix´ es)
est ´ egal au coefficient binomial
p+n−1
p
.
D´ emonstration. — Soit x = (x 1 , x 2 , . . . , x n ) une telle solution. Associonslui la suite croissante y = (y 1 , y 2 , . . . , y n ) d´ efinie par
y 1 = 1 + x 1 ; y 2 = 1 + x 1 + x 2 ; . . . ; y n−1 = 1 + x 1 + · · · + x n−1 ;
y n = 1 + x 1 + · · · + x n−1 + x n = 1 + p.
On a : 1 ≤ y 1 ≤ y 2 ≤ · · · ≤ y n−1 ≤ 1 + p. R´ eciproquement, si y est une telle
suite, on d´ efinit x = (x 1 , x 2 , . . . , x n ) par :
x n = 1 + p − y n−1 ; x n−1 = y n−1 − y n−2 ; . . . ; x 2 = y 2 − y 1 ; x 1 = y 1 − 1.
Il y a donc bijection entre les solutions x de l’´ equation (4.5.1) et les suites
croissantes, au sens large, de longueur (n − 1), dont les termes sont pris dans
[ 1 + p ]. Le cardinal de l’ensemble des solutions x est donc ´ egal ` a
(1 + p) + (n − 1) − 1
n − 1
=
p + n − 1
n − 1
=
p + n − 1
p
.
ENOMBREMENT
33
4.5. Suites croissantes. — Dans la proposition suivante, on construit
explicitement une bijection entre un ensemble de suites croissantes (au sens
large) et un ensemble de suites strictement croissantes. On applique enfin le
corollaire pr´ ec´ edent.
Proposition 4.5.1. — Soient n et p deux entiers positifs et B un ensemble totalement ordonn´ e de cardinal p. Alors le nombre de suites croissantes
(c 1 ≤ c 2 ≤ · · · ≤ c n ) (au sens large), de longueur n, dont les c i sont extraits
de B est ´ egal `
a
p+n−1
n
.
D´ emonstration. — Sans restreindre la g´ en´ eralit´ e, on peut prendre B
comme ´ etant l’intervalle [ p ]. Soit (c 1 ≤ c 2 ≤ · · · ≤ c n ) une telle suite
croissante. On lui fait correspondre la suite d = (d 1 < d 2 < · · · < d n ),
d´ efinie par :
d 1 = c 1 ; d 2 = c 2 + 1 ; d 3 = c 3 + 2 ; . . . ; d n = c n + n − 1.
La suite d ainsi form´ ee est naturellement strictement croissante. De plus,
1 ≤ d 1 < d 2 < · · · < d n ≤ p + n − 1.
L’application c → d envoie bijectivement l’ensemble des suites croissantes
d´ ecrites dans l’´ enonc´ e de la proposition sur l’ensemble des suites strictement
croissantes, de longueur n, dont les termes sont pris dans l’intervalle [ p +
n − 1 ]. Comme le cardinal de l’ensemble de ces derni` eres suites est ´ egal ` a
p+n−1
n
d’apr` es le pr´ ec´ edent corollaire, ce nombre est aussi le nombre des
suites croissantes, de longueur n, dont les termes sont pris entre 1 et p.
On trouve encore un coefficient binomial dans le d´ enombrement suivant,
mais les param` etres sont diff´ erents.
Proposition 4.5.2. — Le nombre de suites (x 1 , x 2 , . . . , x n ) qui sont
solutions en nombres entiers positifs de l’´ equation
(4.5.1)
x 1 + x 2 + · · · + x n = p
(n et p fix´ es)
est ´ egal au coefficient binomial
p+n−1
p
.
D´ emonstration. — Soit x = (x 1 , x 2 , . . . , x n ) une telle solution. Associonslui la suite croissante y = (y 1 , y 2 , . . . , y n ) d´ efinie par
y 1 = 1 + x 1 ; y 2 = 1 + x 1 + x 2 ; . . . ; y n−1 = 1 + x 1 + · · · + x n−1 ;
y n = 1 + x 1 + · · · + x n−1 + x n = 1 + p.
On a : 1 ≤ y 1 ≤ y 2 ≤ · · · ≤ y n−1 ≤ 1 + p. R´ eciproquement, si y est une telle
suite, on d´ efinit x = (x 1 , x 2 , . . . , x n ) par :
x n = 1 + p − y n−1 ; x n−1 = y n−1 − y n−2 ; . . . ; x 2 = y 2 − y 1 ; x 1 = y 1 − 1.
Il y a donc bijection entre les solutions x de l’´ equation (4.5.1) et les suites
croissantes, au sens large, de longueur (n − 1), dont les termes sont pris dans
[ 1 + p ]. Le cardinal de l’ensemble des solutions x est donc ´ egal ` a
(1 + p) + (n − 1) − 1
n − 1
=
p + n − 1
n − 1
=
p + n − 1
p
.