Centrale Maths 1 PC 2017

Thème de l'épreuve Partitions et nombres de Bell
Principaux outils utilisés séries entières, probabilités, polynômes, dénombrement
Mots clefs partitions, nombre de Bell, polynômes de Hilbert

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


î, % Mathématiques 1 l\ %, '--| __/ PCC unusuuns EENÏHHLE-SUPËLEE 4 heures Calculatrices autorisées N Soit E un ensemble non vide. On appelle partition de E tout ensemble U : {A1: ..., Ak} de parties de E tel que -- chaque A,, pour i E [[1, k]] est une partie non vide de E; -- les parties Al, ..., Ak sont deux à deuzt disjointes, c'est--à--dire que pour tous i # j entre 1 et [EUR, A, () Aj : ® ; k -- la réunion des A, forme E tout entier : E = U A,. '=1 [ Si [[ une partition de E et si k est le nombre d'éléments de U, on dit aussi que Zi une partition de E en k parties. I Nombre de partitions en le parties I.A * Soit k et 71 deux entiers strictement positifs. Montrer qu'il n'existe qu'un nombre fini de partitions de l'ensemble [[1, n]] en [{ parties. Dans tout le problème, pour tout couple (n,/Æ) d'entiers strictement positifs, on note 501, [EUR) le nombre de partitions de l'ensemble [[1, n]] en [EUR parties. On pose de plus S(0,0) : l et, pour tout (n,/EUR) EUR N*2, S(n, O) : S(O, k) : 0. LE -- Exprimer S(n, [EUR) en fonction de n ou de [EUR dans les cas suivants : I.B.1) [EUR > n ; I.B.2) k : l. I. C * Montrer que pour tous le et n entiers strictement positifs, on a S(n,k) : S(n--l,k-- l) +kS(n--l,k) On pourra distinguer les partitions de [[l,n]] selon qu'elles contiennent ou non le singleton {n}. I.D * I.B.1) Rédiger une fonction Python récursive permettant de calculer le nombre S (n,/t), par application directe de la formule établie à la question LC. n I.B.2) Montrer que, pour n 2 1, le calcul de S (n, [EUR) par cette fonction récursive nécessite au moins (le) opérations (sommes ou produits). II Nombres de Bell Dans toute la suite, on pose pour tout entier n 2 O, Bn : S(n, k) k=0 II.A -- Montrer que pour n 2 1, B,, est égal au nombre total de partitions de l'ensemble [[l,n]]. II.B -- Démontrer la formule k=0 Vn EUR N, B,,+1 : Z (Z) Bk B II. C * Montrer que la suite (--"> est majorée par 1. nEURN 71! II .D * En dedu1re une mmorat10n du rayon de convergence R de la serie entiere Z --|z". n. 7120 +00 B Pour sa EUR ]--R,Rl, on pose f(x) : ;) fisc". ILE f Montrer que pour tout 33 EUR ]--R,Rl, f'(æ) : eæf(æ). II.F * En déduire une expression de la fonction f sur ]--R, Rl. 2017--01--30 08:44:20 Page 1/3 ÎCÔ BY--NC-SA III Une suite de polynômes On définit la suite de polynômes (Hk)kEURN dans [R(X] par HO(X) : 1 et, pour tout [EUR EUR N'", Hk(X) : X(X --1)----(X -- k + 1) III.A -- Montrer que la famille (HO, ..., H") est une base de l'espace R,,(X]. III.B -- III.B.1) Pour tout [EUR EUR N, établir une expression simplifiée de Hk+l(X) + ka(X). III.B.2) En déduire que, pour tout entier naturel 71 TL X" : Z S(n, k)Hk(X) k=0 III.C-- SoitkEURN. OEn III. C. 1) Montrer que la fonction fk: x |_) â( S( n, le) )--| est définie sur ]--1,1(. 71. (EUR, -- ... III.C.2) Pour [EUR EUR N, on considère la fonction gk : 33 r--> k' Montrer que la fonction gk vérifie l'équation différentielle /Ï (eoe_1)kf1 , --fi+ky III.C.3) En déduire que pour tout [EUR EUR N et pour tout &: EUR ]--1, 1(, e_(æk_1>kZSnk III.D -- OEk +oo III.B.1) Pour 33 EUR ]--1,1( et o EUR [R, simplifier z Hk(a)Ü' III.B.2) Montrer que pour u < ln2 +00 EUR" _ le C... : z Hk(a)@ k=0 k! IV Fonctions génératrices On se donne dans la suite un espace probabilisé (Q, %! , [P). Soit m un entier strictement positif. On dit qu'une variable aléatoire Y: Q --> N admet un moment d'ordre m fini si Yadmet une espérance finie, c'est--à--dire si la série Z nmP(Y : n) converge. On appelle alors moment d'ordre m de Yle réel -()Y... :Î nm[P(Y I V.A * Montrer que si Y : Q % N est une variable aléatoire associée à une fonction génératrice GY de rayon strictement supérieur a 1, alors Yadmet a tout ordre un moment fini. I V.B * Réciproquement, soit Y : Q % N une variable aléatoire admettant a tout ordre un moment fini. IV.B.1) Montrer que la fonction génératrice GY est de classe C°° sur (--1, l]. IV.B.2) Exprimer Gg'f' (l) a l'aide des polynômes H k(X ) et de la variable Y. IV.B.3) La fonction génératrice GY a--t--elle nécessairement un rayon de convergence strictement supérieur a 1 '? On pourra utiliser la série entière Zeffioe". IV. C * On suppose dans cette question que Ysuit la loi de Poisson de paramètre 1. IV.C.1) Montrer que pour tout 71 EUR N, B,, : (.Y") +oo n IV.C.2) En déduire que pour tout polynôme Q(X ) a coefiicients entiers, la série Z Q< ) est convergente et n=0 sa somme est de la forme Ne, où N est un entier. 2017--01--30 08:44:20 Page 2/3 (ce BY-NC-SA V Somme de puissances On fixe n E N. On pose l'application linéaire : A : R{X] --> nem P(X) l--> P(X + 1) -- P(X) p V.A * À l'aide d'un encadrement par des intégrales, déterminer un équivalent de Un (p) : z k", a n 2 1 k=0 fixé, lorsque p tend vers +00. V.B * Soit An l'endomorphisme induit par A sur le sous--espace stable RJX]. Déterminer la matrice A de An dans la base (Ho: ..., H"). " [EUR V.C * En déduire que Un(p) : î: î:F -->G 1300 '--> A(P(Q(X--1))) est un isomorphisme. V.D.3) En déduire que pour tout 7" EUR N, il existe un seul polynôme P,.(X ) tel que V.E -- V.E.l) Déterminer le terme dominant dans PT(X ) V.E.2) Montrer que pour r 2 1, X2 divise P X). 7' V.E.3) Expliciter les polynômes P1 (X ) et P2 (X ) oooFlNooo 2017--01--30 08:44:20 Page 3/3 ("à BY--NC-SA

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


 Centrale Maths 1 PC 2017 -- Corrigé Ce corrigé est proposé par Quentin Guilmant (ENS Lyon) ; il a été relu par Thierry Limoges (ENS Cachan) et Benjamin Monmege (enseignant-chercheur à l'université). Le sujet tourne autour de la notion de partitions d'un ensemble à n éléments. Comme tout sujet de combinatoire, c'est l'occasion de faire le lien entre plusieurs domaines classiques des mathématiques, comme les polynômes, les séries entières et, dans cet énoncé, les probabilités. · La première partie propose l'étude du nombre S(n, k) de partitions d'un ensemble à n éléments en k parties. Il s'agit ici essentiellement de se familiariser avec la notion et d'établir une formule de récurrence utile pour la suite. · Le deuxième partie introduit le nombre de Bell Bn qui compte les partitions d'un ensemble à n éléments ; il est égal à la somme sur k des quantités S(n, k) manipulées dans la partie précédente. L'objectif de cette partie P estn d'obtenir une expression simple de la série génératrice exponentielle Bn x /n! de la n>0 suite (Bn )nN . · La troisième partie fait réapparaître naturellement les nombres S(n, k) de la première partie dans le cadre des polynômes. On établit en effet qu'il s'agit des coefficients d'une matrice de passage entre la base canonique de Rn [X] et la famille bien connue des polynômes de Hilbert (même si l'énoncé ne les nomme pas explicitement). On étudie également les séries génératrices exponentielles des suites (S(n, k))nN pour obtenir un certain nombre de jolies formules. · La quatrième partie définit la notion de moment d'une variable aléatoire à valeurs entières, puis relie le nombre de Bell Bn aux moments d'une variable aléatoire suivant une loi de Poisson. · La cinquième et dernière partie fait pour finir le lien entre S(n, k) et les sommes n P finies k p pour p et n entiers et permet d'étudier quelques propriétés notables k=1 de ces sommes. Ce sujet permet de constater une particularité assez fréquente en combinatoire : une suite définie initialement comme le cardinal d'une famille d'objets (en l'occurrence, le nombre de partitions d'un ensemble à n éléments) intervient aussi dans des domaines a priori sans rapport. La combinatoire, relativement peu étudiée en CPGE, constitue ainsi une passerelle entre des domaines très divers. Lorsqu'elle apparaît aux concours, elle donne des énoncés riches faisant intervenir un large spectre du programme de prépa. Indications Partie I I.E Utiliser la formule du triangle de Pascal. Partie II II.A Exprimer l'ensemble des partitions comme l'union disjointe des ensembles des partitions en k parties. II.B Considérer une partition de [[ 1 ; n + 1 ]] et isoler la partie contenant l'élément n + 1. II.C Procéder par récurrence et utiliser la question II.B. P P n II.D Comparer la série Bn /n ! xn à la série x . II.E Développer en série entière le produit e x f (x) à l'aide d'un produit de Cauchy. II.F Résoudre l'équation différentielle de la question II.E. Partie III III.B.1 Observer que Hk divise Hk+1 et factoriser l'expression Hk+1 + kHk par le polynôme Hk . III.B.2 Procéder par récurrence et utiliser les questions I.C et III.B.1. III.C.1 Comparer la fonction fk à la série entière de la question II.D. III.C.3 Procéder par récurrence sur k, dériver la fonction fk et comparer le problème de Cauchy obtenu à celui que satisfait la fonction gk . III.D.1 Reconnaître un développement limité usuel. Partie IV IV.A Utiliser le fait que les séries entières de terme général an xn et nan xn ont le même rayon de convergence. IV.B.1 Appliquer les théorèmes de dérivation et d'échange entre limite et série. IV.B.3 Prouver que la série proposée par l'énoncé converge sur [ -1 ; 1 ] et définir une variable aléatoire dont la série génératrice est de la même forme à une constante multiplicative près. IV.C.1 Calculer E(Hk (Y)) et utiliser la question III.B.2. Partie V V.A Relier k n à une intégrale entre k et k + 1 d'un polynôme de degré n. V.C Utiliser la question III.B.2 et faire apparaître une somme télescopique. V.D.3 Chercher un antécédent par du polynôme X2r+1 . V.E.1 Utiliser la question V.A. V.E.2 Écrire Pr sous une forme développée et calculer (Pr ) sous forme développée. I. Nombre de partitions en k parties I.A Remarquons que toute partition de l'ensemble [[ 1 ; n ]] en k parties est obtenue en choisissant k sous-ensembles deux-à-deux disjoints de [[ 1 ; n ]]. Or, il y a 2nsous 2n ensembles de [[ 1 ; n ]]. Ainsi, le nombre de partitions en k parties est majoré par . k En particulier, Le nombre de partitions de [[ 1 ; n ]] en k parties est fini. I.B.1 Une partitions de l'ensemble [[ 1 ; n ]] en k parties ne peut pas contenir strictement plus de n sous-ensembles, car chacun d'entre-eux doit être non vide. Ainsi, Si k > n, alors S(n, k) = 0. I.B.2 Pour tout entier n non nul, l'ensemble {[[ 1 ; n ]]} est l'unique partition de l'ensemble [[ 1 ; n ]] en 1 partie, de sorte que n N S(n, 1) = 1 I.C Notons Ekn l'ensemble des partitions de [[ 1 ; n ]] en k parties. On sépare cet ensemble en deux sous-ensembles disjoints : n · l'ensemble Ek,1 des partitions en k parties dont l'une d'elles est réduite à l'élément n ; n · l'ensemble Ek,2 des partitions en k parties dont aucune n'est réduite à n. Ainsi, n n S(n, k) = |Ekn | = |Ek,1 | + |Ek,2 | n n Déterminons maintenant les cardinaux de Ek,1 et Ek,2 . n · Étant donné un élément de Ek,1 , si l'on supprime la partie réduite à n, on obtient une partition de [[ 1 ; n - 1 ]] en k - 1 parties. Cette opération est bijective, la réciproque consistant simplement à rajouter la partie {n}. On en déduit en particulier que n-1 n |Ek,1 | = |Ek-1 | = S(n - 1, k - 1) n · Soit maintenant un élément de Ek,2 . Si l'on supprime l'élément n de la partie à laquelle il appartient, on obtient cette fois une partition de [[ 1 ; n - 1 ]] en k parties. Cependant, l'opération n'est plus bijective, mais surjective, et chaque élément de Ekn-1 admet exactement k antécédents puisque l'on a k choix pour la partie à laquelle on va rajouter n. Il vient cette fois que n |Ek,2 | = k · |Ekn-1 | = k · S(n - 1, k) On peut conclure de tout ceci que S(n, k) = S(n - 1, k - 1) + k · S(n - 1, k) I.D.1 Il s'agit de donner un code qui reprenne tous les cas vus précédemment. Plus précisément, les conventions de l'énoncé et la question I.B donnent les cas de base, la question précédente permet de construire le cas récursif. Il suffit en fait de remarquer que le système de calcul est très proche de la méthode de remplissage du triangle de Pascal. On traitera donc les cas des bordures, c'est-à-dire quand n = 0 ou k = 0, puis les cas qui n'ont pas de sens et enfin le cas général. def calculS(n,k): #Tester les cas "convention". if n==0 and k==0: #On traite ici le cas n=k=0 return 1 elif n==0 or k==0: #On traite ici les cas 0=nn: #On traite ici le cas qui n'a pas de sens k>n return 0 #cas recursif else: res = calculS(n-1,k-1) + k*calculS(n-1,k) return res On peut remarquer que cette fonction termine. En effet, une quantité strictement décroissante est la somme des deux arguments, et pourtant elle doit rester entière et positive. I.D.2 Notons C(n, k) le nombre d'opérations nécessaires dans l'algorithme précédent pour calculer S(n, k). En raison des appels récursifs si 1 6 k 6 n, alors C(n, k) = C(n - 1, k - 1) + C(n - 1, k) + 2 > C(n - 1, k - 1) + C(n - 1, k) Remarquons ici que c'est une formule combinatoire qui correspond au triangle de Pascal. Si k > n, seul l'appel de la fonction est fait et n C(n, k) = 1 > =0 k Maintenant, supposons k 6 n et procédons par récurrence. Considérons la propriété n P(n) : k [[ 0 ; n ]] C(n, k) > k · P(0) est vraie car, en considérant le coût de l'appel de la fonction, 0 C(0, 0) = 1 = 0 · P(n) = P(n + 1) : Soit k [[ 0 ; n + 1 ]]. Si k = 0, alors encore une fois, seul l'appel de la fonction est compté et n+1 C(n + 1, 0) = 1 = 0 Si 1 6 k 6 n, alors C(n + 1, k) = C(n, k - 1) + C(n, k) + 2 n n > + +2 k-1 k n n > + k-1 k n+1 C(n + 1, k) > k (d'après P(n)) (règle de Pascal)