THE COMBINATORIAL RELATIONSHIP BETWEEN TREES, CACTI AND CERTAIN CONNECTION COEFFICIENTS FOR THE SYMMETRICAL GROUP

A combinatorial bijection is given between pairs of permutations in Sn the product of which is a given n-cycle and two-coloured plane edge-rooted trees on n edges, when the numbers of cycles in the disjoint cycle representations of the permutations sum to n + 1. Thus the corresponding connection coefficient for the symmetric group is determined by enumerating these trees with respect to appropriate characteristics. This is extended to the case of m-tuples of permutations in Sn the product of which is a given n-cycle, in which the combinatorial objects replacing trees are cacti of m-gons. © 1992 Academic Press Limited.