SESSION 2002

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 l'ensemble des entiers relatifs, le corps des nombres réels et celui des nombres complexes.

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 est une fonction de dans telle qu'il existe pour lequel si . On note l'ensemble des séries de Laurent formelles à coefficients dans . Soient et , on définit leur somme par et leur produit par la formule Si on définit par .
1.1 Vérifier que le produit «•» est bien défini, qu'il admet un élément neutre, et que est une -algèbre.
On note les puissances d'un élément pour le produit «•».
Soit une famille de séries de Laurent formelles telle que
(i) il existe tel que pour tout et tout ,
(ii) pour tout on a sauf pour un nombre fini de .
1.2 Montrer que la formule définit une série de Laurent formelle.

On note la série ci-dessus.
1.3 Soit la série de Laurent formelle telle que si et . Montrer que est inversible dans , et que pour toute on a .
1.4 Soit une série de Laurent formelle telle que si , montrer que est inversible et que .
1.5 Montrer que l'addition et le produit définissent une structure de corps commutatif sur .
1.6 Soient et deux séries de Laurent formelles telles que si , et n'est pas identiquement nulle. Montrer que la série de Laurent formelle est bien définie.
1.7 Soient des séries de Laurent formelles vérifiant pour -1 , et . On suppose que les séries entières et ont des rayons de convergence non auls. Montrer que les séries entières
et ont des rayons de convergence non nuls, et valent, dans un voisinage de zéro, et respectivement.
1.8 Montrer que les séries de Laurent formelles telles que pour et forment un groupe pour la loi de composition o.
On notera ce groupe , et l'inverse dans d'un élément de .
Soit , on définit sa dérivée par la formule .
1.9 Soit , montrer que pour tout on a .
1.10 Montrer que pour tout et toute on a .
1.11 Soit , montrer que pour tout on a .
1.12 En utilisant 1.11 calculer l'inverse, pour la loi de composition o, de la série de Laurent formelle . Quel est le rayon de convergence de la série entière associée à cet inverse?

Soit un entier , on considère le groupe des permutations de l'ensemble . On notera la permutation identique qui est l'élément neutre de .
Soit , on rappelle que les orbites de sont les sous-ensembles de de la forme , où parcourt , et qu'elles forment une partition de . On note le nombre d'orbites de . Pour on note le plus petit nombre ; tel que puisse s'écrire comme le produit de transpositions, et on pose .
2.1 Soit la transposition qui échange et . Déterminer en fonction de , suivant que et sont dans la même orbite de ou non.
2.2 Soient et deux permutations de , montrer que .
2.3 Montrer que .
2.4 Soient et deux permutations de . Montrer que si alors toute orbite de est incluse dans une orbite de .
Soit une permutation circulaire d'ordre , i.e une permutation ayant une seule orbite. Pour on note le nombre de décompositions de en un produit de transpositions, et on pose .
2.5 Vérifier que ne dépend pas de la permutation circulaire choisie, et montrer que les nombres satisfont la relation de récurrence

On pourra étudier les décompositions en produit de transpositions de en utilisant 2.4.
2.6 On considère la série de Laurent formelle . Déduire de 2.5 une relation entre et .
2.7 En utilisant 1.12, déduire de 2.6 que .

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.
appelle graphe un comple où est un ensemble fini, dont les éléments sont appelés les sommets du graphe, et un ensemble de parties à deux éléments de , appelées les arêtes du graphe.
Un graphe est dit connexe si pour tout couple de sommets dans il existe un entier et une suite de sommets telle que et est une arête pour tout .
Un circuit de longueur de est une suite de sommets , tous distincts, telle que pour , et soient des arêtes de .
3.1 Soit un graphe connexe à sommets ( ), montrer que a au moins arêtes.
3.2 Soit un graphe sans circuit de longueur , ayant au moins une arête, montrer qu'il existe un sommet de appartenant à une seule arête.
3.3 Soit un graphe connexe à sommets, montrer que les conditions suivantes sont équivalentes
(i) n'a pas de circuit de longueur .
(ii) a 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 et tout sommet il existe une unique application telle que l'ensemble des arêtes de l'arbre soit .
Soit une matrice de taille , avec , à coefficients dans . On note , pour , la matrice obtenue en supprimant la ligne et la colonne de .
3.5 Soit le polynôme caractéristique de , montrer que .
On suppose maintenant que est symétrique et que ses coefficients vérifient:

3.6 Montrer que 0 est valeur propre de .
3.7 Montrer que dét( ) ne dépend pas de .
3.8 Exprimer dét en fonction des valeurs propres de .

On note l'ensemble des applications de dans . Soit , on note l'endomorphisme de tel que pour tout et , où désigne la base canonique de .
3.9 Montrer que dét .
3.10 Montrer que s'il existe et tels que pour , et , alors dét . Montrer que dans le cas contraire la puissance de est nulle, et que est l'ensemble des arêtes d'un arbre d'ensemble de sommets . Que vaut dét dans ce cas?
On note l'ensemble des arbres dont l'ensemble des sommets est .
3.11 Déduire des questions 3.4, 3.9 et 3.10 l'identité

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

On note l'ensemble des -uplets ( ) où est une permutation circulaire d'ordre dans , et sont des transpositions satisfaisant . Soit l'ensemble des couples ( ) où ( ) est un arbre de sommets et est une énumération de l'ensemble des arêtes de ( ). Pour chaque partie à deux éléments on note la transposition .
3.13 Montrer que l'application qui à tout associe

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

On reprend les notations de la partie 3.
O dont les sommets sont les points de coordonnées ( ) vérifiant . Soit 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 . On notera les sommets du cube.

Soit un espace vectoriel réel de dimension 8 , dont on choisit une base ( ) indexée par les sommets du cube. On note , pour la symétric orthogonale
de par rapport au plan d'équation . Soit l'endomorphisme de tel que pour .
4.1 Vérifier que les endomorphismes et commutent et déterminer une base formée de vecteurs propres communs à ces endomorphismes.

Soit la matrice de taille telle que
(i) si , et si les sommets et sont sur une même arête du cube,
(ii) si et les sommets et ne sont pas sur une même arête du cube,
(iii) vérifie la condition précédant 3.6 .
4.2 Exprimer la matrice à l'aide des matrices des endomorphismes et dans la base .
4.3 En utilisant les questions 3.8 et 3.11 , déterminer le nombre d'arbres d'ensemble de sommets , dont les arêtes sont dans . Ces arbres sont appelés les arbres couvrants du cube.
4.4 Quel est le nombre d'arbres couvrants pour un cube de dimension ?