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