Now we refine our methods in order to enumerate orbits with prescribed properties. We introduce a weight function on GX, i.e. a mapping from X into a commutative ring which is constant on the orbits of G on X, and the Cauchy-Frobenius Lemma will be refined in order to count orbits with prescribed weight. For example we shall be able to enumerate graphs by their number of edges. This leads us to certain generating functions, the so-called cycle indicator polynomials. The enumeration of rooted trees amounts to the consideration of sums of cycle indicator polynomials and leads to recursive methods. These recursions can be used even for constructive methods, and they stimulate the formalization of the calculation of generating functions. Afterwards we generalize the enumeration of symmetry classes by introducing a combinatorial situation which covers both the notion of symmetry class (which was in fact Pólya's approach to the enumeration of graphs) and the situation which J.H. Redfield studied in order to enumerate superpositions of graphs.

Finally we shall discuss a categorical approach to the evaluation of generating functions, the theory of species. It yields one of the various systematic approaches to decompositions of structures (like decomposing permutations into cycles, graphs into connected components, and so on).

  • Enumeration by weight
  • Cycle indicator polynomials
  • Sums of cycle indicators, recursive methods
  • A generalization
  • The Decomposition Theorem
  • Species

    last changed: August 28, 2001