Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Maths sup AlgèbreTopics traitant de algèbre [tout]Lister tous les topics de mathématiques
Niveau Maths sup
Partager :

Mots réduits d'une permutation

Posté par austinpower (invité) 24-02-07 à 00:37

Bonjour,
pourriez-vous m'aider pour cet exo.
Merci

On appelle mot de la permutation \mu  toute suite ( \i_1,\i_2,...,\i_k) telle que :
\mu = \tau{i_1}\tau{i_2}...\tau{i_k}
Un mot est dit réduit s'il est de longueur minimale. On appelle longueur d'une permutation \sigma et l'on note l(\sigma)  la longueur d'un mot réduit.
1. Donner un algorithme qui calcule un mot réduit de \sigma. Ecrire la fonction correspondante
2. En déduire que la longueur d'une permutation est inférieure au nombre d'inversions.
3. Montrer qu'il y a en fait égalité.
4. Donner un algorithme qui calcule tous les mots réduits d'une permutation \sigma
5. Montrer que la fonction génératrice des permutations comptées par longueur est \sum_{\sigma\in\mathfrak{S}_n}t^{l(\sigma)} = (1+t)(1+t+t^2)(1+t+t^2+t^3)...(1+t+t^2+...+t^{n-1})

Posté par
Cauchyre : Mots réduits d'une permutation 24-02-07 à 00:41

Salut,

je comprend pas bien ce que tu as écrit dans ta parenthese?

(1,2,...k)?

En gros tu décomposes ta permutation en transpositions c'est bien ca?

Posté par austinpower (invité)re : Mots réduits d'une permutation 24-02-07 à 09:48

Ca c'est mal affiché mais dans la parenthese, c'est en faite (i1,i2,..., ik)

Posté par
Cauchyre : Mots réduits d'une permutation 24-02-07 à 13:33

Que représente:

3$\tau_{i_1}?

Posté par austinpower (invité)re : Mots réduits d'une permutation 24-02-07 à 15:48

\tau signifie transposition élémentaire

Posté par
Cauchyre : Mots réduits d'une permutation 24-02-07 à 16:17

T_i1 échange quels éléments?


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1675 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !