A versatile combinatorial approach of studying products of long cycles in symmetric groups

摘要

Let S-X denote the symmetric group of permutations on the set X. Studies on triples of permutations satisfying certain conditions have a long history. Particularly interesting cases are when one of the involved permutations is a long cycle, and another involved one is either an involution or also a long cycle. Suppose {B-1, B-2, ... , B-k} is a family of disjoint sets. Here we solve the problem of enumerating the pairs of long cycles on U-i=1(k) B-i whose product is a member of the direct product S-B1 x S-B2 x ... x S-Bk. For those pairs of long cycles the projection of whose product onto S-Bi contains d(i) cycles, we also obtain the first explicit counting formula. @@@ As a consequence, in a unified way, we recover a number of results, including results of Boccara, Walkup, Zagier, Stanley, Feray and Vassilieva, as well as Hultman. We obtain a number of new results as well. In particular, we obtain new explicit formulas concerning factorizations of a permutation into long cycles, and we obtain the first nontrivial explicit formula for computing strong separation probabilities. The latter gives an answer to an open problem of Stanley.

关键词