Nombresentiersnaturels –Combinatoire
Exercice résolu
DÉNOMBREMENT DESSURJECTIONS
On se propose de chercher le nombre S
p
n de surjections de [[ 1 , n ]] sur [[ 1 , p ]] , où (n, p) ∈ N
∗2
.
1 Calculer S
p
n pour p > n. Calculer S
n
n ; S
1
n ; S
2
n .
2 Calculer S
p
p+1 .
3 En considérant la restriction à [[ 1 , n − 1]] d’une surjection de [[ 1 , n ]] dans [[ 1 , p ]] , montrer que:
∀n>1 ∀p>1 S
p
n =p(S
p
n − 1 +S
p − 1
n − 1 )
4 Construire une table des S
p
n pour 1 n 7 et 1 p 7.
Conseils
Solution
Fairedes schémas.
1) Si p > n, il n’existe pasdesurjection de [[ 1 , n ]] sur [[ 1 , p ]] : S
p
n = 0 .
• Si p = n, les surjections [[ 1 , n ]] sur [[ 1 , n ]] sont les bijections :
S
n
n = n!.
• Si p = 1, il existe une seule applicationde[ [1, n]] dans {1}, et elle
est surjective : S
1
n = 1.
• Si p = 2, seules les deux applications constantes ne sont pas surjectives :
S
2
n = 2
n
− 2.
Préciser ce qu’il faut connaître pour spécifier une surjection précise.
2) Si n = p +1 , un unique élément de l’ensemble d’arrivée ad eux
antécédents, et tous les autres en ontu ns eul. On peut caractériser une
surjection par le choix de cet élément, de ses deux antécédents, et d’une
permutation des (p − 1) éléments restants :
S
p
p+1 = p
p+1
2
(p − 1)! =
p(p +1)!
2
3) Soit s unesurjection de [[ 1 , n ]] sur [[ 1 , p ]] . L’élément i = s(n)p eut
être choisi de p façons.Soit s
la restrictionde s à[ [1, n − 1]].
• Si s
atteint i, c’estune surjection de [[ 1 , n − 1]]s ur [[ 1 , p ]] :i lya
S
p
n − 1 possibilités.
• Si s
n’atteint pas i, elle définitu ne surjection de [[ 1 , n − 1]]s ur
[[ 1 , p ]] \{i} :i lya S
p − 1
n − 1 possibilités.
D’où S
p
n = p
S
p
n−1 + S
p−1
n−1
Appliquerl af ormule de proche en
proche. Vérifier les valeurs données.
4) Àl’aide de cette formule de récurrence, compléter la table suivante :
p
n
1
2
3
4
5
6
7
1
1
2
1
2
3
1
6
4
1
24
5
1
120
6
1
720
7
1
8400
5040
Hachette Livre–HPrépa /Math –Laphotocopie non autorisée est un délit
179
Exercice résolu
DÉNOMBREMENT DESSURJECTIONS
On se propose de chercher le nombre S
p
n de surjections de [[ 1 , n ]] sur [[ 1 , p ]] , où (n, p) ∈ N
∗2
.
1 Calculer S
p
n pour p > n. Calculer S
n
n ; S
1
n ; S
2
n .
2 Calculer S
p
p+1 .
3 En considérant la restriction à [[ 1 , n − 1]] d’une surjection de [[ 1 , n ]] dans [[ 1 , p ]] , montrer que:
∀n>1 ∀p>1 S
p
n =p(S
p
n − 1 +S
p − 1
n − 1 )
4 Construire une table des S
p
n pour 1 n 7 et 1 p 7.
Conseils
Solution
Fairedes schémas.
1) Si p > n, il n’existe pasdesurjection de [[ 1 , n ]] sur [[ 1 , p ]] : S
p
n = 0 .
• Si p = n, les surjections [[ 1 , n ]] sur [[ 1 , n ]] sont les bijections :
S
n
n = n!.
• Si p = 1, il existe une seule applicationde[ [1, n]] dans {1}, et elle
est surjective : S
1
n = 1.
• Si p = 2, seules les deux applications constantes ne sont pas surjectives :
S
2
n = 2
n
− 2.
Préciser ce qu’il faut connaître pour spécifier une surjection précise.
2) Si n = p +1 , un unique élément de l’ensemble d’arrivée ad eux
antécédents, et tous les autres en ontu ns eul. On peut caractériser une
surjection par le choix de cet élément, de ses deux antécédents, et d’une
permutation des (p − 1) éléments restants :
S
p
p+1 = p
p+1
2
(p − 1)! =
p(p +1)!
2
3) Soit s unesurjection de [[ 1 , n ]] sur [[ 1 , p ]] . L’élément i = s(n)p eut
être choisi de p façons.Soit s
la restrictionde s à[ [1, n − 1]].
• Si s
atteint i, c’estune surjection de [[ 1 , n − 1]]s ur [[ 1 , p ]] :i lya
S
p
n − 1 possibilités.
• Si s
n’atteint pas i, elle définitu ne surjection de [[ 1 , n − 1]]s ur
[[ 1 , p ]] \{i} :i lya S
p − 1
n − 1 possibilités.
D’où S
p
n = p
S
p
n−1 + S
p−1
n−1
Appliquerl af ormule de proche en
proche. Vérifier les valeurs données.
4) Àl’aide de cette formule de récurrence, compléter la table suivante :
p
n
1
2
3
4
5
6
7
1
1
2
1
2
3
1
6
4
1
24
5
1
120
6
1
720
7
1
8400
5040
Hachette Livre–HPrépa /Math –Laphotocopie non autorisée est un délit
179