ALGÈBRE. — Un résultat extrémal en théorie des permutations.
Jacques, Alain ; Lenormand, Claude ; Lentin, André ; Perrot, Jean-François
HAL, hal-01573916 / Harvested from HAL
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)
Publié le : 1968-02-19
Classification:  [MATH]Mathematics [math]
@article{hal-01573916,
     author = {Jacques, Alain and Lenormand, Claude and Lentin, Andr\'e and Perrot, Jean-Fran\c cois},
     title = {ALG\`EBRE. --- Un r\'esultat extr\'emal en th\'eorie des permutations. },
     journal = {HAL},
     volume = {1968},
     number = {0},
     year = {1968},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/hal-01573916}
}
Jacques, Alain; Lenormand, Claude; Lentin, André; Perrot, Jean-François. ALGÈBRE. — Un résultat extrémal en théorie des permutations. . HAL, Tome 1968 (1968) no. 0, . http://gdmltest.u-ga.fr/item/hal-01573916/