ENS Mathématiques Paris Lyon MP 2002, épreuve PLSujet et corrigé

Pas encore noté

Explorer les annales

BanqueX-ENS Année2002 FilièreMP MatièreMathématiques

Annales X-ENS MP Mathématiques X-ENS MP 2002 MP Mathématiques Mathématiques 2002

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Présentation du sujet

Formule d'inversion de Lagrange, décompositions de permutations circulaires et théorème de Kirchhoff sur les arbres couvrants

Le problème relie plusieurs domaines des mathématiques autour de l'énumération d'objets combinatoires. La première partie construit le corps des séries de Laurent formelles et démontre la formule d'inversion de Lagrange. La deuxième l'applique au dénombrement des décompositions d'une permutation circulaire en transpositions, en établissant la célèbre formule w_n = n^(n-2). La troisième démontre le théorème de Kirchhoff, qui exprime le nombre d'arbres couvrants d'un graphe à l'aide d'un déterminant, et retrouve par cette voie le résultat de la deuxième partie.

1Partie 1 : formule de LagrangeConstruire le corps des séries de Laurent formelles, définir la composition et la dérivation, et démontrer la formule d'inversion de Lagrange donnant les coefficients de la série réciproque d'une série composable.
2Partie 2 : permutationsÉtudier le nombre de transpositions nécessaires pour décomposer une permutation, établir une relation de récurrence sur le nombre de décompositions d'une permutation circulaire en produit de transpositions, et en déduire, via la formule de Lagrange, que ce nombre vaut n puissance (n-2).
3Partie 3 : arbresÉtablir des caractérisations combinatoires des arbres (graphes connexes sans cycle), démontrer le théorème de Kirchhoff reliant le nombre d'arbres couvrants d'un graphe à un déterminant de matrice, et l'utiliser pour retrouver le résultat de la partie 2 par une bijection entre décompositions et arbres étiquetés.
4Partie 4 : dénombrement d'arbres couvrantsAppliquer le théorème de Kirchhoff au graphe du cube en exploitant les symétries de ce graphe pour diagonaliser la matrice associée, et calculer le nombre de ses arbres couvrants.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

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

Sujet en PDF

SESSION 2002

Filière MP
(Epreuve commune aux ENS de Paris et Lyon)

MATHEMATIQUES

Durée : 6 heures

Ce problème est consacré à certaines propriétés énumératives d'objets combinatoires, d'une part les permutations, d'autre part les arbres.
On sera particulièrement attentif à la clarté, la précision et la concision de la rédaction. Les candidats pourront utiliser les résultats des questions non traitées.

Les parties 1, 2 et 3 sont largement indépendantes. La partie 4 utilise les résultats de la partie 3.
On notera

Z

l'ensemble des entiers relatifs,

R

le corps des nombres réels et

C

celui des nombres complexes.

1. Formule de Lagrange

Cette partie est consacrée à la démonstration de la formule d'inversion de Lagrange (question 1.11).
Une série de Laurent formelle à coefficients dans

C

est une fonction

f

Z

dans

C

telle qu'il existe

N \in Z

pour lequel

f(n) = 0

n \leq N

. On note

L

l'ensemble des séries de Laurent formelles à coefficients dans

C

. Soient

f

g \in L

, on définit leur somme par

(f + g)(n) = f(n) + g(n)

et leur produit par la formule

(f \cdot g)(n) = \sum_(k = - \infty)^\inftyf(k)g(n - k)

λ \in C

on définit

λf \in L

par

(λf)(n) = λf(n)

.
1.1 Vérifier que le produit «•» est bien défini, qu'il admet un élément neutre, et que

L

est une

C

-algèbre.
On note

f^k

les puissances d'un élément

f \in L

pour le produit «•».
Soit

(f_k)_(k \in Z)

une famille de séries de Laurent formelles telle que
(i) il existe

N

tel que

f_k(n) = 0

pour tout

k

et tout

n \leq N

,
(ii) pour tout

n

on a

f_k(n) = 0

sauf pour un nombre fini de

k

.
1.2 Montrer que la formule

f(n) = \sum_(k = - \infty)^\inftyf_k(n)

définit une série de Laurent formelle.

On note

\sum_(k = - \infty)^\inftyf_k

la série ci-dessus.
1.3 Soit

t

la série de Laurent formelle telle que

t(n) = 0

n \neq 1

t(1) = 1

. Montrer que

t

est inversible dans

L

, et que pour toute

f \in L

on a

f = \sum_(k = - \infty)^\inftyf(k)t^k

.
1.4 Soit

u

une série de Laurent formelle telle que

u(n) = 0

n \leq 0

, montrer que

1 - u

est inversible et que

(1 - u)^(- 1) = 1 + \sum_(k = 1)^\inftyu^k

.
1.5 Montrer que l'addition et le produit définissent une structure de corps commutatif sur

L

.
1.6 Soient

f

u

deux séries de Laurent formelles telles que

u(n) = 0

n \leq 0

, et

u

n'est pas identiquement nulle. Montrer que la série de Laurent formelle

f \circ u = \sum_(k = - \infty)^(+ \infty)f(k)u^k

est bien définie.
1.7 Soient

f, g, u

des séries de Laurent formelles vérifiant

f(n) = g(n) = u(n) = 0

pour

n \leq

-1 , et

u(0) = 0

. On suppose que les séries entières

F(z) = \sumf(n)z^n, G(z) = \sumg(n)z^n

U(z) = \sumu(n)z^n

ont des rayons de convergence non auls. Montrer que les séries entières

\sum(f \cdot g)(n)z^n

\sum(f \circ u)(n)z^n

ont des rayons de convergence non nuls, et valent, dans un voisinage de zéro,

F(z)G(z)

F(U(z))

respectivement.
1.8 Montrer que les séries de Laurent formelles

u

telles que

u(n) = 0

pour

n \leq 0

u(1) \neq 0

forment un groupe pour la loi de composition o.
On notera ce groupe

G

, et

u^(⟨ - 1⟩)

l'inverse dans

G

d'un élément

u

G

.
Soit

f \in L

, on définit sa dérivée

f^' \in L

par la formule

f^'(n) = (n + 1)f(n + 1)

.
1.9 Soit

f \in L, f \neq 0

, montrer que pour tout

n \in Z

on a

(f^n)^' = nf^' \cdot f^(n - 1)

.
1.10 Montrer que pour tout

u \in G

et toute

f \in L

on a

f(- 1) = (u^' \cdot (f \circ u))(- 1)

.
1.11 Soit

u \in G

, montrer que pour tout

k \geq 1

on a

u^(⟨ - 1⟩)(k) = 1/ku^(- k)(- 1)

.
1.12 En utilisant 1.11 calculer l'inverse, pour la loi de composition o, de la série de Laurent formelle

te^(- t) = \sum_(n = 0)^\infty((- 1)^n)/(n!)t^(n + 1)

. Quel est le rayon de convergence de la série entière associée à cet inverse?

2. Permutations

Soit

n

un entier

\geq 1

, on considère le groupe

Σ_n

des permutations de l'ensemble

{1, \dots, n}

. On notera

e

la permutation identique qui est l'élément neutre de

Σ_n

.
Soit

σ \in Σ_n

, on rappelle que les orbites de

σ

sont les sous-ensembles de

{1, \dots, n}

de la forme

{σ^k(s) : k ∈ ℤ}

, où

s

parcourt

{1, \dots, n}

, et qu'elles forment une partition de

{1, \dots, n}

. On note

O(σ)

le nombre d'orbites de

σ

. Pour

σ \neq e

on note

|σ|

le plus petit nombre

k

; tel que

σ

puisse s'écrire comme le produit de

k

transpositions, et on pose

|e| = 0

.
2.1 Soit

τ = (ij)

la transposition qui échange

i

j

. Déterminer

O(στ)

en fonction de

O(σ)

, suivant que

i

j

sont dans la même orbite de

σ

ou non.
2.2 Soient

σ_1

σ_2

deux permutations de

{1, \dots, n}

, montrer que

|σ_1 σ_2| \leq |σ_1| + |σ_2|

.
2.3 Montrer que

|σ| = n - O(σ)

.
2.4 Soient

σ_1

σ_2

deux permutations de

{1, \dots, n}

. Montrer que si

|σ_1| + |σ_1^(- 1)σ_2| = |σ_2|

alors toute orbite de

σ_1

est incluse dans une orbite de

σ_2

.
Soit

c \in Σ_n

une permutation circulaire d'ordre

n

, i.e une permutation ayant une seule orbite. Pour

n \geq 2

on note

w_n

le nombre de décompositions de

c

en un produit de

n - 1

transpositions, et on pose

w_1 = 1

.
2.5 Vérifier que

w_n

ne dépend pas de la permutation circulaire choisie, et montrer que les nombres

w_n

satisfont la relation de récurrence

w_n = n/2\sum_(k = 0)^(n - 2)((n - 2)!)/(k!(n - k - 2)!)w_(k + 1)w_(n - k - 1) (n \geq 2)

On pourra étudier les décompositions en produit de

n - 2

transpositions de

(ij)c

en utilisant 2.4.
2.6 On considère la série de Laurent formelle

w = \sum_(n = 1)^\infty(w_n)/((n - 1)!)t^n

. Déduire de 2.5 une relation entre

w

w^'

.
2.7 En utilisant 1.12, déduire de 2.6 que

w_n = n^(n - 2)

3. Arbres

Le résultat principal de cette partie est le Théorème de Kirchhoff (question 3.11). On l'utilise ensuite pour retrouver par une autre méthode le résultat final de la partie 2.

O_(11)

appelle graphe un comple

G = (S, A)

où

S

est un ensemble fini, dont les éléments sont appelés les sommets du graphe, et

A

un ensemble de parties à deux éléments de

S

, appelées les arêtes du graphe.
Un graphe est dit connexe si pour tout couple de sommets

(a, b)

dans

S

il existe un entier

k \geq 1

et une suite de sommets

s_1, \dotss_k

telle que

a = s_1, b = s_k

{s_i, s_(i + 1)}

est une arête pour tout

i \in {1, \dots, k - 1}

.
Un circuit de longueur

k

G

est une suite de sommets

s_1, \dots, s_k

, tous distincts, telle que

{s_i, s_(i + 1)}

pour

i = 1, \dots, k - 1

, et

{s_k, s_1}

soient des arêtes de

G

.
3.1 Soit

G

un graphe connexe à

n

sommets (

n \geq 2

), montrer que

G

a au moins

n - 1

arêtes.
3.2 Soit

G

un graphe sans circuit de longueur

\geq 3

, ayant au moins une arête, montrer qu'il existe un sommet de

G

appartenant à une seule arête.
3.3 Soit

G

un graphe connexe à

n

sommets, montrer que les conditions suivantes sont équivalentes
(i)

G

n'a pas de circuit de longueur

\geq 3

.
(ii)

G

n - 1

arêtes.

Un graphe comexe satisfaisant l'une des deux conditions équivalentes ci-dessus sera appelé un arbre.
3.4 Montrer que pour tout arbre d'ensemble de sommets

S

et tout sommet

s \in S

il existe une unique application

φ : S∖{s} \to S

telle que l'ensemble des arêtes de l'arbre soit

{{u, φ(u)}; u \in S∖{s}}

.
Soit

M

une matrice de taille

n \times n

, avec

n \geq 2

, à coefficients dans

R

. On note

M^(ii)

, pour

i \in {1, \dots, n}

, la matrice obtenue en supprimant la

è i^(ème)

ligne et la

è i^(ème)

colonne de

M

.
3.5 Soit

P(λ) = dét(M - λI)

le polynôme caractéristique de

M

, montrer que

P^'(0) = - \sum_(i = 1)^(nh)dét(M^(ii))

.
On suppose maintenant que

M

est symétrique et que ses coefficients vérifient:

pour tout i ∈ {1, …, n}, on a ∑_(j = 1)^n M_(ij) = 0.

3.6 Montrer que 0 est valeur propre de

M

.
3.7 Montrer que dét(

M^(ii)

) ne dépend pas de

i

.
3.8 Exprimer dét

(M^(ii))

en fonction des valeurs propres de

M

On note

F_n

l'ensemble des applications de

{1, \dots, n - 1}

dans

{1, \dots, n}

. Soit

φ \in F_n

, on note

E_φ

l'endomorphisme de

C^n

tel que

E_φ(e_j) = e_(φ(j))

pour tout

j \in {1, \dots, n - 1}

E_φ(e_n) = 0

, où

(e_j)_(1 \leq j \leq n)

désigne la base canonique de

C^n

.
3.9 Montrer que dét

(M^(nn)) = - \sum_(φ \in F_n)\prod_(j = 1)^(n - 1)M_(jφ(j))dét(E_φ - I)

.
3.10 Montrer que s'il existe

k \geq 1

a_1, …, a_k ∈ {1, …, n − 1}

tels que

φ(a_j) = a_(j + 1)

pour

j = 1, \dots, k

, et

φ(a_k) = a_1

, alors dét

(E_φ - I) = 0

. Montrer que dans le cas contraire la puissance

è n^(ème)

E_φ

est nulle, et que

{{i, φ(i)}; i \in {1, \dots, n - 1}}

est l'ensemble des arêtes d'un arbre d'ensemble de sommets

{1, \dots, n}

. Que vaut dét

(E_φ - I)

dans ce cas?
On note

T_n

l'ensemble des arbres dont l'ensemble des sommets est

{1, \dots, n}

.
3.11 Déduire des questions 3.4, 3.9 et 3.10 l'identité

dét(M^(nn^n)) = (− 1)^(n − 1)∑_((S, A) ∈ T_n)∏_({i, j} ∈ A)M_(ij).

3.12 En utilisant 3.8 et 3.11 , calculer le nombre d'éléments de

T_n

On note

F

l'ensemble des

n

-uplets (

c, τ_1, \dots, τ_(n - 1)

) où

c

est une permutation circulaire d'ordre

n

dans

Σ_n

, et

τ_1, \dots, τ_(n - 1)

sont des transpositions satisfaisant

c = τ_1\dotsτ_(n - 1)

. Soit

Ω

l'ensemble des couples (

(S, A), ω

) où (

S, A

) est un arbre de sommets

S = {1, \dots, n}

ω = (a_1, \dots, a_(n - 1))

est une énumération de l'ensemble des arêtes de (

S, A

). Pour chaque partie à deux éléments

{i, j} \subset S

on note

τ({i, j})

la transposition

(ij)

.
3.13 Montrer que l'application qui à tout

((S, A), (a_1, \dots, a_(n - 1))) \in Ω

associe

(τ(a_1)\dotsτ(a_(n - 1)), τ(a_1), \dots, τ(a_(n - 1)))

est whe bijection entre

Ω

F

.
3.14 En utilisant 3.12 et 3.13 , retrouver le résultat de la question 2.7.

4. Dénombrement d'arbres couvrants

On reprend les notations de la partie 3.
O

è_(n considère le cube de)R^3

dont les sommets sont les points de coordonnées (

x_1, x_2, x_3

) vérifiant

x_1^2 = x_2^2 = x_3^3 = 1

. Soit

G = (S, A)

le graphe dont les sommets sont les sommets du cube et les arêtes sont les paires de sommets dont la distance mutuelle est 2 , pour la distance usuelle de

R^3

. On notera

s_1, \dots, s_8

les sommets du cube.

Soit

V

un espace vectoriel réel de dimension 8 , dont on choisit une base (

e_(s_j); j = 1, \dots, 8

) indexée par les sommets du cube. On note

γ_i

, pour

i = 1, 2, 3

la symétric orthogonale
de

R^3

par rapport au plan d'équation

x_i = 0

. Soit

ε_i

l'endomorphisme de

V

tel que

ε_i(e_(s_k)) = e_(γ_i(s_k))

pour

k = 1, \dots, 8

.
4.1 Vérifier que les endomorphismes

ε_1, ε_2

ε_3

commutent et déterminer une base formée de vecteurs propres communs à ces endomorphismes.

Soit

M

la matrice de taille

8 \times 8

telle que
(i)

M_(ij) = 1

i \neq j

, et si les sommets

s_i

s_j

sont sur une même arête du cube,
(ii)

M_(ij) = 0

i \neq j

et les sommets

s_i

s_j

ne sont pas sur une même arête du cube,
(iii)

M

vérifie la condition

(*)

précédant 3.6 .
4.2 Exprimer la matrice

M

à l'aide des matrices des endomorphismes

ε_1, ε_2

ε_3

dans la base

(e_(s_j))_(1 \leq j \leq 8)

.
4.3 En utilisant les questions 3.8 et 3.11 , déterminer le nombre d'arbres d'ensemble de sommets

S

, dont les arêtes sont dans

A

. Ces arbres sont appelés les arbres couvrants du cube.
4.4 Quel est le nombre d'arbres couvrants pour un cube de dimension

n

Questions fréquentes

4 questions

Sur quels chapitres porte ce sujet de maths des ENS MP 2002 ?

Il porte sur les séries formelles, la combinatoire des permutations, la théorie des graphes et l'algèbre linéaire (réduction des matrices symétriques), reliées entre elles par des méthodes de dénombrement.

Les parties de ce sujet sont-elles indépendantes ?

Les parties 1, 2 et 3 sont largement indépendantes entre elles, mais la partie 4 utilise les résultats de la partie 3 (théorème de Kirchhoff).

Qu'est-ce que le théorème de Kirchhoff démontré dans ce sujet ?

C'est un résultat qui exprime le nombre d'arbres couvrants d'un graphe comme un déterminant construit à partir de sa matrice d'incidence, utilisé ici pour dénombrer les arbres couvrants d'un graphe donné, comme celui du cube.

Ce sujet aborde-t-il la formule d'inversion de Lagrange ?

Oui, la première partie construit les outils nécessaires (séries de Laurent formelles) pour démontrer cette formule, ensuite utilisée en partie 2 pour dénombrer les décompositions d'une permutation circulaire.

Pas de description pour le moment

Commentaires• ENS Mathématiques Paris Lyon MP 2002, épreuve PL

Connectez-vous pour participer aux discussions

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

Chargement des commentaires...

Explorer les annales

Téléchargements

Présentation du sujet

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

Filière MP (Epreuve commune aux ENS de Paris et Lyon)

MATHEMATIQUES

1. Formule de Lagrange

2. Permutations

3. Arbres

4. Dénombrement d'arbres couvrants

Questions fréquentes

Sur quels chapitres porte ce sujet de maths des ENS MP 2002 ?

Les parties de ce sujet sont-elles indépendantes ?

Qu'est-ce que le théorème de Kirchhoff démontré dans ce sujet ?

Ce sujet aborde-t-il la formule d'inversion de Lagrange ?

Commentaires• ENS Mathématiques Paris Lyon MP 2002, épreuve PL

Commentaires• ENS Mathématiques Paris Lyon MP 2002, épreuve PL

Filière MP
(Epreuve commune aux ENS de Paris et Lyon)