Les correcteurs attendent des réponses précises et concises aux questions posées. Les algorithmes demandés seront exprimés avec un point de vue de haut niveau, sans décrire l'implantation effective ni les structures de données utilisées. On pourra par exemple s'inspirer de l'algorithme donné dans l'énoncé de la Question 1.7.
Préliminaires
Soit l'ensemble des entiers naturels et soit l'ensemble privé de 0 .
Pour , soit le groupe symétrique de degré , c'est-à-dire l'ensemble des permutations de muni de la composition comme loi de groupe. L'élément neutre de est noté . La composition des permutations est notée multiplicativement, on écrit donc pour ou pour l'inverse de . Le support de la permutation est . La transposition , est la permutation de support . Le cycle , , est la permutation de support telle que pour , et . On pose . On représente une permutation à l'aide du mot .
1 Cartes, mélange et réussite
Soit un ensemble de cartes, chacune d'entre elles étant numérotée par un entier différent entre 1 et . Les cartes sont mélangées dans un ordre quelconque et arrangées en une pile. Plus formellement, une pile de cartes s'identifie à la permutation de où est le numéro de la carte en -ième position dans la pile.
On définit un déplacement élémentaire comme l'opération consistant à changer de position une carte dans la pile. On évalue alors le degré de mélange de la pile par le nombre minimal de déplacements élémentaires nécessaire pour obtenir la pile en partant de la pile .
Soit l'ensemble de permutations . On rappelle que les éléments de engendrent . On définit de la façon suivante :
On remarque que est la pile de cartes obtenue à partir de la pile en déplaçant la carte en position jusqu'à la position . Ainsi est une évaluation du mélange de la pile .
Question 1.1. Soit , montrer que: . Soit , montrer que: .
Tournez la page S.V.P.
Question 1.2. Soit avec . Déterminer .
Étant donné une permutation , une sous-suite croissante de est une suite d'indices tels que . Une sous-suite décroissante est une suite d'indices ( ) tels que . La longueur de la sous-suite est le nombre d'indices. On note le maximum des longueurs des sous-suites croissantes de .
Question 1.3. Soit . Démontrer l'égalité . (On pourra commencer par montrer que .)
Une réussite est un jeu de cartes à un joueur obéissant à des règles systématiques et ne faisant donc pas intervenir la réflexion. On s'intéresse à une réussite se jouant avec une pile de cartes de la façon suivante :
La première carte de la pile est posée sur la table de jeu;
puis, jusqu'à ce que la pile soit vide, la carte du dessus de la pile est posée sur la table comme suit :
si la nouvelle carte a un numéro supérieur à ceux des cartes déjà posées et situées en bas d'une colonne, alors elle est disposée sur une nouvelle colonne à droite des cartes déjà posées;
sinon la nouvelle carte est posée tout en bas de la colonne la plus à gauche ne contenant que des cartes de numéros supérieurs au sien.
Pour bien comprendre le mécanisme de cette réussite, considérons une pile de 7 cartes dans l'ordre . La suite des configurations obtenues au cours de la réussite est la suivante :
Fig. 1 - Réussite
Question 1.4. On joue la réussite sur la pile de cartes associée à la permutation . Montrer que le nombre de colonnes de la configuration finale est égal à . (On remarquera que dans l'exemple de la figure 1, la ligne du bas ne correspond pas à une sous-suite croissante de la permutation.)
Question 1.5. Proposer un algorithme prenant en entrée une permutation de et retournant en sortie une sous-suite croissante de longueur maximale de .
L'ensemble engendre . On définit par
On voit que correspond à une autre évaluation du mélange de .
Question 1.6. Le nombre d'inversions d'une permutation est par définition . Montrer que .
Question 1.7. Démontrer avec soin que l'algorithme ci-dessous permet de calculer .
$\mathcal{K}$-mélange $\left(n, \sigma \in \mathfrak{S}_{n}\right)$
inv $\leftarrow 0$
pour $i$ de $n$ à 2 par pas de -1 faire
$k \leftarrow \sigma^{-1}(i)$
si $k<i$ faire
$\sigma \leftarrow \sigma(k, k+1) \cdots(i-1, i), \operatorname{inv} \leftarrow \operatorname{inv}+i-k$
retourner inv
On remarque que . Il est alors naturel de modifier l'algorithme en remplaçant la ligne 5 par
Le nouvel algorithme retourne-t-il en sortie ?
2 Tableaux de Young
L'objet de cette partie est d'étudier de façon plus fine la combinatoire de et de à l'aide des tableaux de Young.
Une partition de est une suite d'entiers vérifiant et . On utilise la notation pour indiquer que est une partition de .
Question 2.1. Écrire un algorithme récursif prenant en entrée et retournant en sortie le nombre de partitions de .
Le diagramme de Ferrers de est une collection de cases arrangées en lignes alignées par la gauche, la -ième ligne en partant du bas contenant cases. Il est souvent utile d'identifier le diagramme de Ferrers avec le sous-ensemble de correspondant aux positions des
Tournez la page S.V.P.
cases, i.e. avec . La taille du diagramme de Ferrers est le nombre de cases. À titre d'exemple, le diagramme de Ferrers de est représenté sur la gauche de la figure 2.
Un tableau de Young partiel de taille est un diagramme de Ferrers de taille dont les cases sont numérotées par des entiers distincts et strictement positifs, de telle sorte que les numéros soient croissants de la gauche vers la droite dans chaque ligne et de bas en haut dans chaque colonne.
Un tableau de Young de taille est un tableau de Young partiel de taille dans lequel, de plus, les cases sont numérotées par les entiers de 1 à . Un tableau de Young est représenté à droite de la figure 2.
Fig. 2 - Diagramme de Ferrers et tableau de Young
On abrège l'expression "tableau de Young" en "tableau", lorsque ceci ne prête pas à confusion. On remarque que tout tableau est un tableau partiel, et d'autre part que toute ligne et toute colonne d'un tableau est un tableau partiel.
La forme d'un tableau partiel , notée , est le diagramme de Ferrers obtenu en oubliant les numéros (ou encore la partition correspondante).
Étant donné un tableau partiel , l'ensemble des entiers apparaissant dans les cases de est noté num . On identifie avec l'application : définie par si et si est l'entier apparaissant dans la case ( ), et par . On note ., le tableau partiel formé de la -ième colonne, respectivement -ième ligne, de .
On appelle tableau vide l'application définie par . La taille de est 0 et on pose et . Si est un tableau partiel tel que contient lignes et colonnes, alors par convention pour et .
On définit une procédure qui prend en entrée ( ) où est soit un tableau partiel soit le tableau vide, et où . L'algorithme fonctionne avec la convention : . On note le résultat retourné en sortie par l'algorithme.
Insertion-ligne ( )
$\alpha \leftarrow 1$
tant que $x<\max \{k \mid k \in \operatorname{num}(T(., \alpha))\}$ faire.
$y \leftarrow \min \{k \mid k \in \operatorname{num}(T(., \alpha)), x<k\}$
soit $(j, \alpha)$ tel que $T(j, \alpha)=y$, faire $T(j, \alpha) \leftarrow x, x \leftarrow y$
$\alpha \leftarrow \alpha+1$
fintantque
soit $j$ la taille de $T(., \alpha)$ faire $T(j+1, \alpha) \leftarrow x$
retourner $T$
On vérifie aisément que est un tableau partiel qui contient une case de plus que le tableau d'entrée et tel que . Il est instructif de suivre l'exécution de la procédure sur un exemple. Dans la figure ci-dessous, l'insertion de 4 dans le tableau partiel de gauche donne en sortie le tableau de droite.
Fig. 3 - Insertion en ligne d'un entier dans un tableau partiel
Question 2.2. Étant donné , on note le tableau de Young obtenu en sortie de l'algorithme suivant:
Montrer que la ligne du bas de est constituée de cases.
On peut définir une opération d'insertion en colonne duale de l'insertion en ligne définie plus haut. Plus précisément, il suffit dans l'algorithme Insertion-ligne de remplacer ( ) par ( ) pour . On note le tableau partiel obtenu par l'insertion en colonne dans de l'entier . On admet le résultat de commutation suivant (la preuve est élémentaire mais peu instructive) : soit un tableau partiel et soit , on a
Étant donné un tableau partiel , on définit le tableau partiel transposé par: . Étant donné une permutation , la permutation miroir est définie par .
Tournez la page S.V.P.
Question 2.3. Soit une permutation. Montrer que l'on a . Démontrer que le maximum des longueurs des sous-suites décroissantes de est égal au nombre de cases dans la colonne de gauche de .
La pile est obtenue par retournement de la pile . On peut argumenter qu'une bonne mesure du degré de mélange de la pile est .
Question 2.4. Soit . Montrer que . Donner explicitement une permutation telle que .
On présente maintenant l'algorithme dit de Robinson-Schensted.
$P \leftarrow \Theta, Q \leftarrow \Theta$
pour $i$ de 1 à $n$ faire
$P^{\prime} \leftarrow$ Insertion-ligne $(P, \sigma(i))$
soit $(u, v)$ tel que $(u, v) \in \operatorname{sh}\left(P^{\prime}\right),(u, v) \notin \operatorname{sh}(P)$, faire
$Q(u, v) \leftarrow i, P \leftarrow P^{\prime}$
retourner $(P, Q)$
On note le résultat retourné en sortie par l'algorithme. En guise d'illustration, on a representé en figure 4 les différentes étapes de l'algorithme pour la permutation .
Fig. 4 - Algorithme de Robinson-Schensted
Question 2.5. Démontrer que l'algorithme de Robinson-Schensted définit une bijection entre et les couples de tableaux de Young de même forme et de taille . En déduire que l'on a
où est le nombre de tableaux de Young de forme .
On admet le résultat suivant (Théorème de Schützenberger) : soit une permutation , on a et .
Question 2.6. Démontrer les égalités
où est le nombre de tableaux de Young de forme et où est la partie entière de .
3 Représentations linéaires du groupe symétrique
L'objectif de cette partie est de donner un très succinct aperçu de la riche théorie liant tableaux de Young et représentations du groupe symétrique.
Soit un -espace vectoriel de dimension . On note le sous-espace vectoriel engendré par . On note le groupe linéaire de , c'est-à-dire l'ensemble des applications linéaires inversibles de dans , muni de la composition comme loi de groupe. Comme d'habitude, on identifie au groupe multiplicatif des matrices carrées d'ordre complexes et inversibles. L'identité de est notée . Une représentation (linéaire) de dimension de est une application où est de dimension et telle que . On remarque que cela implique et .
Question 3.1. Démontrer que , admet exactement deux représentations de dimension 1 que l'on explicitera.
Une représentation est réductible s'il existe un sousespace vectoriel de tel que et stable par pour tout . Dans ce cas, on définit l'application où est la restriction de à . Il est clair que est une représentation de . Une représentation est irréductible si elle n'est pas réductible.
Question 3.2. Soit une représentation et soit un produit scalaire sur . Pour tout , on pose
Montrer que est un produit scalaire sur . Montrer que si est réductible, alors il existe une décomposition en somme directe où les sont des sous-espaces vectoriels stables par , et tels que est irréductible.
On considère le groupe symétrique , et l'application
On vérifie aisément que est une représentation de dimension de , appelée représentation standard.
Question 3.3. Soit . Démontrer que est stable par pour tout et en déduire que est réductible. Montrer que si avec , alors . Montrer que est une représentation irréductible de .
Deux représentations et de dimension de sont isomorphes s'il existe une matrice inversible d'ordre telle que
On admet le difficile et profond résultat suivant : L'ensemble des représentations irréductibles (à isomorphisme près) de peut être paramétré par où est de dimension , le nombre de tableaux de Young de forme .
Question 3.4. Déterminer toutes les représentations irréductibles de (à isomorphisme près). On explicitera les matrices de la représentation de dimension 2 dans une base que l'on choisira.
Pour tout , déterminer explicitement une partition telle que . Déterminer le nombre et la dimension des représentations irréductibles de et de (à isomorphisme près).
ENS Informatique Fondamentale (Maths Info) MP PC 2003 - Version Web LaTeX | WikiPrépa | WikiPrépa
