0 avis
ALGÈBRE. — Un résultat extrémal en théorie des permutations.
Archive ouverte
Edité par HAL CCSD
Note (*) C.R. Acad. Sc. Paris 1968. International audience. On calcule un Max-min et un min-Max sur l'ensemble des décompositions d'une permutation donnée en un produit de deux permutations. Soit Sn une permutation de n objets ('); désignons par z() le nombre des cycles disjoints de a, y compris les cycles de longueur i. Le but de cette Note est d'établir le THÉORÈME 1 (i) Max{min{z(), z()}; , Sn, = } = [(n + z())/2], où [a/e] note la partie entière de a/b; (ii) min{Max{z(), z()}; t, Sn; = } = I ou 2 selon que est paire ou impaire. L'énoncé (i) se rencontre naturellement dans la théorie des équations dans les monoïdes libres. (ii) se déduit du résultat suivant, qui précise le théorème 1 de Ore (') THÉORÈME 2. Toute permutation paire de n objets est le commutateur d'un cycle de longueur n et d'une involution. Les démonstrations font appel aux propriétés suivantes A. DÉFINITION. Une décomposition = (, , Sn) sera dite normale si elle satisfait les trois conditions (a) a et sont des involutions, i. e. a2 = 2 = i (b) (c) si k = z() et y,, 2, Yk sont les cycles de a, alors a = 1 2 k et = 12 k avec pour r = I, 2, k, r = rr décomposition normale de Yr. En particulier, i = i entraîne a = pi = i. PROPOSITION 1. Tout cycle Sn de longueur n admet exactement n décompositions normales Y = .Sin est impair, a et ont toujours chacune un seuL point fixe. Si n est pair, dans la moitié des cas a a deux points fixes et n'en a aucun, dans les autres cas c'est l'inverse qui se produit. En effet, si Y = a(3 est une décomposition normale, on déduit de (a)
Consulter en ligne
Suggestions
Du même auteur
