Mathématiques 1

2016
TSI
4 heures Calculatrices autorisées
Nombres de Stirling et problème du collectionneur
Ce problème est consacré à l’étude de nombre introduits au xviiie siècle par James Stirling et intervenant en
particulier en théorie des probabilités et dans l’étude de la fiabilité de certains circuits électroniques.
Les parties du problème sont très largement indépendantes. Tout candidat peut admettre un résultat précé-
demment donné dans le texte pour aborder les questions suivantes, à condition de l’indiquer clairement sur sa
copie.
On rappelle les conventions 0! = 1 et ∀𝑎 ∈ ℝ, 𝑎0 = 1 et on note
− 𝐶 1 (ℝ, ℝ) l’ensemble des fonctions de ℝ dans ℝ, dérivables sur ℝ et dont la dérivée est continue sur ℝ ;
− ℳu� (ℝ) l’ensemble des matrices carrées d’ordre 𝑛 à coefficients réels.

I Généralités sur les nombres de Stirling

Si 𝐸 est un ensemble et 𝑘 un entier naturel non nul, une partition de 𝐸 est un ensemble {𝐴1 , …, 𝐴u� } de parties
de 𝐸 non vides, deux à deux disjointes, et dont la réunion est égale à 𝐸 :
u�
∀𝑖 ∈ {1, …, 𝑘}, 𝐴u� ≠ ∅ ∀(𝑖, 𝑗) ∈ {1, …, 𝑘}2 , 𝑖 ≠ 𝑗 ⟹ 𝐴u� ∩ 𝐴u� = ∅ ⋃ 𝐴u� = 𝐸
u�=1

Par exemple, {{1}, {2, 3}, {4, 5}} est une partition de 𝐸 = {1, 2, 3, 4, 5} en trois parties. On notera en particulier
que l’ordre dans lequel interviennent les parties 𝐴1 , …, 𝐴u� n’a pas d’incidence sur la définition de la partition.
Pour 𝑛 ∈ ℕ∗ et 𝑘 ∈ {1, …, 𝑛}, on note 𝑆u�,u� le nombre de partitions d’un ensemble à 𝑛 éléments en 𝑘 parties. On
pose également 𝑆0,0 = 1 et 𝑆u�,0 = 0 lorsque 𝑛 ∈ ℕ∗ .
Les nombres 𝑆u�,u� sont appelés nombres de Stirling de deuxième espèce.

I.A – Premières propriétés des nombres de Stirling

I.A.1)
a) Déterminer la valeur de 𝑆3,2 .
b) Soit 𝑛 ∈ ℕ∗ . Que valent 𝑆u�,1 et 𝑆u�,u� ?
I.A.2) Soit 𝑛 un entier, 𝑛 ⩾ 2, 𝑘 un entier compris entre 1 et 𝑛 − 1 et 𝐸 = {𝑥1 , …, 𝑥u� } un ensemble à 𝑛
éléments. On souhaite établir une relation entre 𝑆u�,u� , 𝑆u�−1,u�−1 et 𝑆u�−1,u� .
a) Dans cette question, on étudie l’exemple 𝐸 = {1, 2, 3, 4} (𝑛 = 4) et 𝑘 = 2.
i. Expliciter les partitions de 𝐸 en deux parties, dont l’une est le singleton {4}.
ii. Expliciter les partitions de 𝐸 en deux parties, dont l’une contient 4 tout en étant différente du singleton {4}.
iii. Vérifier, pour l’exemple traité, la relation 𝑆u�,u� = 𝑆u�−1,u�−1 + 𝑘𝑆u�−1,u� .
b) On revient au cas général présenté en début de question I.A.2.
i. Quel est le nombre de partitions de 𝐸 en 𝑘 parties, dont l’une est {𝑥u� } ? On exprimera le résultat à l’aide
d’un nombre de Stirling.
ii. Quel est le nombre de partitions de 𝐸 en 𝑘 parties, dont l’une contient 𝑥u� tout en étant différente du singleton
{𝑥u� } ? On exprimera le résultat à l’aide d’un nombre de Stirling.
iii. En déduire que 𝑆u�,u� = 𝑆u�−1,u�−1 + 𝑘𝑆u�−1,u� .
𝑛(𝑛 − 1)
I.A.3) En déduire que, pour tout entier 𝑛 ⩾ 2, 𝑆u�,u�−1 = . On pourra par exemple procéder par
2
récurrence.
I.A.4) Montrer que, pour tout entier 𝑛 ⩾ 3, 𝑆u�,2 + 1 = 2(𝑆u�−1,2 + 1) et en déduire la valeur de 𝑆u�,2 pour
tout entier 𝑛 ⩾ 2.
I.A.5) Soient 𝑛 ∈ ℕ∗ , 𝑘 ∈ ℕ∗ et deux ensembles 𝐸 = {𝑥1 , …, 𝑥u� } et 𝐹 = {𝑦1 , …, 𝑦u� }. On note 𝜎u�,u� le nombre
d’applications surjectives de 𝐸 dans 𝐹 .
a) Que vaut 𝜎u�,u� si 𝑛 < 𝑘 ?
b) Que vaut 𝜎u�,u� si 𝑛 = 𝑘 ?
c) Expliciter les applications surjectives de 𝐸 dans 𝐹 lorsque 𝑛 = 3 et 𝑘 = 2, et préciser la valeur de 𝜎3,2 .

2015-12-10 [Link] Page 1/3

d) Dans cette question, on souhaite obtenir une relation entre 𝜎u�,u� et 𝑆u�,u� .
Si 𝑓 est une application de 𝐸 dans 𝐹 et 𝑗 un entier compris entre 1 et 𝑘, on note 𝐴u� = 𝑓 −1 ({𝑦u� }) l’ensemble des
antécédents par 𝑓 de 𝑦u� .
i. Étant donnée une application 𝑓 surjective de 𝐸 dans 𝐹 , montrer que 𝒜 = {𝐴1 , …, 𝐴u� } est une partition de
𝐸 en 𝑘 parties. On note Π(𝑓) cette partition.
ii. Étant donnée 𝒜′ = {𝐴′1 , …, 𝐴u� ′} une partition de 𝐸 en 𝑘 parties, combien y a-t-il d’applications 𝑓 surjectives
de 𝐸 dans 𝐹 telles que Π(𝑓) = 𝒜′ ?
iii. En déduire la relation 𝜎u�,u� = 𝑘! 𝑆u�,u� .
I.A.6) Montrer, par exemple par récurrence, que, pour tout 𝑛 ∈ ℕ, ∀𝑘 ∈ {0, …, 𝑛}, 𝑆u�,u� ⩽ (2𝑘)u� .

I.B – Utilisation des nombres de Stirling en algèbre linéaire

Soit 𝑁 ∈ ℕ∗ ; on note ℝu� [𝑋] l’ensemble des polynômes à coefficients réels de degré inférieur ou égal à 𝑁 et ℬ
la base canonique de ℝu� [𝑋]. On définit la famille de polynômes (𝑃u� )0⩽u�⩽u� par

⎧ 𝑃0 = 1
{ u�−1
⎨ 𝑃u� = ∏ (𝑋 − 𝑗)
{ pour tout 𝑘 ∈ {1, …, 𝑁 }
⎩ u�=0

I.B.1) Montrer que la famille {𝑃0 , …, 𝑃u� } est une base de ℝu� [𝑋], que l’on notera ℬ0 .
I.B.2)
a) Pour tout entier 𝑘 ∈ {0, …, 𝑁 − 1}, démontrer l’égalité 𝑋𝑃u� = 𝑃u�+1 + 𝑘𝑃u� .
u�
b) En déduire par récurrence que, pour tout entier 𝑛 ∈ {0, …, 𝑁 }, 𝑋 u� = ∑ 𝑆u�,u� 𝑃u� . On pourra utiliser la
u�=0
relation démontrée en I.A.2.
I.B.3) Donner la matrice 𝑀 de passage de la base ℬ0 à la base ℬ, en précisant en particulier ses coefficients
diagonaux.
I.B.4)
a) Quel est le polynôme caractéristique de la matrice 𝑀 ?
b) Montrer que la matrice 𝑀 n’est pas diagonalisable dans ℳu�+1 (ℝ) lorsque 𝑁 ⩾ 2. Qu’en est-il si 𝑁 = 1 ?

I.C – Un lien entre nombres de Stirling et loi de Poisson

+∞ u�
𝑖 u�
Pour 𝑛 ∈ ℕ et pour les réels 𝑥 pour lesquels cette somme a un sens, on pose 𝑓u� (𝑥) = ∑ 𝑥.
u�=0
𝑖!
+∞ u�
𝑖 u�
I.C.1) Déterminer le rayon de convergence de la série entière ∑ 𝑥 et en déduire le domaine de définition
u�=0
𝑖!
de la fonction 𝑓u� .
I.C.2) Déterminer les valeurs de 𝑓0 (𝑥), 𝑓1 (𝑥) et 𝑓2 (𝑥).
I.C.3) Soit 𝑘 ∈ {0, …, 𝑛} et 𝑖 ∈ ℕ. Préciser la valeur de 𝑃u� (𝑖) en distinguant les cas 0 ⩽ 𝑖 ⩽ 𝑘 − 1 (lorsque 𝑘
est non nul) et 𝑖 ⩾ 𝑘.
I.C.4) À l’aide de la relation montrée en I.B.2, vérifier que pour tout couple (𝑛, 𝑖) d’entiers naturels
u�
𝑖u� = ∑ 𝑆u�,u� 𝑃u� (𝑖)
u�=0

u� +∞ u�
𝑥u�
I.C.5) Montrer que 𝑓u� (𝑥) = ∑ 𝑆u�,u� ∑ et en déduire l’égalité 𝑓u� (𝑥) = 𝑒u� ∑ 𝑆u�,u� 𝑥u� .
u�=0 u�=u�
(𝑖 − 𝑘)! u�=0
I.C.6) Soit 𝑌 une variable aléatoire suivant une loi de Poisson de paramètre 1.
Montrer que pour tout entier 𝑛 ∈ ℕ∗ , la variable aléatoire 𝑌 u� admet une espérance 𝐸(𝑌 u� ) et donner une
expression de 𝐸(𝑌 u� ) en fonction des nombres de Stirling. Confronter les valeurs trouvées pour 𝐸(𝑌 ) et 𝐸(𝑌 2 )
avec les résultats du cours sur l’espérance et la variance d’une variable aléatoire suivant une loi de Poisson de
paramètre 𝜆.

I.D – Comportement asymptotique des nombres de Stirling

I.D.1) Pour 𝑘 ∈ ℕ, on considère l’équation différentielle

𝑦′(𝑥) = (𝑘 + 1)𝑦(𝑥) + 1 (𝑒u� − 1)u� (I.1)

𝑘!
d’inconnue 𝑦 ∈ 𝐶 1 (ℝ, ℝ).

2015-12-10 [Link] Page 2/3

 1
a) Montrer que la fonction 𝑥 ↦ (𝑒u� − 1)u�+1 est solution de (I.1).
(𝑘 + 1)!
b) Résoudre l’équation différentielle (I.1).
I.D.2) On se propose de démontrer par récurrence sur 𝑘 ∈ ℕ la proposition
+∞
𝑆u�,u� u�
∀𝑥 ∈ ℝ, ∑ 𝑥 = 1 (𝑒u� − 1)u� (I.2)
u�=u�
𝑛! 𝑘!

a) Soit 𝑘 ∈ ℕ fixé. En utilisant par exemple l’inégalité établie en I.A.6, montrer que le rayon de convergence de
+∞
𝑆u�,u� u�
la série entière ∑ 𝑥 est infini.
u�=u�
𝑛!
b) Montrer que la proposition (I.2) est vraie pour 𝑘 = 0.
c) Soit 𝑘 un entier naturel fixé tel que la proposition (I.2) soit vraie. Montrer alors, en utilisant le résultat de
+∞
𝑆u�,u�+1 u�
la question I.A.2, que la fonction 𝑥 ↦ ∑ 𝑥 est solution de l’équation différentielle (I.1).
u�=u�+1
𝑛!
d) Conclure.
1 u� 𝑘
I.D.3) En déduire, pour tous 𝑛 ∈ ℕ et 𝑘 ∈ {0, …, 𝑛}, l’égalité 𝑆u�,u� = ∑(−1)u�−u� ( )𝑗u� . On pourra
𝑘! u�=0 𝑗
commencer par développer (𝑒u� − 1)u� à l’aide de la formule du binôme de Newton.
𝑆u�,u�
I.D.4) On fixe un entier 𝑘 ∈ ℕ∗ . Déterminer lim et en déduire un équivalent de 𝑆u�,u� lorsque 𝑛 → +∞.
u�→+∞ 𝑘u�

II Nombres de Stirling et problème du collectionneur

Le problème du collectionneur (« coupon collector’s problem ») est un problème de probabilités classique. Un
fabricant de tablettes de chocolat propose à ses acheteurs de collectionner des images. Chaque tablette vendue
contient une image de la collection, que l’on découvre à l’ouverture de la tablette. Chaque image peut être collée
dans un album contenant 𝑘 emplacements (𝑘 est un entier supérieur ou égal à deux) correspondant au nombre
d’images distinctes de la collection. La probabilité pour un acheteur de découvrir dans une tablette une image
donnée est égale à 1/𝑘.
On se propose de déterminer le nombre moyen d’achats nécessaires pour constituer la collection complète des 𝑘
images et d’étudier comment les nombres de Stirling interviennent dans le problème du collectionneur.
Pour 𝑖 entier compris entre 1 et 𝑘, on note 𝑋u� le nombre minimum d’achats nécessaires pour obtenir 𝑖 vignettes
différentes et 𝑍u� le nombre minimum d’achats nécessaires pour qu’un collectionneur possédant déjà 𝑖 vignettes
distinctes puisse enrichir sa collection d’une vignette autre que celles qu’il possède déjà.
II.A – Équivalent de 𝐸(𝑋u� ) lorsque 𝑘 → +∞
II.A.1) Préciser la loi de la variable aléatoire 𝑋1 et donner 𝐸(𝑋1 ), son espérance.
II.A.2) Pour 𝑖 compris entre 1 et 𝑘 −1, vérifier que la variable aléatoire 𝑍u� suit la loi géométrique de paramètre
𝑘−𝑖
et donner 𝐸(𝑍u� ), son espérance.
𝑘
II.A.3) Pour 𝑖 compris entre 1 et 𝑘 − 1, comparer 𝑋u�+1 − 𝑋u� et 𝑍u� .
u�−1
II.A.4) En remarquant que 𝑋u� = 𝑋1 + ∑(𝑋u�+1 − 𝑋u� ), donner une expression de 𝐸(𝑋u� ), l’espérance de 𝑋u� ,
u�=1
sous la forme d’une somme.
II.A.5)
u�
1
a) Pour 𝑛 ∈ ℕ∗ , on pose 𝑢u� = (∑ ) − ln(𝑛). Montrer que la série de terme général 𝑢u� − 𝑢u�−1 (𝑛 ⩾ 2) est
u�=1
𝑖
convergente. Qu’en déduit-on pour la suite (𝑢u� )u�∈ℕ∗ ?
b) En déduire un équivalent de 𝐸(𝑋u� ) lorsque 𝑘 tend vers +∞ et interpréter ce résultat.

II.B – Équivalent de 𝑃 (𝑋u� = 𝑛) lorsque 𝑛 → +∞

Dans cette sous-partie, on fixe l’entier 𝑘.
II.B.1) Quelle est la valeur de 𝑃 (𝑋u� = 𝑛) pour 𝑛 compris entre 1 et 𝑘 − 1 ?
𝑘(𝑘 − 1)! 𝑆u�−1,u�−1
II.B.2) Montrer que si 𝑛 est un entier supérieur ou égal à 𝑘, alors 𝑃 (𝑋u� = 𝑛) = .
𝑘u�
II.B.3) En déduire un équivalent et la limite de 𝑃 (𝑋u� = 𝑛) lorsque 𝑛 → +∞, et interpréter ce résultat.

• • • FIN • • •

2015-12-10 [Link] Page 3/3