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)