X Maths 2 MP 2008

Thème de l'épreuve Autour des surjections
Principaux outils utilisés dénombrements, séries entières, polynômes, algèbre linéaire
Mots clefs surjection, multinôme, double comptage, partition d'entier, Fubini

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE

FILIÈRE

MP

CONCOURS D'ADMISSION 2008

DEUXIÈME COMPOSITION DE MATHÉMATIQUES
(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

Dénombrement d'applications entre ensembles finis
On se propose de démontrer quelques propriétés du nombre des applications 
surjectives d'un
ensemble fini sur un autre.
Étant donné deux nombres entiers strictement positifs k et n, on note
· pk,n le nombre de parties à k éléments de l'ensemble {1, . . . , n}, nul si k 
> n ; on rappelle
!
n
pour k 6 n ;
que pk,n =
k
· jk,n le nombre d'applications injectives de {1, . . . , k} dans {1, . . . , 
n}, nul si k > n ;
· sk,n le nombre d'applications surjectives de {1, . . . , k} dans {1, . . . , 
n}, nul si k < n.
On posera aussi p0,n = j0,n = 1.

Première partie
1. Préciser les valeurs de jn,n et sn,n .
2. Montrer que l'on a jk,n =

n
k

!

k! si k 6 n.

Pour tout entier r > 0, on note P (r) (resp. S(r)) la matrice à r lignes et r 
colonnes de
coefficients P (r)k,n = pk,n (resp. S(r)k,n = sk,n ) pour k, n = 1, . . . , r.
3.a) Montrer que l'on a, pour k et n > 0 :
nk =

X

sk,q pq,n .

q=1,... ,n

3.b) Calculer le déterminant de la matrice A(r) de coefficients A(r)k,n = nk , 
k, n = 1, . . . , r.
1

Deuxième partie
Pour tout entier d > 0, on désigne par Ed l'espace vectoriel des polynômes à 
une indéterminée,
à coefficients complexes, de degré 6 d. On le munit de la base (X 0 = 1, X, . . 
. , X d ) ; on définit
un endomorphisme T de Ed par
T (P )(X) = P (X + 1) pour tout P  Ed .
4.a) Déterminer les coefficients Tk,n de la matrice représentant T dans le base 
indiquée (ici
0 6 k, n 6 d).
4.b) Même question pour T -1 dont on démontrera l'existence.
4.c) Étant donné deux vecteurs lignes (a0 , . . . , ad ) et (b0 , . . . , bd ) 
satisfaisant a0 = b0 et, pour
n = 1, . . . , d,
!
X
n
an =
bq
,
q
q=0,... ,n

écrire les bq en fonction des an .

4.d) Établir une formule de la forme
sk,n =

X

n,q q

k

q=1,... ,n

!

n
q

,

où 0 < n 6 k et où les n,q sont des coefficients à déterminer.
Dans la suite de cette seconde partie, on définit des éléments Nk de Ed , k = 
0, 1, . . . , d, par
Nk (X) =

si k = 0

1

 1 X(X + 1) · · · (X + k - 1)

k!

si k > 0 .

5. Vérifier que les Nk forment une base de Ed .
6. Démontrer la formule

T (Nk ) = Nk + T (Nk-1 ) pour k > 0 .
7.a) Déterminer les coefficients T 0, on désigne par
· Ak,n l'ensemble des applications de {1, . . . , k} dans {1, . . . , n} ;
· Bk,n l'ensemble des applications surjectives de {1, . . . , k} dans {1, . . . 
, n}, ensemble bien
entendu vide si k < n ;
· Ck,n l'ensemble des applications f : {1, . . . , n}  N satisfaisant
f (1) + . . . + f (n) = k ;
· Dk,n le sous-ensemble du précédent formé des f telles que f (i) > 1 pour tout 
i (ici, n 6 k).
9. Démontrer la « formule du multinôme », pour n > 0, k > 0 :
(x1 + . . . + xn )k =

X

f Ck,n

k!
f (1)
x
· · · xnf (n) ,
f (1)! · · · f (n)! 1

où x1 , . . . , xn sont des nombres réels.
[On pourra procéder par récurrence sur n.]
10. Montrer que
(x1 + . . . + xn )k =

X

x(1) · · · x(k) .

Ak,n

11. Montrer que, pour 0 < n 6 k, on a
sk,n =

X

f Dk,n

k!
.
f (1)! · · · f (n)!

Quatrième partie
On considère une série entière à coefficients réels

X

ak xk ; on suppose a0 = 0 ; on note R1

k>0

son rayon de convergence supposé non nul, et (x) sa somme. Pour n et k entiers 
> 0, on pose

n,k =

X

af (1) · · · af (n)

si 0 < n 6 k

f Dk,n

0,k =

si 0 6 k < n

0

1

si k = 0

0 si k > 0
3

12. Indiquer un minorant  > 0 du rayon de convergence de la série entière

X

n,k xk où n > 0 ;

k>0

déterminer la somme de cette série dans l'intervalle |x| < .
On considère une seconde série entière

X

bn xn ; on note R2 son rayon de convergence sup-

n>0

posé non nul, et (x) sa somme.
13. Montrer que la série entière

XX

k>0

bn n,k xk a un rayon de convergence non nul, et

n>0

préciser sa somme au voisinage de 0.
14. On considère la fonction (x) = e(e
 à l'aide des nombres sk,n .

x -1)

. Exprimer les coefficients de la série de Taylor de

4

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Maths 2 MP 2008 -- Corrigé
Ce corrigé est proposé par Sébastien Desreux (ENS Ulm) ; il a été relu par
Guillaume Dujardin (ENS Cachan) et Paul Pichaureau (Professeur en CPGE).

Cette épreuve de combinatoire démontre quelques identités utilisant des 
dénombrements de surjections. Elle fait essentiellement appel aux résultats 
basiques du
cours de sup ; aucun théorème nécessitant des hypothèses complexes n'est 
utilisé.
Bien que le thème central de l'épreuve soit le dénombrement des surjections,
le sujet utilise peu de résultats de combinatoire. Les outils mis en oeuvre 
sont en
fait l'algèbre et l'analyse, employées astucieusement. Ceci peut paraître 
étonnant
au premier abord, mais il s'agit d'une démarche classique : la combinatoire, 
comme
l'arithmétique, fait appel à tous les autres domaines des mathématiques.
· La première partie traite rapidement le comptage des bijections et des 
injections
avant de démontrer, à la question 3.a, une identité reliant nombre 
d'applications, nombre de surjections et combinaisons. Ce résultat s'interprète 
ensuite
comme une relation matricielle, ce qui amène au calcul d'un déterminant.
· La deuxième partie donne d'abord une interprétation algébrique à la formule
de la question 3.a, au moyen d'un endomorphisme T de C[X]. Cela permet 
d'inverser la relation et fournit une première identité de comptage des 
surjections.
On introduit ensuite une base qui généralise les combinaisons, dans laquelle
les matrices de T et T-1 sont très simples. La partie se clôt sur une question
difficile qui explicite le changement de base.
· La troisième partie a pour but de démontrer une deuxième identité de comptage
des surjections. À cette fin, on développe (x1 + · · · + xn )k de deux façons.
· La quatrième partie montre comment les surjections peuvent être utilisées pour
des opérations sur les séries entières. Les résultats des parties III et IV 
sont mis
x
en oeuvre pour calculer la série de Taylor en 0 de la fonction x 7 e e -1 .
Le sujet porte sur des parties du programme qui sont rarement exploitées et
peut théoriquement être abordé dès la sup. Attention toutefois, il requiert par 
endroits un certain recul vis-à-vis des outils conceptuels, ce qui correspond 
bien aux
objectifs de sélection de l'École Polytechnique. À chaque question, il faut 
trouver
rapidement le bon argument et, pour cela, prendre le temps d'interpréter la 
question
et de comprendre la manière dont l'énoncé veut nous guider. Il faut cependant 
être
particulièrement attentif aux bornes des sommes et aux domaines des variables.
Enfin, il faut noter que cet énoncé présente un grand intérêt pédagogique. En 
effet,
il est excellent pour apprendre à repérer les étapes par lesquelles l'auteur du 
sujet nous
fait passer, deviner ce qu'il faut réutiliser, bref comment naviguer avec 
succès dans
un sujet de concours. Usuellement, ce cheminement est parasité par des questions
techniques qui préparent l'emploi d'un théorème complexe, ce qui n'est pas le 
cas ici.
En cela, il représente une bonne préparation à tous les concours.

Indications
Première partie
1 Que dire d'une injection de [[ 1 ; n ]] dans lui-même ?
2 Une injection j : [[ 1 ; k ]]  [[ 1 ; n ]] est une bijection de [[ 1 ; k ]] 
dans j([[ 1 ; k ]]).
3.a Regrouper les applications selon le cardinal q de leur image.
3.b Remarquer que A(r) = S(r) × P(r) (attention aux bornes de la somme) et que
les matrices P(r) et S(r) sont triangulaires.
Deuxième partie
4.a T(X ) correspond au n-ième vecteur colonne de la matrice de T.
n

4.b Exprimer T-1 à l'aide de P(X - 1).
4.c Multiplier le vecteur (b0 , . . . , bd ) par la matrice de T (qui est 
inversible).
4.d Appliquer le résultat de la question 4.c à l'identité de la question 3.a .
5 Examiner les degrés des polynômes de la famille.
6 Exprimer le membre de droite en fonction de X et factoriser.
7.a La question 6 a fourni une relation de récurrence, qui permet d'exprimer 
T(Nk )
dans la base (N0 , . . . , Nd ).
7.b Nk = T(Nk - Nk-1 ).
8 Deux polynômes de degré d qui coïncident en d + 1 points sont égaux.
Troisième partie
9 Utiliser l'hypothèse de récurrence sur l'expression x1 + · · · + xn-1 + (xn + 
xn+1 ).
10 On doit choisir un xi parmi n, k fois de suite.
11 Les membres de droite des questions 9 et 10 sont des polynômes en x1 dont les
termes constants sont égaux.
Quatrième partie
12 Partir de la série dont la somme est [(x)]n .
13 Partir de la série dont la somme est ((x)) quand |(x)| < R2 .
14 Application directe de la question précédente.

Première partie
1 Lorsque les ensembles de départ et d'arrivée d'une application f sont tous 
deux
finis et de même cardinal, il est équivalent d'affirmer que f est injective, 
surjective
ou bijective. Or, une bijection de [[ 1 ; n ]] dans lui-même est une 
permutation, donc
n  N

jn,n = sn,n = n !

Rappelons qu'une idée intuitive des injections, surjections, bijections et
applications peut se représenter à l'aide de graphes bien connus :
[[ 1 ; k ]]

[[ 1 ; n ]]

injection

[[ 1 ; k ]]

[[ 1 ; n ]]

surjection

[[ 1 ; k ]]

[[ 1 ; n ]]

bijection

[[ 1 ; k ]]

[[ 1 ; n ]]

application

2 Notons j une injection de [[ 1 ; k ]] dans [[ 1 ; n ]] (avec k 6 n). L'image 
de j est
l'un quelconque
  des sous-ensembles de [[ 1 ; n ]] possédant k éléments, que l'on peut
n
choisir de
façons. L'image de j étant fixée, j est une injection de [[ 1 ; k ]] vers un
k
ensemble à k éléments, c'est donc une bijection : il y a par conséquent k ! 
injections
de [[ 1 ; k ]] dans [[ 1 ; n ]] qui ont pour image Im (j).
 
n

n  N k 6 n
jk,n =
k!
k
On constate qu'il est aisé de dénombrer les injections. La suite du problème
se concentre sur les surjections.
3.a Notons A l'ensemble des applications de [[ 1 ; k ]] dans [[ 1 ; n ]] (avec 
k et n > 0).
Regroupons dans un ensemble Aq les éléments de A dont l'image a pour cardinal 
q. Ce dernier vaut au moins 1 (l'image de l'application ne peut pas être vide),
et au plus n.
n
S
A =
Aq
q=1

Supposons maintenant q fixé, q  [[ 1 ; n ]], et déterminons le cardinal de Aq .

· Il y a pq,n façons de choisir q éléments parmi n par définition des pq,n .
· Un sous-ensemble Sq de [[ 1 ; n ]] possédant q éléments étant choisi, les 
applications de Aq ayant pour image exactement Sq sont des surjections de [[ 1 
; k ]]
dans Sq ; il y en a sk,q .
· Le nombre d'applications appartenant à Aq est donc
q  [[ 1 ; n ]]

Card Aq = sk,q × pq,n

Comme les Aq sont deux à deux disjoints,
n
n
P
P
Card A =
Card Aq =
sk,q × pq,n
q=1

q=1

Par ailleurs, A possède nk éléments car chacun des k éléments de l'ensemble de
départ peut prendre l'une quelconque des n images possibles. Il vient :
n
P
k, n  N nk =
sk,q pq,n
q=1

La technique utilisée ci-dessus s'appelle le double comptage : elle consiste à
compter de deux manières le nombre d'éléments d'un ensemble. Cette idée
est fréquemment utilisée pour établir des identités combinatoires.
3.b Pour r > 0 fixé, calculons le terme général du produit Q(r) = S(r) × P(r) :
r
P
(k, n)  [[ 1 ; r ]]2 Q(r)k,n =
sk,q × pq,n
q=1

Vu les conventions de notation adoptées, n est toujours plus petit que r. Or 
d'après
le préambule, pq,n = 0 dès que q > n, d'où
n
P
(k, n)  [[ 1 ; r ]]2 Q(r)k,n =
sk,q × pq,n
q=1

D'après la question 3.a, ceci signifie que
A(r) = S(r) × P(r)

Il est pratique à cette étape de noter, au brouillon, l'allure générale des 
matrices S(r) et P(r) :
 n r
 nr
1

1

1!
1
1
1

 1

2!
0

S(r) = 
P(r) = 
 k
 k
..
..

.
.

0
r! r
1 r

*

*

Or, la matrice S(r) est triangulaire inférieure puisque sk,n = 0 dès que k < n ;
de même, P(r) est triangulaire supérieure puisque pk,n = 0 dès que k > n. Leurs
déter 
n
minants sont donc les produits de leurs termes diagonaux. Comme pn,n =
=1
n
pour tout n  [[ 1 ; r ]], det P(r) = 1. De plus, d'après la question 1, sn,n = 
n ! pour
r

tout n  [[ 1 ; r ]] donc det S(r) =

 q !. Il vient
q=1
r

det A(r) = det S(r) × det P(r) =

 q!
q=1

Le calcul pouvait aussi être mené à la main en faisant apparaître une matrice
de Vandermonde.
 1

1 21 31 · · · r 1
12 22 32 · · · r2 

A(r) =  .
..
..
.. 
 ..
.
.
.
1r

2r

3r

· · · rr