Reductive Enumeration Under Mutually Orthogonal Group Actions

摘要

The paper deals with orbit enumeration within the framework of Burnside's Lemma in a special situation when the group possesses two 'mutually orthogonal' action with respect to fixed points of its elements. Due to this property, only regular permutations should be taken into account in the enumeration. This considerably facilitates counting combinatorial objects up to isomorphism and obtaining simple closed formulae. Two general approaches reducing the counting of nonisomorphic (unrooted) objects to "rooted' and 'cycle-rooted' (and then quotient) objects, respectively, are developed and described. We give here a general description and a survey of methods and results arisen. The idea turns out to be applicable to numerous concrete problems. Most of them can be modelled by tuples of permutations that generate transitive groups and are considered up to conjugacy. Enumerative results are given for counting subgroups of free groups, strong automata, coverings of surfaces, planar maps and plane point configurations. In conclusion, some open questions are posed.