Centrale Mathématiques 1 TSI 2016Sujet

Pas encore noté

Dénombrement, partitions d'un ensemble
Polynômes, bases et changement de base
Réduction des matrices (polynôme caractéristique, diagonalisabilité)
Séries entières
Variables aléatoires discrètes, loi de Poisson, loi géométrique
Espérance et moments d'une variable aléatoire
Équations différentielles linéaires
Suites et séries numériques, équivalents

Explorer les annales

BanqueCentrale Année2016 FilièreTSI MatièreMathématiques

Annales Centrale TSI Mathématiques Centrale TSI 2016 TSI Mathématiques Mathématiques 2016

Téléchargements

Télécharger le sujet (PDF)

Lire en ligne LaTeX Word

Corrigé : pas encore disponible
Rapport du jury : non disponible

Présentation du sujet

Les nombres de Stirling de deuxième espèce et le problème du collectionneur de vignettes

Le problème introduit les nombres de Stirling de deuxième espèce, qui comptent les partitions d'un ensemble en un nombre donné de parties, et établit leurs premières propriétés combinatoires. Il les relie ensuite à une base particulière de l'espace des polynômes, à la loi de Poisson, puis étudie leur comportement asymptotique. La seconde partie applique ces résultats au problème probabiliste du collectionneur de vignettes.

1I.A - Premières propriétés des nombres de StirlingÉtablir des valeurs particulières et une relation de récurrence sur les nombres de Stirling à partir de dénombrements de partitions et d'applications surjectives.
2I.B - Utilisation des nombres de Stirling en algèbre linéaireConstruire une base de l'espace des polynômes à partir de produits de facteurs (X-j) et exprimer les nombres de Stirling comme coefficients de changement de base, puis étudier la diagonalisabilité de la matrice de passage associée.
3I.C - Un lien entre nombres de Stirling et loi de PoissonÉtudier une famille de séries entières liées aux nombres de Stirling et en déduire une expression des moments d'une variable aléatoire suivant une loi de Poisson.
4I.D - Comportement asymptotique des nombres de StirlingRésoudre une équation différentielle linéaire pour obtenir le développement en série entière des nombres de Stirling, puis en déduire une formule explicite et un équivalent lorsque n tend vers l'infini.
5II.A - Équivalent de E(X_k) lorsque k tend vers l'infiniModéliser le nombre d'achats nécessaires pour compléter une collection à l'aide de variables géométriques et obtenir un équivalent de son espérance.
6II.B - Équivalent de P(X_k = n) lorsque n tend vers l'infiniExprimer la loi du nombre d'achats nécessaires à l'aide des nombres de Stirling et en déduire un équivalent de cette probabilité.

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

Nombres de Stirling et problème du collectionneur

Ce problème est consacré à l'étude de nombre introduits au XVIII

^e

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

\foralla \in ℝ, a^0 = 1

et on note

$C^1(ℝ, ℝ)$ l'ensemble des fonctions de $ℝ$ dans $ℝ$ , dérivables sur $ℝ$ et dont la dérivée est continue sur $ℝ$ ;
$M_n(ℝ)$ l'ensemble des matrices carrées d'ordre $n$ à coefficients réels.

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

E

est un ensemble et

k

un entier naturel non nul, une partition de

E

est un ensemble

{A_1, …, A_k}

de parties de

E

non vides, deux à deux disjointes, et dont la réunion est égale à

E

∀i ∈ {1, …, k}, A_i ≠ ∅ ∀(i, j) ∈ {1, …, k}^2, i ≠ j ⟹ A_i ∩ A_j = ∅ ⋃_(i = 1)^k A_i = E

Par exemple,

{{1}, {2, 3}, {4, 5}}

est une partition de

E = {1, 2, 3, 4, 5}

en trois parties. On notera en particulier que l'ordre dans lequel interviennent les parties

A_1, \dots, A_k

n'a pas d'incidence sur la définition de la partition.
Pour

n \in ℕ^*

k \in {1, \dots, n}

, on note

S_(n, k)

le nombre de partitions d'un ensemble à

n

éléments en

k

parties. On pose également

S_(0, 0) = 1

S_(n, 0) = 0

lorsque

n \in ℕ^*

.
Les nombres

S_(n, k)

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

S_(3, 2)

.
b) Soit

n \in ℕ^*

. Que valent

S_(n, 1)

S_(n, n)

?
I.A.2) Soit

n

un entier,

n ⩾ 2, k

un entier compris entre 1 et

n - 1

E = {x_1, …, x_n}

un ensemble à

n

éléments. On souhaite établir une relation entre

S_(n, k), S_(n - 1, k - 1)

S_(n - 1, k)

.
a) Dans cette question, on étudie l'exemple

E = {1, 2, 3, 4}(n = 4)

k = 2

.
i. Expliciter les partitions de

E

en deux parties, dont l'une est le singleton

{4}

.
ii. Expliciter les partitions de

E

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

S_(n, k) = S_(n - 1, k - 1) + kS_(n - 1, k)

.
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

E

k

parties, dont l'une est

{x_n}

? On exprimera le résultat à l'aide d'un nombre de Stirling.
ii. Quel est le nombre de partitions de

E

k

parties, dont l'une contient

x_n

tout en étant différente du singleton

{x_n}

? On exprimera le résultat à l'aide d'un nombre de Stirling.
iii. En déduire que

S_(n, k) = S_(n - 1, k - 1) + kS_(n - 1, k)

.
I.A.3) En déduire que, pour tout entier

n ⩾ 2, S_(n, n - 1) = (n(n - 1))/2

. On pourra par exemple procéder par récurrence.
I.A.4) Montrer que, pour tout entier

n ⩾ 3, S_(n, 2) + 1 = 2(S_(n - 1, 2) + 1)

et en déduire la valeur de

S_(n, 2)

pour tout entier

n ⩾ 2

.
I.A.5) Soient

n \in ℕ^*, k \in ℕ^*

et deux ensembles

E = {x_1, …, x_n}

F = {y_1, …, y_k}

. On note

σ_(n, k)

le nombre d'applications surjectives de

E

dans

F

.
a) Que vaut

σ_(n, k)

n < k

?
b) Que vaut

σ_(n, k)

n = k

?
c) Expliciter les applications surjectives de

E

dans

F

lorsque

n = 3

k = 2

, et préciser la valeur de

σ_(3, 2)

.
d) Dans cette question, on souhaite obtenir une relation entre

σ_(n, k)

S_(n, k)

f

est une application de

E

dans

F

j

un entier compris entre 1 et

k

, on note

A_j = f^(− 1)({y_j})

l'ensemble des antécédents par

f

y_j

.
i. Étant donnée une application

f

surjective de

E

dans

F

, montrer que

A = {A_1, …, A_k}

est une partition de

E

k

parties. On note

Π(f)

cette partition.
ii. Étant donnée

A^′ = {A_1^′, …, A_k^′}

une partition de

E

k

parties, combien y a-t-il d'applications

f

surjectives de

E

dans

F

telles que

Π(f) = A^'

?
iii. En déduire la relation

σ_(n, k) = k!S_(n, k)

.
I.A.6) Montrer, par exemple par récurrence, que, pour tout

n ∈ ℕ, ∀k ∈ {0, …, n}, S_(n, k) ⩽ (2k)^n

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

Soit

N \in ℕ^*

; on note

ℝ_N[X]

l'ensemble des polynômes à coefficients réels de degré inférieur ou égal à

N

B

la base canonique de

ℝ_N[X]

. On définit la famille de polynômes

(P_k)_(0 ⩽ k ⩽ N)

par

{P_0 = 1; P_k = ∏_(j = 0)^(k − 1)(X − j) pour tout k ∈ {1, …, N}

I.B.1) Montrer que la famille

{P_0, …, P_N}

est une base de

ℝ_N[X]

, que l'on notera

B_0

.
I.B.2)
a) Pour tout entier

k \in {0, \dots, N - 1}

, démontrer l'égalité

XP_k = P_(k + 1) + kP_k

.
b) En déduire par récurrence que, pour tout entier

n ∈ {0, …, N}, X^n = ∑_(k = 0)^n S_(n, k)P_k

. On pourra utiliser la relation démontrée en I.A.2.
I.B.3) Donner la matrice

M

de passage de la base

B_0

à la base

B

, en précisant en particulier ses coefficients diagonaux.
I.B.4)
a) Quel est le polynôme caractéristique de la matrice

M

?
b) Montrer que la matrice

M

n'est pas diagonalisable dans

M_(N + 1)(ℝ)

lorsque

N ⩾ 2

. Qu'en est-il si

N = 1

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

Pour

n \in ℕ

et pour les réels

x

pour lesquels cette somme a un sens, on pose

f_n(x) = \sum_(i = 0)^(+ \infty)(i^n)/(i!)x^i

.
I.C.1) Déterminer le rayon de convergence de la série entière

\sum_(i = 0)^(+ \infty)(i^n)/(i!)x^i

et en déduire le domaine de définition de la fonction

f_n

.
I.C.2) Déterminer les valeurs de

f_0(x), f_1(x)

f_2(x)

.
I.C.3) Soit

k \in {0, \dots, n}

i \in ℕ

. Préciser la valeur de

P_k(i)

en distinguant les cas

0 ⩽ i ⩽ k - 1

(lorsque

k

est non nul) et

i ⩾ k

.
I.C.4) À l'aide de la relation montrée en I.B.2, vérifier que pour tout couple (

n, i

) d'entiers naturels

i^n = \sum_(k = 0)^n S_(n, k)P_k(i)

I.C.5) Montrer que

f_n(x) = \sum_(k = 0)^n S_(n, k)\sum_(i = k)^(+ \infty)(x^i)/((i - k)!)

et en déduire l'égalité

f_n(x) = e^x\sum_(k = 0)^n S_(n, k)x^k

.
I.C.6) Soit

Y

une variable aléatoire suivant une loi de Poisson de paramètre 1.

Montrer que pour tout entier

n \in ℕ^*

, la variable aléatoire

Y^n

admet une espérance

E(Y^n)

et donner une expression de

E(Y^n)

en fonction des nombres de Stirling. Confronter les valeurs trouvées pour

E(Y)

E(Y^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

k \in ℕ

, on considère l'équation différentielle

y^'(x) = (k + 1)y(x) + 1/(k!)(e^x - 1)^k

d'inconnue

y \in C^1(ℝ, ℝ)

.
a) Montrer que la fonction

x \mapsto 1/((k + 1)!)(e^x - 1)^(k + 1)

est solution de (I.1).
b) Résoudre l'équation différentielle (I.1).
I.D.2) On se propose de démontrer par récurrence sur

k \in ℕ

la proposition

\forallx \in ℝ, \sum_(n = k)^(+ \infty)(S_(n, k))/(n!)x^n = 1/(k!)(e^x - 1)^k

a) Soit

k \in ℕ

fixé. En utilisant par exemple l'inégalité établie en I.A.6, montrer que le rayon de convergence de la série entière

\sum_(n = k)^(+ \infty)(S_(n, k))/(n!)x^n

est infini.
b) Montrer que la proposition (I.2) est vraie pour

k = 0

.
c) Soit

k

un entier naturel fixé tel que la proposition (I.2) soit vraie. Montrer alors, en utilisant le résultat de la question I.A.2, que la fonction

x \mapsto \sum_(n = k + 1)^(+ \infty)(S_(n, k + 1))/(n!)x^n

est solution de l'équation différentielle (I.1).
d) Conclure.
I.D.3) En déduire, pour tous

n \in ℕ

k \in {0, \dots, n}

, l'égalité

S_(n, k) = 1/(k!)\sum_(j = 0)^k(- 1)^(k - j)(k/j)j^n

. On pourra commencer par développer

(e^x - 1)^k

à l'aide de la formule du binôme de Newton.
I.D.4) On fixe un entier

k \in ℕ^*

. Déterminer

lim_(n \to + \infty)(S_(n, k))/(k^n)

et en déduire un équivalent de

S_(n, k)

lorsque

n \to + \infty

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

k

emplacements (

k

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/k

.
On se propose de déterminer le nombre moyen d'achats nécessaires pour constituer la collection complète des

k

images et d'étudier comment les nombres de Stirling interviennent dans le problème du collectionneur.
Pour

i

entier compris entre 1 et

k

, on note

X_i

le nombre minimum d'achats nécessaires pour obtenir

i

vignettes différentes et

Z_i

le nombre minimum d'achats nécessaires pour qu'un collectionneur possédant déjà

i

vignettes distinctes puisse enrichir sa collection d'une vignette autre que celles qu'il possède déjà.
II.A - Équivalent de

E(X_k)

lorsque

k \to + \infty

II.A.1) Préciser la loi de la variable aléatoire

X_1

et donner

E(X_1)

, son espérance.
II.A.2) Pour

i

compris entre 1 et

k - 1

, vérifier que la variable aléatoire

Z_i

suit la loi géométrique de paramètre

(k - i)/k

et donner

E(Z_i)

, son espérance.
II.A.3) Pour

i

compris entre 1 et

k - 1

, comparer

X_(i + 1) - X_i

Z_i

.
II.A.4) En remarquant que

X_k = X_1 + \sum_(i = 1)^(k - 1)(X_(i + 1) - X_i)

, donner une expression de

E(X_k)

, l'espérance de

X_k

, sous la forme d'une somme.

II.A.5)

a) Pour

n \in ℕ^*

, on pose

u_n = (\sum_(i = 1)^n 1/i) - ln(n)

. Montrer que la série de terme général

u_n - u_(n - 1)(n ⩾ 2)

est convergente. Qu'en déduit-on pour la suite

(u_n)_(n \in ℕ^*)

?
b) En déduire un équivalent de

E(X_k)

lorsque

k

tend vers

+ \infty

et interpréter ce résultat.
II.B - Équivalent de

P(X_k = n)

lorsque

n \to + \infty

Dans cette sous-partie, on fixe l'entier

k

.
II.B.1) Quelle est la valeur de

P(X_k = n)

pour

n

compris entre 1 et

k - 1

?
II.B.2) Montrer que si

n

est un entier supérieur ou égal à

k

, alors

P(X_k = n) = (k(k - 1)!S_(n - 1, k - 1))/(k^n)

.
II.B.3) En déduire un équivalent et la limite de

P(X_k = n)

lorsque

n \to + \infty

, et interpréter ce résultat.

Questions fréquentes

4 questions

Sur quels chapitres porte ce sujet de maths 1 sur les nombres de Stirling ?

Le sujet mobilise le dénombrement (partitions d'ensembles), les polynômes et le changement de base, la réduction des matrices, les séries entières, les probabilités discrètes (loi de Poisson, loi géométrique) et les équations différentielles linéaires.

Les parties de ce sujet sur les nombres de Stirling sont-elles indépendantes ?

Oui, l'énoncé précise explicitement que les parties du problème sont très largement indépendantes, et autorise à admettre un résultat précédent pour aborder la suite, à condition de le signaler.

Qu'étudie la seconde partie de ce sujet, sur le problème du collectionneur ?

Elle applique les résultats de la première partie au problème classique du collectionneur de vignettes : le nombre moyen d'achats nécessaires pour compléter une collection, et la loi de probabilité de ce nombre d'achats, exprimée à l'aide des nombres de Stirling.

Faut-il des connaissances avancées en probabilités pour ce sujet ?

Le sujet utilise l'espérance de variables aléatoires discrètes, notamment la loi géométrique et la loi de Poisson, ainsi que la notion de somme de variables aléatoires, ce qui correspond au programme de probabilités de deuxième année.

Pas de description pour le moment

Commentaires• Centrale Mathématiques 1 TSI 2016

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...