Sums of cycle indicators, recursive methods |

The stabilizer of *fÎY ^{X}* in

The stabilizer of(S_{X})_{f}=Å_{y}S_{Xy}, where X_{y}:=f^{-1}[{y}].

Thus the difference of cycle indicators of alternating and symmetric groups has the following useful interpretation (recall figure):Corollary:The stabilizers offÎYin^{X}Sand in_{X}Aare the same, or, equivalently, they both are equal to the identity subgroup, if and only if_{X}fis injective.

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:For| X | >1the polynomialis the generating function for the enumeration of the injectiveC(A_{X},X | åy)-C(S_{X},X | åy)S-classes on_{X}Yby weight.^{X}

Corollary:Ifdenotes a chiral action, then_{G}Xis the generating function for the enumeration by weight of theC(G^{+},X | åy)-C(G,X | åy)G-classes onYwhich split over^{X}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

ifå_{n=0}^{¥}C(S_{n},n)=expå_{k=1}^{¥}[z_{k}choose k]ÎQ[[z_{1},z_{2},...]],

This sum is of great interest since it can be used for a recursion method which we are going to describe next.å_{n=0}^{¥}C(S_{n},n| p(u))=exp å_{k=1}^{¥}[1 choose k]p(u^{k}) ÎQ[[u]],

Example:A graph is called atreeif and only if it is connected and does not contain any cycle. A tree with a single distinguished vertex is called arootedtree. 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 treesIf

r(x)denotes the generating function for the enumeration of rooted trees by their number of vertices, then figure shows thatWe claim that this formal power series satisfies a recursion formula in terms of cycle indicator polynomials of symmetric groups.r(x)=x+x^{2}+2x^{3}+4x^{4}+....Proof: It is clear that the generating function for the enumeration of rooted trees is equal to the sum over allLemma:r(x)=xå._{n=0}^{¥}C(S_{n},n| r(x))nÎof the generating functions of rooted trees with root degreeNn, i.e. where the root is incident with exactlynedges. It therefore remains to evaluate the generating function for the enumeration of trees with root degreen.Denote by

Rthe set of all the rooted trees. A rooted tree with root degreencan be considered as an orbit ofSon the set_{n}R. If we now give an element of^{n}Rthe weightx, where^{v}vdenotes the number of vertices of the rooted tree in question, then we obtain the power seriesxC(Swhich therefore is the desired generating function for the enumeration of rooted trees with root degree_{n},n| r(x))nby 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:

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:Corollary:The formal power seriesr(x)which generates the numbers of rooted trees by number of vertices satisfies the recursion formular(x)=x·expå_{1}^{¥}[r(x^{k}) choose k].

n b_n n b_n 1 1 11 1842 2 1 12 4766 3 2 13 12486 4 4 14 32973 5 9 15 87811 6 20 16 235381 7 48 17 634847 8 115 18 1721159 9 286 19 4688676 10 719 20 12826228

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).

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):Example:Each graph is a disjoint union ofconnectedgraphs (a graph is calledconnectedif 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 theconnected components. Thus the generating functiong(x)=åof the graphs and the generating function_{v}g_{v}x^{v}c(x)=åfor the connected graphs are related as follows:_{v}c_{v}x^{v}As we already know thatg(x)=å_{n=0}^{¥}C(S_{n},n| c(x))=expå_{k=1}^{¥}[c(x^{k}) choose k].we can use above exponential formula in order to evaluate the entries of the following table:g_{v}=[1 choose v!]å_{pÎSv}2^{c(bar (p))},

v g_v c_v 1 1 1 2 2 1 3 4 2 4 11 6 5 34 21 6 156 112 7 1044 853 8 12346 11117 9 274668 261080 10 12005168 11716571

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 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 *C _{3}H_{7}OH*:

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
*C _{3}H_{7}OH* again, or, more generally the formula

a(x)=xå_{n=0}^{3}C(S_{n},n| a(x)).

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Sums of cycle indicators, recursive methods |