.
Example
We would like to derive from 
a formula for the number of
graphs on 
vertices. Before we start doing so it should be mentioned
that this example is the second typical example which we present.
The first
examples
were devoted to the
introduction of group theoretical concepts,
to
the derivation of Sylow's Theorem
and to a
number theoretic result of Fermat.
The only example where a suitable choice of 
and 
was made in order to define and enumerate a mathematical structure
was in fact
the composition of two symmetric groups.
As this example
may have been a little bit artificial we admit that it is
only now that we start to apply our paradigmatic actions more systematically.
Let us see how suitably chosen 
, 
and can be used in order to define
and enumerate the graphs on vertices.(Later on we shall refine this method
by counting these graphs according to the number of edges or according
to their automorphism group. Finally we shall even use this Ansatz
in order to construct such graphs and also to generate them
uniformly at random.) The way of defining
graphs as orbits of groups may at first glance seem to be circumstantial,
but we shall see that this definition is very flexible since it can easily be
generalized to all other kinds of graphs like multigraphs, directed graphs
and so on.
vertices can be considered (after numbering the
vertices from 1 to , say) as a map 
from the set
of
(unordered) pairs of vertices into the set 
, where
we put
For example, the first one of the two labelled graphs of figure
can be identified in this way with the mapping 
defined by
acts
on 
and hence also on
, so that we obtain an action
of on 
which is of the form 
as
was described in . Two labelled graphs are called
isomorphic
if and only if
they lie in the same orbit under this action, i.e. if and only if
each arises
from the other by renumbering the vertices, so that for example the
labelled graphs of figure are isomorphic (apply
.
Figure: Two isomorphic labelled graphs with 4 vertices
on
vertices is defined to be such an isomorphism
class of labelled graphs. It can be visualized by taking any member of the
isomorphism class and deleting the labels.This yields for the
labelled graphs shown in figure the
drawings of figure .
Figure: The graphs obtained from the labelled ones above
It should be clear by now what we
mean by a graph, and that in our terminology a graph is
not a pair 
consisting of a set 
of vertices and a set 
of
edges, but that a graph can be represented by such a pair,
so that, for example, the graphs of figure are in fact equal.
, then
we again consider 
, but we change into
The elements of
are called labelled -graphs
, while by -graphs
on vertices
we mean the orbits of on this set.
by the
union 
, and now 
,
for 
, means that
the vertex with the number 
carries a 
-fold loop.
the set of injective pairs over 
.
Thus graphs, -graphs, -graphs with loops
and also digraphs can be
considered as symmetry classes of mappings. Several other structures
will later on be obtained in the same way. Having defined the graphs
this way we want to count them by an application of which
means that we have to derive a formula for 
, the number of
cyclic factors of 
, the permutation induced by 
on the set of pairs of points,
expressed in terms of the
cycle structure of 
. In fact we can do better, we can derive the
cycle type of from the cycle type of .