Weights
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).
last changed: January 19, 2005
