É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
