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 n ∈ ℕ^∗, soit 𝔖_n le groupe symétrique de degré n, c'est-à-dire l'ensemble des permutations de {1, 2, …, n} muni de la composition comme loi de groupe. L'élément neutre de 𝔖_n est noté e. La composition des permutations est notée multiplicativement, on écrit donc σσ^′ pour σ ∘ σ^′ ou σ^(− 1) pour l'inverse de σ. Le support de la permutation σ est {i|σ(i) ≠ i}. La transposition (i, j), i ≠ j, est la permutation de support {i, j}. Le cycle c_(ij), i < j, est la permutation de support {i, i + 1, …, j} telle que σ(k) = k + 1 pour k = i, …, j − 1, et σ(j) = i. On pose c_(ji) = c_(ij)^(− 1), i < j. On représente une permutation σ ∈ 𝔖_n à l'aide du mot σ(1), σ(2), …, σ(n).
1 Cartes, mélange et réussite
Soit un ensemble de n cartes, chacune d'entre elles étant numérotée par un entier différent entre 1 et n. 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 𝔖_n où σ(i) est le numéro de la carte en i-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 e.
Soit l'ensemble de permutations U = {c_(ij)|i, j ∈ {1, 2, …, n}, i ≠ j}. On rappelle que les éléments de U engendrent 𝔖_n. On définit U : 𝔖_n ⟶ ℕ de la façon suivante :
On remarque que σc_(ij) est la pile de cartes obtenue à partir de la pile σ en déplaçant la carte en position i jusqu'à la position j. Ainsi U(σ) est une évaluation du mélange de la pile σ.
Question 1.2. Soit i, j ∈ {1, 2, …, n} avec i ≠ j. Déterminer U((i, j)).
Étant donné une permutation σ, une sous-suite croissante de σ est une suite d'indices (i_1, …, i_k) tels que i_1 < i_2 < ⋯ < i_k, σ(i_1) < σ(i_2) < ⋯ < σ(i_k). Une sous-suite décroissante est une suite d'indices ( i_1, …, i_k ) tels que i_1 < i_2 < ⋯ < i_k, σ(i_1) > σ(i_2) > ⋯ > σ(i_k). La longueur de la sous-suite est le nombre d'indices. On note L(σ) le maximum des longueurs des sous-suites croissantes de σ.
Question 1.3. Soit σ ∈ 𝔖_n. Démontrer l'égalité U(σ) + L(σ) = n. (On pourra commencer par montrer que |L(σc_(ij)) − L(σ)| ⩽ 1.)
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 n 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 7, 2, 3, 6, 1, 5, 4. 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 à L(σ). (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 𝔖_n et retournant en sortie une sous-suite croissante de longueur maximale de σ.
L'ensemble K = {(i, i + 1)|i ∈ {1, 2, …, n − 1}} engendre 𝔖_n. On définit K : 𝔖_n ⟶ ℕ par
On voit que K(σ) correspond à une autre évaluation du mélange de σ.
Question 1.6. Le nombre d'inversions d'une permutation σ est par définition Inv(σ) = Card{(i, j)|i < j, σ(i) > σ(j)}. Montrer que K(σ) = Inv(σ).
Question 1.7. Démontrer avec soin que l'algorithme ci-dessous permet de calculer K(σ).
$\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 (k, k + 1)⋯(i − 1, i) = c_(ki). Il est alors naturel de modifier l'algorithme en remplaçant la ligne 5 par
5^′. σ ← σc_(ki), inv ← inv + 1.
Le nouvel algorithme retourne-t-il en sortie U(σ) ?
2 Tableaux de Young
L'objet de cette partie est d'étudier de façon plus fine la combinatoire de U(σ) et de L(σ) à l'aide des tableaux de Young.
Une partition de n ∈ ℕ^∗ est une suite d'entiers λ = (λ_1, λ_2, …, λ_k) vérifiant λ_1 ⩾ λ_2 ⩾ ⋯ ⩾ λ_k ⩾ 1 et ∑_i λ_i = n. On utilise la notation λ⊢n pour indiquer que λ est une partition de n.
Question 2.1. Écrire un algorithme récursif prenant en entrée n ∈ ℕ^∗ et retournant en sortie le nombre de partitions de n.
Le diagramme de Ferrers de λ = (λ_1, λ_2, …, λ_k)⊢n est une collection de n cases arrangées en k lignes alignées par la gauche, la i-ième ligne en partant du bas contenant λ_i cases. Il est souvent utile d'identifier le diagramme de Ferrers avec le sous-ensemble de (ℕ^∗)^2 correspondant aux positions des
Tournez la page S.V.P.
cases, i.e. avec {(j_i, i), 1 ⩽ i ⩽ k, 1 ⩽ j_i ⩽ λ_i}. La taille du diagramme de Ferrers est le nombre de cases. À titre d'exemple, le diagramme de Ferrers de (3, 2, 1, 1)⊢7 est représenté sur la gauche de la figure 2.
Un tableau de Young partiel de taille n ∈ ℕ^∗ est un diagramme de Ferrers de taille n 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 n ∈ ℕ^∗ est un tableau de Young partiel de taille n dans lequel, de plus, les cases sont numérotées par les entiers de 1 à n. 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 T, notée sh(T), est le diagramme de Ferrers obtenu en oubliant les numéros (ou encore la partition correspondante).
Étant donné un tableau partiel T, l'ensemble des entiers apparaissant dans les cases de T est noté num (T). On identifie T avec l'application T : ℕ^∗ × ℕ^∗ ⟶ num(T) ∪ {0} définie par T(j, i) = k si (j, i) ∈ sh(T) et si k est l'entier apparaissant dans la case ( j, i ), et par T(j, i) = 0si(j, i) ∉ sh(T). On note T(j,.), respectivementT(., i), le tableau partiel formé de la j-ième colonne, respectivement i-ième ligne, de T.
On appelle tableau vide l'application Θ définie par ∀i, j ∈ ℕ^∗, Θ(i, j) = 0. La taille de Θ est 0 et on pose sh(Θ) = ∅ et num(Θ) = ∅. Si T est un tableau partiel tel que sh(T) contient i lignes et j colonnes, alors par convention T(⋅, u) = T(v, ⋅) = Θ pour u > i et v > j.
On définit une procédure qui prend en entrée ( T, x ) où T est soit un tableau partiel soit le tableau vide, et où x ∈ ℕ^∗, x ∉ num(T). L'algorithme fonctionne avec la convention : max{k|k ∈ ∅} = 0. On note l_x(T) le résultat retourné en sortie par l'algorithme.
Insertion-ligne ( T, x )
$\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 l_x(T) est un tableau partiel qui contient une case de plus que le tableau d'entrée T et tel que num(l_x(T)) = num(T) ∪ {x}. 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é σ ∈ 𝔖_n, on note P(σ) le tableau de Young obtenu en sortie de l'algorithme suivant:
P ← Θ, pour i de 1 à n faire P ← InSERTION-LIGNE (P, σ(i)).
Montrer que la ligne du bas de P(σ) est constituée de L(σ) 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 ⋆ = ⋅, j, j + 1. On note c_x(T) le tableau partiel obtenu par l'insertion en colonne dans T de l'entier x ∈ ℕ^∗, x ∉ num(T). On admet le résultat de commutation suivant (la preuve est élémentaire mais peu instructive) : soit T un tableau partiel et soit x, y ∈ ℕ^∗, x, y ∉ num(T), x ≠ y, on a
c_y ∘ l_x(T) = l_x ∘ c_y(T)
Étant donné un tableau partiel T, on définit le tableau partiel transposé T^t par: ∀i, j ∈ ℕ^∗, T^t(i, j) = T(j, i). Étant donné une permutation σ = σ(1), σ(2), ⋯, σ(n), la permutation miroir est définie par σ¯ = σ(n), ⋯, σ(2), σ(1).
Tournez la page S.V.P.
Question 2.3. Soit σ une permutation. Montrer que l'on a P(σ¯) = P(σ)^t. 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 P(σ).
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 min{U(σ), U(σ¯)}.
Question 2.4. Soit σ ∈ 𝔖_(n^2). Montrer que min{U(σ), U(σ¯)} ⩽ n(n − 1). Donner explicitement une permutation σ ∈ 𝔖_(n^2) telle que U(σ) = U(σ¯) = n(n − 1).
On présente maintenant l'algorithme dit de Robinson-Schensted. RS(n, σ ∈ 𝔖_n)
$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 (P(σ), Q(σ)) 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 7, 2, 3, 6, 1, 5, 4.
Fig. 4 - Algorithme de Robinson-Schensted
Question 2.5. Démontrer que l'algorithme de Robinson-Schensted définit une bijection entre 𝔖_n et les couples de tableaux de Young de même forme et de taille n. En déduire que l'on a
où d_λ est le nombre de tableaux de Young de forme λ et où [n/2] est la partie entière de n/2.
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 E un ℂ-espace vectoriel de dimension dim(E) = k ∈ ℕ^∗. On note ℂu le sous-espace vectoriel engendré par u ∈ E. On note GL(E) le groupe linéaire de E, c'est-à-dire l'ensemble des applications linéaires inversibles de E dans E, muni de la composition comme loi de groupe. Comme d'habitude, on identifie GL(E) au groupe multiplicatif des matrices carrées d'ordre k complexes et inversibles. L'identité de GL(E) est notée I. Une représentation (linéaire) de dimension k ∈ ℕ^∗ de 𝔖_n est une application Ψ : 𝔖_n ⟶ GL(E) où E est de dimension k et telle que ∀σ, τ ∈ 𝔖_n, Ψ(στ) = Ψ(σ)Ψ(τ). On remarque que cela implique Ψ(e) = I et ∀σ ∈ 𝔖_n, Ψ(σ^(− 1)) = Ψ(σ)^(− 1).
Question 3.1. Démontrer que 𝔖_n, n ⩾ 2, admet exactement deux représentations de dimension 1 que l'on explicitera.
Une représentation Ψ : 𝔖_n ⟶ GL(E) est réductible s'il existe un sousespace vectoriel F de E tel que 0 < dim(F) < dim(E) et stable par Ψ(σ) pour tout σ ∈ 𝔖_n. Dans ce cas, on définit l'application Ψ_F : 𝔖_n ⟶ GL(F) où Ψ_F(σ) est la restriction de Ψ(σ) à F. Il est clair que Ψ_F est une représentation de 𝔖_n. Une représentation est irréductible si elle n'est pas réductible.
Question 3.2. Soit une représentation Ψ : 𝔖_n ⟶ GL(E) et soit (⋅ | ⋅) un produit scalaire sur E. Pour tout u, v ∈ E, on pose
⟨u|v⟩ = ∑_(σ ∈ 𝔖_n)(Ψ(σ)u|Ψ(σ)v)
Montrer que ⟨ ⋅ | ⋅ ⟩ est un produit scalaire sur E. Montrer que si Ψ est réductible, alors il existe une décomposition en somme directe E = ⨁_i E_i où les E_i sont des sous-espaces vectoriels stables par Ψ(σ), σ ∈ 𝔖_n, et tels que Ψ_(E_i) est irréductible.
On considère le groupe symétrique 𝔖_n, n ⩾ 2, et l'application
S : 𝔖_n, ⟶ GL(ℂ^n); σ, ⟼ S(σ) = (S(σ)_(ij)) avec S(σ)_(ij) = {1, si i = σ(j); 0, sinon
On vérifie aisément que S est une représentation de dimension n de 𝔖_n, appelée représentation standard.
Question 3.3. Soit H = {(x_1, …, x_n) ∈ ℂ^n|x_1 + ⋯ + x_n = 0}. Démontrer que H est stable par S(σ) pour tout σ ∈ 𝔖_n et en déduire que S est réductible. Montrer que si x = (x_1, …, x_n) ∈ H avec ∀i ≠ j, x_i ≠ x_j, alors ∑_σ ℂS(σ)x = H. Montrer que S_H est une représentation irréductible de 𝔖_n.
Deux représentations Ψ_1 et Ψ_2 de dimension k de 𝔖_n sont isomorphes s'il existe une matrice inversible P d'ordre k telle que
∀σ ∈ 𝔖_n, Ψ_1(σ) = P^(− 1)Ψ_2(σ)P
On admet le difficile et profond résultat suivant : L'ensemble 𝔈 des représentations irréductibles (à isomorphisme près) de 𝔖_n peut être paramétré par 𝔈 = {Ψ_λ, λ⊢n} où Ψ_λ est de dimension d_λ, le nombre de tableaux de Young de forme λ.
Question 3.4. Déterminer toutes les représentations irréductibles de 𝔖_3 (à isomorphisme près). On explicitera les matrices de la représentation de dimension 2 dans une base que l'on choisira.
Pour tout n ⩾ 2, déterminer explicitement une partition λ⊢n telle que d_λ = n − 1. Déterminer le nombre et la dimension des représentations irréductibles de 𝔖_4 et de 𝔖_5 (à isomorphisme près).
Pas de description pour le moment
Commentaires• ENS Informatique Fondamentale (Maths Info) MP PC 2003
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
