A generalizationWeightsCycle indicator polynomialsSums of cycle indicators, recursive methods

Sums of cycle indicators, recursive methods

If AX denotes the alternating group on the finite set X then, by Pólya's Theorem, the coefficient of the monomial Py yc(f,y) in C(AX,X | åy) is equal to the number of AX-classes of mappings with the same content as f. If we exclude the trivial case | X | =1, then the AX-class of f differs from its SX-class if and only if its stabilizers (SX)f and (AX)f are equal, and if these classes differ, then the SX-class of f consists of two AX-classes.

The stabilizer of fÎYX in SX is the following direct sum of the symmetric groups on the inverse images of the yÎY:

  (SX)f=Åy SXy, where Xy:=f-1[{y}].
The stabilizer of f in AX is the intersection of (SX)f with AX. As each noninjective f is left fixed by a transposition while each injective f has the identity subgroup as its stabilizer, we obtain
Corollary: The stabilizers of fÎYX in SX and in AX are the same, or, equivalently, they both are equal to the identity subgroup, if and only if f is injective.
Thus the difference of cycle indicators of alternating and symmetric groups has the following useful interpretation (recall figure):
Corollary: For | X | >1 the polynomial
C(AX,X | åy)-C(SX,X | åy)
is the generating function for the enumeration of the injective SX-classes on YX by weight.
Corresponding results hold for cyclic and dihedral groups. Also these arguments can be considered as a certain kind of involution principle. In fact we obtain in the same way the following generalization of the corollary above (recall the corollary on chiral actions):
Corollary: If GX denotes a chiral action, then
C(G+,X | åy)-C(G,X | åy)
is the generating function for the enumeration by weight of the G-classes on YX which split over G+.

Besides these differences of cycle indicator polynomials we can form sums of cycle indicator polynomials of series of groups, e.g. we obtain (by simply comparing coefficients) the equation

  ån=0¥ C(Sn ,n)=expåk=1¥[zk choose k]ÎQ[[z1,z2,...]],
if C(S0,0 | p(u)):=1 and where Q[[z1,z2,...]] denotes the ring of formal power series over Q in the indeterminates z1,z2,.... An immediate consequence is
  ån=0¥ C(Sn,n | p(u))=exp åk=1¥ [1 choose k]p(uk) Î Q[[u]],
This sum is of great interest since it can be used for a recursion method which we are going to describe next.
Example: A graph is called a tree if and only if it is connected and does not contain any cycle. A tree with a single distinguished vertex is called a rooted tree. Figure shows the smallest rooted trees. The root is distinguished by indicating it as a circle while the other vertices are indicated by a bullet.

The smallest rooted trees
 

If r(x) denotes the generating function for the enumeration of rooted trees by their number of vertices, then figure shows that

r(x)=x+x2+2x3+4x4+....
We claim that this formal power series satisfies a recursion formula in terms of cycle indicator polynomials of symmetric groups.
Lemma:   r(x)=xån=0¥ C(Sn ,n | r(x)).
Proof: It is clear that the generating function for the enumeration of rooted trees is equal to the sum over all nÎN of the generating functions of rooted trees with root degree n, i.e. where the root is incident with exactly n edges. It therefore remains to evaluate the generating function for the enumeration of trees with root degree n.

Denote by R the set of all the rooted trees. A rooted tree with root degree n can be considered as an orbit of Sn on the set R n. If we now give an element of R the weight xv, where v denotes the number of vertices of the rooted tree in question, then we obtain the power series xC(Sn ,n | r(x)) which therefore is the desired generating function for the enumeration of rooted trees with root degree n by their number of vertices. This completes the proof.

An application of the above exponential expressions and for the sum of the cycle indicator polynomials of finite symmetric groups as an exponential formal power series allows to rewrite the recursion formula for the generating function of the rooted trees in the following way:

Corollary: The formal power series r(x) which generates the numbers of rooted trees by number of vertices satisfies the recursion formula
r(x)=x·expå1¥ [r(xk) choose k].
This recursion together with a suitable program system, like MAPLE or MACSYMA, allows to evaluate the smallest numbers of rooted trees, some of which are shown in the following table:
nb_nnb_n
11111842
21124766
321312486
441432973
591587811
62016235381
74817634847
8115181721159
9286194688676
107192012826228

Similar arguments apply in each case when the structure in question consists of a certain and well defined number of structures of the same kind. Lower down we shall see how a systematic theory can be developed which covers this and many other cases (there are various approaches, the books are full of them, for example the book of Goulden/Jackson gives an approach that covers very many cases in a different and more elementary way compared to the theory of species which is briefly indicated down below).

Example: Each graph is a disjoint union of connected graphs (a graph is called connected if and only if from each of its vertices we can reach any other vertex by walking along suitably chosen edges). These connected subgraphs are well defined, and they are called the connected components. Thus the generating function g(x)=åvgvxv of the graphs and the generating function c(x)=åv cvxv for the connected graphs are related as follows:
  g(x)=ån=0¥ C(Sn ,n | c(x))=expåk=1¥ [c(xk) choose k].
As we already know that
gv=[1 choose v!]åpÎSv2c(bar (p)),
we can use above exponential formula in order to evaluate the entries of the following table:
vg_vc_v
111
221
342
4116
53421
6156112
71044853
81234611117
9274668261080
101200516811716571
Further examples show up in the sciences. It was already briefly mentioned that the origins of this theory of enumeration lie in chemistry and the problem of isomerism. A few remarks concerning the history are therefore in order. It was already in the 18th century when Alexander von Humboldt conjectured that there might be chemical substances which are composed by the same set of atoms but have differend properties. In his book with the title ''Versuche über die gereizte Muskel- und Nervenfaser, nebst Vermutungen über den chemischen Prozeß in der Tier- und Pflanzenwelt``, published in 1797, he writes (on page 128 of volume I):
Drei Körper a,b und c können aus gleichen Quantitäten Sauerstoff, Wasserstoff, Kohlenstoff, Stickstoff und Metall zusammengesetzt und in ihrer Natur doch unendlich verschieden seyn.
But it needed a quarter of a century to develop the anaytical methods that allowed to find out what the atomic constituents of a chemical molecule are. These methods were developed in particular by J. L. Gay-Lussac and J. von Liebig, who were the first to prove von Humboldt's conjecture to be true. Here is a sentence taken from a paper of Gay-Lussac that describes their discovery:
comme ces deux acides son très différents, il faudrait pour expliquer leur différence admettre entre leurs éléments un mode de combinaison différent. C'est un objet qui appelle un nouveau examen.
It needed some time to realize that a new phenomenon was discovered, J. J. Berzelius gave it the name isomerism. Chemists tried to find out what the reason is by sketching molecules. Here are three of these attempts to draw the molecule of C2H5OH: The first attempt is due to Couper:

The next one is the way how Loschmidt drew this molecule:

The breakthrough towards a solution of this problem is due to Alexander Crum Brown, who used a variation of Loschmidt's method by putting the circles of atoms that are assumed to be connected somehow apart but joining them by edges in order to emphasize the connection. Here are his drawings for the alcohol C3H7OH:

This introduction of molecular graphs solved the problem of isomerism by showing that there may exist different graphs that correspond to a given chemical formula (which prescribes in fact the degree sequence, which is the sequence of valencies of the atoms in the given formula). Moreover it gave rise to the development of graph theory (there are of course also other birthdays of graph theory known, for example Euler's solution of the Königsberg bridge problem, and Kirchhoff's invention of electric circuits as well as Hamiltons game called ''trip around the world``), and it stimulated the combinatorial theory of enumeration since the question of chemical isomerism is at first glance equivalent to the problem of constructing all the graphs which are connected and which have a given edge degree sequence. Let us consider, for example, the chemical formula C3H7OH again, or, more generally the formula CnH2n+1OH. The problem is to construct all the graphs which correspond to each of these formulae, i.e. all the graphs that consist of n vertices of degree 4 (the carbon atoms are of that valency) together with 2n+2 vertices of degree 1 (the hydrogen) and one of degree 2 (the oxygen) which must have a neighbour of degree 1 (so that a hydroxyl group -OH occurs). This problem amounts to the construction of rooted trees, as, by a well-known result of graph theory, such degree sequences can be satisfied by trees only (the cyclomatic number is zero in this case). The root represents the substructure ºC-O-H, so that the root degree is <= 3. Consider the two examples shown above which correspond to the formula C3H7OH. As the carbon atoms are of valency 4, we can make life easier by neglecting the hydrogen atoms, so that the skeletons remain, which correspond to the rooted trees with 3 vertices. From each one of these structures we can reconstruct the original molecular graph and hence the desired generating function a(x) for the numbers of alcohols satisfies the recursion

  a(x)=xån=03C(Sn ,n | a(x)).
harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

A generalizationWeightsCycle indicator polynomialsSums of cycle indicators, recursive methods