car
n
0
= 1 et a
0 = 1 ; si k = n, alors
n
k
a
k b
n−k =
n
n
a
n b
0 = a
n , car
n
n
= 1 ; dans le cas
général, on a
n
k
a
k b
n−k =
n
n−k
a
k b
n−k , d’où la formule.
Corollaire. Soient n et p des entiers tels que 1 p n. Il y a
n
p
applications
strictement croissantes de {1, . . . , p} dans {1, . . . , n}.
Démonstration. Si u est une application strictement croissante de {1,. . .,p} dans {1,. . .,n},
on a u(1) < u(2) < · · · < u(p), donc les éléments u(1), . . . , u(p) sont deux à deux différents
et l’ensemble {u(1), . . . , u(p)} est une partie à p éléments de {1, . . . , n}.
Notons S l’ensemble des applications strictement croissantes de {1, . . . , p} dans {1, . . . , n} et
P l’ensemble des parties à p éléments de {1, . . . , n}. À toute application strictement croissante
u : {1,. . .,p} → {1,. . .,n}, associons la partie {u(1), . . . , u(p)}. On définit ainsi une application
f : S → P . Montrons que f est une bijection, ce qui prouvera le corollaire.
Soit U une partie à p éléments de {1, . . . , n}. Rangeons les éléments de U dans l’ordre croissant : on obtient U = {u 1 ,. . .,u p }, où les entiers u i vérifient 1 u 1 < · · · < u p n. Définissons
l’application u : {1, . . . , p} → {1, . . . , n} en posant u(i) = u i si 1 i p. L’application u est
strictement croissante et {u(1), . . . , u(p)} = U , autrement dit u est un antécédent de U par f .
Supposons que v est un (autre) antécédent de U . On a v ∈ S , donc v : {1, . . . , p} → {1, . . . , n}
est une application strictement croissante ; de plus, on a f (v) = U , donc {v(1), . . . , v(p)} =
U = {u(1),. . .,u(p)}. Puisque v est strictement croissante, on a v(1) < · · · < v(p). On en déduit
les égalités v(1) = u(1), . . . , v(p) = u(p), donc v = u.
Par l’application f : S → P , tout élément de P possède exactement un antécédent. L’application
f est donc bijective.
Nombre d'applications croissantes
Dans ce paragraphe, p est un entier au moins égal à 1 et n est un entier positif ou nul.
Considérons les inéquations suivantes
(1)
x 1 + x 2 + · · · + x p n ,
x i ∈ N , x i 1
(2)
x 1 + x 2 + · · · + x p n ,
x i ∈ N
où l’inconnue est une suite (x 1 , . . . , x p ) d’entiers positifs ou nuls pour (2), d’entiers
strictement positifs pour (1).
Voici deux interprétations utiles pour les solutions de ces inéquations.
A) Il y a une bijection entre les solutions de (2) et les applications croissantes
de {1, . . . , p} dans {0, 1, . . . , n}.
Si s = (x 1 , . . . , x p ) est une solution de (2), on définit l’application
u s : {1, . . . , p} → {0, 1, . . . , n}
en posant u s (k) = x 1 + · · · + x k si 1 k p. Puisque les entiers x k sont positifs ou
nuls, l’application u s est croissante.
Réciproquement, supposons que v est une application croissante de {1, . . . , p} dans
{0, 1,. . .,n} ; posons x 1 = v(1) et x k = v(k) − v(k − 1) pour 2 k p ; par hypothèse,
on a x 1 0 et x k = v(k) − v(k − 1) 0 pour 2 k p, donc (x 1 , . . . , x p ) est une
62 – ENSEMBLES FINIS
n
0
= 1 et a
0 = 1 ; si k = n, alors
n
k
a
k b
n−k =
n
n
a
n b
0 = a
n , car
n
n
= 1 ; dans le cas
général, on a
n
k
a
k b
n−k =
n
n−k
a
k b
n−k , d’où la formule.
Corollaire. Soient n et p des entiers tels que 1 p n. Il y a
n
p
applications
strictement croissantes de {1, . . . , p} dans {1, . . . , n}.
Démonstration. Si u est une application strictement croissante de {1,. . .,p} dans {1,. . .,n},
on a u(1) < u(2) < · · · < u(p), donc les éléments u(1), . . . , u(p) sont deux à deux différents
et l’ensemble {u(1), . . . , u(p)} est une partie à p éléments de {1, . . . , n}.
Notons S l’ensemble des applications strictement croissantes de {1, . . . , p} dans {1, . . . , n} et
P l’ensemble des parties à p éléments de {1, . . . , n}. À toute application strictement croissante
u : {1,. . .,p} → {1,. . .,n}, associons la partie {u(1), . . . , u(p)}. On définit ainsi une application
f : S → P . Montrons que f est une bijection, ce qui prouvera le corollaire.
Soit U une partie à p éléments de {1, . . . , n}. Rangeons les éléments de U dans l’ordre croissant : on obtient U = {u 1 ,. . .,u p }, où les entiers u i vérifient 1 u 1 < · · · < u p n. Définissons
l’application u : {1, . . . , p} → {1, . . . , n} en posant u(i) = u i si 1 i p. L’application u est
strictement croissante et {u(1), . . . , u(p)} = U , autrement dit u est un antécédent de U par f .
Supposons que v est un (autre) antécédent de U . On a v ∈ S , donc v : {1, . . . , p} → {1, . . . , n}
est une application strictement croissante ; de plus, on a f (v) = U , donc {v(1), . . . , v(p)} =
U = {u(1),. . .,u(p)}. Puisque v est strictement croissante, on a v(1) < · · · < v(p). On en déduit
les égalités v(1) = u(1), . . . , v(p) = u(p), donc v = u.
Par l’application f : S → P , tout élément de P possède exactement un antécédent. L’application
f est donc bijective.
Nombre d'applications croissantes
Dans ce paragraphe, p est un entier au moins égal à 1 et n est un entier positif ou nul.
Considérons les inéquations suivantes
(1)
x 1 + x 2 + · · · + x p n ,
x i ∈ N , x i 1
(2)
x 1 + x 2 + · · · + x p n ,
x i ∈ N
où l’inconnue est une suite (x 1 , . . . , x p ) d’entiers positifs ou nuls pour (2), d’entiers
strictement positifs pour (1).
Voici deux interprétations utiles pour les solutions de ces inéquations.
A) Il y a une bijection entre les solutions de (2) et les applications croissantes
de {1, . . . , p} dans {0, 1, . . . , n}.
Si s = (x 1 , . . . , x p ) est une solution de (2), on définit l’application
u s : {1, . . . , p} → {0, 1, . . . , n}
en posant u s (k) = x 1 + · · · + x k si 1 k p. Puisque les entiers x k sont positifs ou
nuls, l’application u s est croissante.
Réciproquement, supposons que v est une application croissante de {1, . . . , p} dans
{0, 1,. . .,n} ; posons x 1 = v(1) et x k = v(k) − v(k − 1) pour 2 k p ; par hypothèse,
on a x 1 0 et x k = v(k) − v(k − 1) 0 pour 2 k p, donc (x 1 , . . . , x p ) est une
62 – ENSEMBLES FINIS