\input lmacros
\newcommand{\Orbit}{{\rm Orbit}}
\newcommand{\Stab}{{\rm Stab}}
\newcommand{\compose}{\circ}
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

\begin{center}
{\bf Notes:  Permutation groups and Polya theory.}
\end{center}

\bigskip

\noindent 1.  Counting problems involving symmetry.

\medskip

These notes deal with a method of combining ordinary generating
functions with a little bit of group theory to solve certain kinds of
counting problems ``up to symmetry.''  Let us introduce some examples
to make clear what is meant.

Example: suppose we wish to color the faces of a cube with two
colors, red and blue.  If the cube is held in a fixed position, we
have two choices for each face, and these can be made independently
for a total of 64 ways of choosing.  If however the cube is allowed to
rotate, then some of these choices are essentially the same as others.
For instance, one possibility is to color the top face red and all
others blue.  Another is to color the front face red and all others
blue.  But these are the same in that we could change one to other by
merely rotating the cube.  Therefore we do not wish to count them
separately.  Accordingly, there will be far less than 64 ways of
choosing the colors, up to rotational symmetry.

In a variation of this problem, we might wish not only to count all
the ways to color the cube, but to keep track of how may ways have $k$
red faces, for each $k$ from $0$ to $6$.  For this we should use an
ordinary generating function, in which a way of coloring counts with
weight $x^{k}$ if it has $k$ red faces.  The choice to be made at an
individual face is red (weight $x^{1} = x$) or blue (weight $x^{0} =
1$) for a total of $(1+x)$.  If the position of the cube is held
fixed, we may make our choices independently, getting $(1+x)^{6} = 1 +
6x + 15x^{2}+\cdots $ for the total.

  If we count colorings up to symmetry, however, we will get a
different answer.  There will still be one way to color with no red
faces, but now all six ways to have just one red face are the same and
count as one.  The fifteen ways to have two red faces only come in two
kinds: red faces adjacent, or opposite.  So the ordinary generating function
for ways of coloring, up to rotational symmetry, should look like
$1+x+2x^{2}+\cdots $.

Another example: we  wish to string 15 black and white beads into
a necklace.  If we think of the necklace as having 15 fixed spaces, we
can decide independently for each space whether to put a black bead
there or a white one.  In the actual necklace, however, there are only
15 spaces arranged in a circle with no special starting point or
direction.  Another way to say this is that if we choose beads for our
15 fixed positions, then rotate or reverse the pattern, whatever
pattern we get should be considered the same as the one we started
with.

What both examples have in common is that there is a set $X$ of
locations---the cube faces, the necklace positions---and a choice to
be made at each location.  The choices can be made independently from
a set $A$ (red and blue, or black and white) whose generating function
$F(x)$ is known.  If there were no symmetry, the generating function
for all ways of choosing would then be $F(x)^{n}$, where $n = |X|$ is
the number of locations.  In the examples, though, there are certain
symmetries (rotations of the cube, rotations and reversals of the
necklace), each of which permutes the set $X$ of locations and thereby
makes some ways of choosing equivalent to others.  The problem is to
find a generating function that counts each equivalence class only once.

\newpage

\noindent 2.  Permutation groups.

\medskip

We will now give a definition that makes mathematically precise the
informal notion of symmetries permuting a set of locations $X$.

Let $X$ be a set.  Recall that a {\it permutation} of $X$ is a
bijective function $\pi \colon X\rightarrow X$.  There are two
operations we can do on permutations.  First, given permutations $\pi
$ and $\sigma $ we can compose them as functions to get a permutation
$\pi \sigma $ defined by $\pi \sigma (x) = \pi (\sigma (x))$.  Second,
given a permutation $\pi $ we can take its inverse function $\pi
^{-1}$, since $\pi $ is a bijection by definition.

We use ${\bf 1}$ to denote the {\it identity} permutation defined by
${\bf 1}(x) = x$.  Evidently if $\pi $ is any permutation we have $\pi
{\bf 1} = {\bf 1}\pi  = \pi $ and $\pi \pi ^{-1} = \pi ^{-1}\pi = {\bf
1}$.  Thus our notation is at least consistent with arithmetic
notation, though we must be careful not to commute things: $\pi \sigma
$ and $\sigma \pi $ do not have to be the same.

A {\it permutation group} $G$ on the set $X$ means a collection of
permutations which form a closed system under the composition and
inverse operations and contains the identity element.  
More formally we require that:

(1) ${\bf 1}\in G$,

(2) $\pi \sigma \in G$ for all $\pi \in G$ and $\sigma \in G$,

(3) $\pi ^{-1}\in G$ for all $\pi \in G$.

In practice the way we get permutation groups is that $X$ consists of
parts of a geometric figure or other mathematical entity permuted by
symmetries.  For instance $X$ may be the faces of a cube, or its
vertices, or its edges, and we consider how rotations permute $X$.  Or
$X$ may be the bead positions of a necklace, that is, points arranged
in a circle, and we consider how symmetries permute those points.
In another type of example, $X$ might be the nodes of an unordered tree and we
could consider all symmetries of the tree.

In these situations, we seldom have to check conditions (1), (2), and
(3) for a permutation group explicitly.  We just have to make sure we
do not omit any symmetries.  For the identity is always a valid
symmetry (and we must always be sure to count it when using the Polya--Burnside
theorem, discussed below), giving condition (1).  Furthermore if we
transform by one symmetry and then another, the net result is a
symmetry.  For instance we can rotate a cube first one way and then
another and the combined effect is itself a rotation.  This gives
condition (2).  Finally, given any symmetry we can reverse it and that
gives the inverse.  For instance we can reverse any cube rotation by
rotating the same amount in the opposite direction.  This gives
condition (3).

Example:  the group $C_{5}$ of rotations of a pentagon in the plane,
\vspace{1.4in}
permuting the vertices.  
Label the vertices as shown,
and we get five rotations: identity $ = {\bf 1}$, rotation by $2\pi /5$
= (1 2 3 4 5), rotation by $4\pi /5$ = (1 3 5 2 4), rotation by $6\pi
/5$ = (1 4 2 5 3), rotation by $8\pi /5$ = (1 5 4 3 2).

Example:  the group $D_{5}$ of rotations and reflections of a
pentagon, permuting the vertices.  Now we are thinking of the pentagon
as a figure in 3-space so we can pick it up and put it down backwards.
In addition to the five rotations in $C_{5}$ we get five reflections.
For instance, reflecting about a vertical axis gives (2 5)(3 4).  The
whole group contains 10 permutations: $D_{5} = \{${\bf 1}, (1 2 3 4
5), (1 3 5 2 4), (1 4 2 5 3), (1 5 4 3 2), (2 5)(3 4), (1 3)(4 5), 
(1 5)(2 4), (1 2)(3 5), (1 4)(2 3)$ \}$.  This example would be the
appropriate group for the necklace problem, if there were only five beads.

Example: the group $H$ of rotations of the cube, acting on the six
faces.  Label them like this:

\vspace{1in}

\noindent
(Here labels appear at the centers of the associated faces; faces 1,3,4
are visible and faces 2,5,6 are hidden.)
There are 24 rotations.  We won't list them all here but just consider
some typical ones.  For instance there is a rotation by $\pi /2$ about
a vertical axis through the centers of faces 1 and 6, given by (2 3 4
5).  Or there is the rotation by $\pi $ about this same axis, which
gives (2 4)(3 5).  Another possible axis of rotation goes through two
opposite vertices, say the vertex on top at left rear and the vertex
on the bottom at right front.  A rotation of $2\pi /3$ about this axis
would be (1 5 2)(3 4 6).

Once they are written down, we can use these permutations to compute
with rotations.  For instance if we do the rotation (2 3 4 5) above,
followed by (1 5 2)(3 4 6), we get the composition (1 5 2)(3 4 6)(2 3
4 5) = (1 5)(2 4)(3 6).  On inspection we find this last permutation
to represent a rotation
of $\pi $ about an axis through the centers of the edge at top back
and the edge at bottom front.  You will probably find that this computation
of composition of rotations with symbols is quite a bit easier than
trying to do it by pure geometric intuition!

If the group $G$ acts on a set $X$, it also has a natural way of acting
on the set of maps from $X$ to $Z$, where $A$ is some set of colors.
Consider, for example, the case where $X$ is the set of faces of a cube,
numbered 1 through 6 as above, and $A = \{\mbox{red, blue}\}$.  Let $g$
be the permutation $(2 3 4 5)$, and let $c: X \rightarrow A$ be the
coloring that assigns to face 2 the color red and to all other faces
the color blue.  Then we can define $c' = g(c)$ as the coloring that
assigns to face 3 the color red and to all other faces the color blue.
More generally, if $c$ gives color $a$ to face $x$, then $c'$ gives
color $a$ to face $g(x)$.  Hence the function $c'$ is the composition
$c \compose g^{-1}$ (check this: $c'(g(x)) = (c \compose g^{-1})(g(x)) 
= c(g^{-1}(g(x))) = c(x) = a$).  In general, we define $g(c)$ (``$g$
acting on $c$'') as $c \compose g^{-1}$.

\bigskip

\noindent 3.  Cycle indicators.

\medskip

Associated with a permutation group $G$ is a polynomial $C_{G}$ called its
{\it cycle indicator} which contains all the information necessary to
solve symmetric choice counting problems of the kind discussed in
section 1.  It's a polynomial in several variables
$C_{G}(t_{1},t_{2},\ldots)$ and is a kind of
generating function counting the permutations in $G$ according to how
many cycles of various sizes they have.

Given a permutation $\pi $, let $k_{1}$ be the number of 1-cycles (=
fixed points) in
$\pi $, $k_{2}$ the number of 2-cycles, and so on.  Then we define the
cycle indicator of $\pi $ to be the monomial
$$ C(\pi ) = t_{1}^{k_{1}}t_{2}^{k_{2}}\cdots . $$
For a group $G$ of permutations we define the cycle indicator to be
the sum of the cycle indicators for permutations in $G$, divided by
the number of elements in $G$:
$$ C_{G}(t_{1},t_{2},\ldots) = \frac{1}{|G|}\sum _{g\in G}C(g). $$

Example: consider the group $C_{5}$ from section 2.  The identity permutation
has 5 1-cycles, so $C({\bf 1}) = t_{1}^{5}$.  Each of the four other
rotations has 1 5-cycle for a cycle indicator of $t_{5}$.  Adding up,
we get
$$ C_{C_{5}} = \frac{1}{5}(t_{1}^{5}+4t_{5}). $$

Example: the group $D_{5}$ from section 2.  In addition to the
identity and four rotations we have 5 reflections each with cycle
indicator $t_{1}t_{2}^{2}$ (2 2-cycles and a 1-cycle).  Thus
$$ C_{D_{5}} = \frac{1}{10}(t_{1}^{5}+4t_{5}+5t_{1}t_{2}^{2}). $$

Example: the group $H$ of rotations of a cube, acting on the faces.  We
can classify the 24 rotations by their axis type and angle.  In
particular, the axis of rotation can pass through two opposite face
centers, or two opposite vertices, or two opposite edge centers.  We
get the table
$$ \begin{array}{c@{\quad }c@{\quad }c}
\mbox{{\rm axis, angle}}&\mbox{{\it C(g)}}&\mbox{{\rm number of
this type}}\\
& & \\
{\bf 1}&				t_{1}^{6}&		1\\
\mbox{{\rm face-center, }}\pm \pi /2&	t_{1}^{2}t_{4}&		6\\
\mbox{{\rm face-center, }}\pi &		t_{1}^{2}t_{2}^{2}&	3\\
\mbox{{\rm vertex, }}\pm 2\pi /3&	t_{3}^{2}&		8\\
\mbox{{\rm edge-center, }}\pi &		t_{2}^{3}&		6.
\end{array} $$
Totalling it up we get
$$ C_{H} =
\frac{1}{24}(t_{1}^{6}+6t_{1}^{2}t_{4}+3t_{1}^{2}t_{2}^{2}+
8t_{3}^{2}+6t_{2}^{3}). $$

Example: the symmetric group $S_{4}$ of all permutations of 4
elements.  They are 1 identity, 6 of the form ($a$ $b$)($c$)($d$), 3
of the form ($a$ $b$)($c$ $d$), 8 of the form ($a$ $b$ $c$)($d$), and
6 of the form ($a$ $b$ $c$ $d$).  We get 
$$ C_{S_{4}} = \frac{1}{24}(t_{1}^{4}+6t_{1}^{2}t_{2}+3t_{2}^{2}+
8t_{1}t_{3}+6t_{4}). $$
Later we will find a systematic way to express the cycle indicators
$C_{S_{n}}$ for all $n$.

\bigskip
%%
\pagebreak

\noindent 4.  Polya--Burnside theorem.

\medskip

We can now state a theorem which gives the solution to symmetric
counting problems of the kind discussed in section 1.

\medskip

\noindent {\it Polya--Burnside theorem:}  Let $G$ be a permutation
group acting on a set $X$ of locations for independent choices.
Suppose at each location in $X$ we are to choose something from a
set $A$ whose elements are counted by an ordinary generating function
$F(x)$.  Then the ordinary generating function counting all
essentially different ways of choosing, where two ways are considered
the same if there is a permutation in $G$ that carries one to other,
is given by 
$$ C_{G}(F(x),F(x^{2}),F(x^{3}),\ldots). $$
That is, by substituting $F(x^{i})$ for $t_{i}$ in the cycle indicator
for $G$.

\medskip

As with all ordinary generating function principles, the resulting generating
function counts a way of choosing with weight $x^{n}$ if its
total size, {\it i.e.}, the total of the sizes of the individual
choices, is $n$.
The theorem also applies to the situation where in place of  $F(x)$ we
have a generating function
$F(x,y,\ldots)$ in more than one variable.  In this situation we substitute
$F(x^{i},y^{i},\ldots)$ for $t_{i}$ in the cycle indicator.

Example:  determine the number of essentially different red/blue colorings
of the faces of a cube, keeping track of the number of red faces.  We
use generating functions in which a pattern has weight $x^{k}$ for $k$
red faces.  The locations for choices are the faces of the cube.  The
choice to be made at each location is red or blue, with generating
function $F(x) = 1+x$.  The permutation group acting is the group $H$
from the previous section, so we get the generating function for
essentially different red/blue colorings to be 
$$ C_{H}(F(x),F(x^{2}),F(x^{3}),F(x^{4})) $$
$$ = C_{H}(1+x,1+x^{2},1+x^{3},1+x^{4})  $$
$$ = \frac{1}{24}((1+x)^{6}+6(1+x)^{2}(1+x^4)+3(1+x)^{2}(1+x^2)^{2}+
8(1+x^3)^{2}+6(1+x^2)^{3}) $$
$$ = \frac{1}{24}(24 + 24x + 48x^{2} + 48x^{3} + 48x^{4} + 24x^{5}+24x^{6}) $$
$$ = 1 + x +2x^{2}+2x^{3}+2x^{4}+x^{5}+ x^{6}. $$
In other words there is one coloring with no red faces, one with 1 red
face, two with 2 red faces, two with 3, two with 4, one with 5, and
one with 6.  With a little thought you can see directly that this is correct.

Example:  the necklace problem from section 1.  We want to count
15-bead necklaces with black and white beads.  The group is $D_{15}$,
consisting of all rotations and reflections of 15 points arranged in a
circle.  Let's compute its cycle indicator.  For ${\bf 1}$ we get
$t_{1}^{15}$.  If we rotate by 3, 6, 9, or 12 beads, the beads break
up into 3 5-cycles so we have $4t_{5}^{3}$ for these.  If we rotate by
5 or 10 beads, we get 5 3-cycles for $2t_{3}^{5}$.  Any other rotation
creates a 15-cycle for $8t_{15}$.  In addition, we have 15
reflections, one centered on each bead.  Such a reflection fixes its central
bead and switches the others in pairs forming 7 2-cycles for
$15t_{1}t_{2}^{7}$.  Our cycle indicator is then
$$ C_{D_{15}} = \frac{1}{30}(t_{1}^{15}+4t_{5}^{3}+2t_{3}^{5}+
8t_{15}+15t_{1}t_{2}^{7}). $$
The choice to be made at each location is to use a black or white
bead.  Let's do this with two variables, using weight $x^{j}y^{k}$ for
a necklace with $j$ black and $k$ white beads.  The generating
function for the choice to be made at each location is then $F(x,y) =
(x+y)$.  For $t_{i}$ we must substitute $(x^{i}+y^{i})$.  Doing this we get
$$ \frac{1}{30}((x+y)^{15}+4(x^5+y^5)^{3}+2(x^3+y^3)^{5}+
8(x^{15}+y^{15})+15(x+y)(x^{2}+y^{2})^{7}) $$
as the generating function counting all 15-bead black-and-white necklaces.


\bigskip

\noindent 5.  Orbits and stabilizers.

\medskip

The one bit of group theory necessary to prove the Polya--Burnside
theorem is a numerical relationship between ``orbits'' and
``stabilizers'' for a permutation group.  We discuss this relationship
here because it is also useful for determining the number of elements
of a permutation group.  The proof of the Polya--Burnside theorem we
give at the end of these notes.

Let $G$ be a group of permutations on a set $X$.  Consider an element
$x\in X$.  We define the {\it orbit} Orbit($x$) to be the set of all
elements gotten by applying permutations in $G$ to the element $x$.
In symbols,
$$ \mbox{{\rm Orbit}}(x) = \{g(x) \:|\: g\in G \}\subseteq X. $$
We define the {\it stabilizer} Stab($x$) to be the ``subgroup''
consisting of all permutations in $g$ that fix $x$.  In symbols,
$$ \mbox{{\rm Stab}}(x) = \{g\in G \:|\: g(x) = x \}\subseteq G. $$

Example: let $X$ be the set of ``facelets'' in a Rubik's cube, nine on
each face.  Let $G$ be the group of permutations of the facelets that
can be done by legal Rubik's cube moves.  If we pick a ``corner''
facelet, we can move it to any other corner position, so the orbit of
any corner facelet $x$ is the set of all corner facelets.  If we pick
an ``edge'' facelet its orbit is similarly the set of all edge
facelets.  The stabilizer of a facelet is the set of all do-able
Rubik's cube operations in which that facelet ends up where it
started.

The basic numerical fact about orbits and stabilizers is:

\medskip

\noindent {\it Orbit--stabilizer theorem:}  Given a permutation group
$G$ acting on a set $X$ we have 
$$ |\mbox{{\rm Orbit}}(x)|\cdot |\mbox{{\rm Stab}}(x)| = |G| $$
for any $x\in X$.

\medskip

{\it Proof:}  Fix $x \in X$.
For each $y\in\Orbit(x)$, define the ``transporter of
$x$ to $y$'' to be $G(x\rightarrow y) = \{g\in G \:|\: g(x) = y \}$.
Each element $g\in G$ is in just one of these transporters, depending
on what $g(x)$ is for that $g$.  The whole group $G$ is therefore the
disjoint union of the transporters $G(x\rightarrow y)$ for the various
elements $y\in\Orbit(x)$.  If we can show that each transporter has
the same number of elements as Stab($x$), the theorem will follow.

To show $|G(x\rightarrow y)| = |$Stab($x$)$|$ we will give a bijection
between these two sets.  Pick an element $h_{0}\in G(x\rightarrow y)$.
We use $h_{0}$ to define the bijection.  Define a
function $\phi \colon $Stab($x$)$\rightarrow G(x\rightarrow y)$ by the
rule $\phi (g) = h_{0}g$.  We must check that $\phi$ really maps
Stab($x$) to $G(x\rightarrow y)$.  For each $g$ in Stab($x$), 
$(\phi(g))(x) = (h_{0}g)(x) = h_{0}(g(x)) = h_{0}(x) = y$, 
so $\phi(g)\in G(x\rightarrow y)$.  
Now we claim that the inverse map $\phi ^{-1}$ 
is given by $\phi^{-1}(h) = h_{0}^{-1}h$.  
Indeed, for every $h$ in Stab($x$),
$\phi (h_{0}^{-1}h) = h_{0}h_{0}^{-1}h = h$,
and for every $g$ in $G(x\rightarrow y)$,
$h_{0}^{-1} (\phi (g)) = h_{0}^{-1}h_{0}g = g$.  
Finally we must check that if $h\in
G(x\rightarrow y)$ then $\phi^{-1}(h)\in\Stab(x)$.  This is true
since $(\phi^{-1}(h))(x) = h_{0}^{-1}(h(x)) = h_{0}^{-1}(y) = x$.  
This completes the proof.

\medskip

An important use of the orbit--stabilizer theorem is simply to find
$|G|$ in cases where it isn't obvious.  For instance, we gave a table
of the cube rotation group $H$ in the last section.  In order to be
sure the table is
complete, we would like to know that the group has 24
elements.  To apply the orbit--stabilizer theorem, let $x$ be the top
face.  Since you can
rotate the top face to any other, Orbit($x$) is the set of all 6 faces.
Stab($x$) consists of those rotations that keep the top face on top.
Including {\bf 1}, there are 4 of these, so the theorem gives $6\cdot
4 = 24$ for the size of the cube rotation group.

\bigskip

\noindent 6.  Cycle indicators for the symmetric groups $S_{n}$.

\medskip

Some very interesting applications of Polya theory occur when the
symmetry group is the group $S_{n}$ of all permutations of
$\{1,\ldots,n \}$.  If as usual $A$ denotes the set of available
choices for each location, then a way of choosing means a selection of
$n$ things from $A$.  With $S_{n}$ as the symmetry group, two ways of
choosing are considered the same if one is {\it any} permutation of
the other.  This means that what we count using the Polya--Burnside
theorem are exactly  unordered combinations of $n$ things from
$A$ (with repetition).  In short, we have:

{\it If $F(x)$ is the ordinary generating function counting  elements
of $A$, then the ordinary generating function counting unordered
combinations with repetition of $n$ things from the set $A$ is given
by}
$$ C_{S_{n}}(F(x),F(x^{2}),\ldots,F(x^{n})), $$
where $C_{S_{n}}(t_{1},t_{2},\ldots,t_{n})$ is the cycle indicator for
$S_{n}$.

We are going to find $C_{S_{n}}$ for all $n$ by a clever use of
exponential generating function principles.  First of all, by
definition
$$ C_{S_{n}} = \frac{1}{n!}\sum _{\pi \in S_{n}}C(\pi ). $$
If we define $CS$ to be an {\it ordinary} generating function for the sequence
$C_{S_{1}}, C_{S_{2}}, C_{S_{3}}, ...$
using a variable $z$, we have
$$ CS(t_{1},t_{2},\ldots;z) = \sum _{n}
C_{S_{n}}(t_{1},t_{2},\ldots)z^{n} = \sum _{n} (\sum _{\pi \in
S_{n}}C(\pi ))\frac{z^{n}}{n!}. $$
We see that $CS$ is also an {\it exponential} generating function
counting the structure of permutations of a finite set
(where $n$ is the number of elements in the set).
However, instead of merely counting each permutation with weight
1, we are counting a permutation $\pi $ with weight $C(\pi )$, which
is the product over its cycles of the weight $t_{k}$ for a $k$-cycle.

This use of $C(\pi )$ presents no particular problem, if we just
improve our exponential generating function counting principles a bit.
A permutation is just a composite structure, consisting of a
partition, with the structure of ``cycle'' on each block, and the
trivial structure among the blocks.  Thus the generating function $CS$
will be $F(G(z))$, where $F(x)$ equals $e^{x}$ and $G(z)$ counts the
structure of ``cycle''.  On a $k$-element set there are $(k-1)!$
possible cycles, and we are to count them each with weight $t_{k}$
instead of 1.  Accordingly, the $z^{k}$ term of $G(z)$ should be
$$ (k-1)!t_{k}z^{k}/k! = t_{k}z^{k}/k. $$
Summing, we have
$$ G(z) = t_{1}z + t_{2}z^{2}/2 + t_{3}z^{3}/3 +\cdots $$
and therefore
$$ CS(t_{1},t_{2},\ldots;z) = e^{G(z)} = e^{t_{1}z + t_{2}z^{2}/2 +
t_{3}z^{3}/3 +\cdots}. $$

This remarkable generating function contains all information about the
numbers of permutations with various cycle structures, as well as the
cycle indicators $C_{S_{n}}$ for all $n$.  As the ordinary generating
function for the cycle indicators $C_{S_{n}}$ it has applications to
Polya theory.  As the exponential generating function for the cycle
indicators of individual permutations it has applications to counting
permutations.  We'll now consider some examples of each.

Example: Partitions.  Let $A$ be the set of positive numbers
$\{1,2,\ldots, \}$, each $i$ taken with weight $x^{i}$, so the
generating function for $A$ is $F(x) = x/(1-x)$.  An unordered
combination with repetition of $n$ elements from $A$ is nothing but a
partition with $n$ parts.  A combination occurs with weight $x^{m}$ if
the numbers $i$ in it total up to $m$, that is, if it's a partition of
$m$.  It follows that
$$ C_{S_{n}}(x/(1-x),x^{2}/(1-x^{2}),\ldots) $$
is the ordinary generating function for partitions with $n$ parts,
that is, $C_{S_{n}}(x/(1-x),x^{2}/(1-x^{2}),\ldots) = P_{n}(x)$.

By the formula for $CS$ we have 
$$ \sum_{n} P_{n}(x)z^{n} = CS(x/(1-x),x/(1-x^{2}),\ldots;z) $$
$$ =
\exp(\frac{zx}{1-x}+\frac{z^{2}x^{2}/2}{1-x^{2}}+
\frac{z^{3}x^{3}/3}{1-x^{3}}+\cdots) $$
$$ = \exp([zx+zx^{2}+zx^{3}+\cdots]
+\frac{1}{2}[z^{2}x^{2}+z^{2}x^{4}+z^{2}x^{6}+\cdots ] +
\frac{1}{3}[z^{3}x^{3}+z^{3}x^{6}+z^{3}x^{9}+\cdots ]+\cdots ) $$
$$ = \exp([zx+z^{2}x^{2}/2+z^{3}x^{3}/3+\cdots]+
[zx^{2}+z^{2}x^{4}/2+z^{3}x^{6}/3+\cdots]+
[zx^{3}+z^{2}x^{6}/2+z^{3}x^{9}/3+\cdots]\cdots) $$ 
$$ =\exp(-\log(1-zx)-\log(1-zx^{2})-\log(1-zx^{3})-\cdots ) =
\frac{1}{1-zx}\frac{1}{1-zx^{2}}\frac{1}{1-zx^{3}}\cdots  $$
which agrees with the two-variable ordinary generating function
counting a partition of $m$ into $n$ parts with weight
$z^{n}x^{m}$.

Example: Unordered unlabeled rooted trees.  Such a tree consists of a
root plus a forest of branches; the forest is in turn an unordered combination,
with repetition, of trees of the same kind.  Here  the number of trees
in the forest is not specified in advance.  If it were, and there were
to be $n$ trees in the forest, then the forest ordinary generating
function would be given by 
$$ C_{S_{n}}(T(x), T(x^{2}),\ldots), $$
where $T(x)$ is the generating function for trees.  (All these
generating functions are {\it ordinary}, since we are counting
unlabeled trees.)  Since $n$ can be any natural number, the true
forest generating function should be
$$ \sum _{n=0}^{\infty }C_{S_{n}}(T(x), T(x^{2}),\ldots) =
CS(T(x),T(x^{2}),\ldots;1). $$
On the right hand side here, we are setting $z=1$ in the generating
function $CS$ to get the sum of the cycle indicators $C_{S_{n}}$.  By
the formula for $CS$, the forest generating function is 
$$ e^{T(x)+T(x^{2})/2+T(x^{3})/3+\cdots } $$
and we arrive at a famous recurrence found by Cayley for the ordinary
generating function $T(x)$ counting unordered unlabeled rooted trees:
$$ T(x) = xe^{T(x)+T(x^{2})/2+T(x^{3})/3+\cdots}. $$

Example: Involutions.  This is an example of the use of $CS$ as an
exponential generating function for permutations.  An {\it involution}
is a permutation $\pi $ that is its own inverse, or equivalently such
that $\pi \pi ={\bf 1}$.  It's not hard to see that $\pi $ is an
involution iff it has only 1-cycles and 2-cycles.  If we set $t_{1} =
t_{2} = 1$ and all other $t_{i} = 0$, then $C(\pi )$ will be $1$ if
$\pi $ is an involution, and 0 otherwise.  It follows immediately that
the exponential generating function counting involutions on $n$
elements for each $n$ is given by
$$ I(z) = CS(1,1,0,0,0,\ldots;z). $$
Using the formula for $CS$ we find that this is
$$ I(z) = e^{z+z^{2}/2}. $$
An alternative way to arrive at $I(z)$ is by the composition
principle: an involution is a partition into 1- and 2-element subsets
(the cycles).  The delta series $z+z^{2}/2$ is the generating function
for the trivial structure of ``1- or 2-element set'', so
$e^{z+z^{2}/2}$ counts partitions into these.


\bigskip

% \noindent Appendix:  Proof of the Polya--Burnside theorem.
\noindent 7.  Proof of the Polya--Burnside theorem.

\medskip

The key to the proof of the Polya--Burnside theorem is a special application
of the orbit--stabilizer theorem,
known as Burnside's Lemma.

\medskip

\noindent {\it Burnside's Lemma:} Let $G$ be a permutation group
acting on a set $W$.  Suppose each element in $W$ is assigned a weight
and that elements in the same orbit have the same weight.  For each
element $g\in G$ define Fix($g$) to be the set of elements $u\in W$
fixed by $g$; in symbols $\mbox{{\rm Fix}}(g) = \{u\in W \:|\: g(u) = u \}$.
Write $||\mbox{{\rm Fix}}(g)||$ for the sum of the weights of the
elements in Fix($g$).  Similarly write $||\mbox{{\rm Orb}}||$ for the
sum in which we count each orbit in $W$ by the weight of any one of
its elements.  Then
$$ ||\mbox{{\rm Orb}}|| = \frac{1}{|G|}\sum _{g\in G}||\mbox{{\rm Fix}}(g)||.$$

\medskip

{\it Proof:}  Let's count all pairs $(g,u)$ in which $g$ belongs to
the group $G$ and $u$ is an element of $W$ fixed by $g$.  We'll count
each pair with the weight of $u$ as its weight, and we'll do the
counting two ways.

First way: For each $g$ we'll count all pairs for that $g$, then add
up for all elements $g$.  For a given $g$ we have one pair  $(g,u)$
for each $u\in \mbox{{\rm Fix}}(g)$.  The weights of these pairs total
to $||\mbox{{\rm Fix}}(g)||$, and so the total for all pairs $(g,u)$ is
$$ \sum _{g\in G}||\mbox{{\rm Fix}}(g)||. $$

Second way:  For each $u$ we'll count all pairs for that $u$, then add
up for all elements $u$.  For a given $u$ we have one pair $(g,u)$ for
each $g\in \mbox{{\rm Stab}}(u)$.  The number of these is then
$|G|/|\mbox{{\rm Orbit}}(u)|$.  Thus every $u$ in $W$ will contribute
to the total its weight times $|G|/|\mbox{{\rm Orbit}}(u)|$.  Consider
all the elements in the orbit of $u$.  Their number is $|\mbox{{\rm
Orbit}}(u)|$, and each contributes $|G|/|\mbox{{\rm Orbit}}(u)|$ times
the weight of $u$ to the total.  Thus the entire orbit contributes to
the total
$|G|$ times the weight of any one of its elements, and the total for
all pairs $(g,u)$ is $|G|\cdot||\mbox{{\rm Orb}}||$.

Equating the totals from the two ways of counting, we get the result.

\medskip

The Polya--Burnside theorem is proved by using Burnside's Lemma on an
appropriate set $W$.  Recall the situation in which the
Polya--Burnside theorem applies: we have a group $G$ permuting a set
$X$ of locations for choices, and a set $A$ of allowed choices with
generating function $F(x)$ counting elements of $A$.  What we are to
count is ways of choosing, that is, functions from $X$ to $A$.

  Let $W$ be the set of ways of choosing.  In counting them with an
ordinary generating function, we are giving each way a weight, which
is just the product of the weights of the choices made at the various
locations in $X$.  Each group element, by permuting the locations $X$,
also permutes the ways of choosing.  Such a permutation does not
change the weight of a way of choosing since it just rearranges the
elements of $A$ that are chosen.  Thus we can regard $G$ not only as a
group of permutations of $X$, but as a group of permutations of $W$,
one in which elements belonging to the same orbit ({\it i.e.}, ways of
choosing that differ by a symmetry in $G$) have the same weight.
Furthermore, the problem of counting ways of choosing, up to symmetry,
asks exactly for the total of the weights of $W$, but counted only
once for each orbit.

The generating function we seek
is exactly the quantity $||\mbox{{\rm Orb}}||$ from the Burnside
Lemma, applied to the action of $G$ on $W$.  To find it, we need to
know the quantity $||\mbox{{\rm Fix}}(g)||$ for each permutation in $G$.
Now $g$ permutes the locations $X$ by sending each one to the next in
its cycle.  If a way of choosing is to be fixed by $g$, then moving
the  choices along the cycles  must leave the whole way of
choosing unchanged.  That happens if, and only if, for each cycle of
$g$, we choose the same element of $A$ at every location in the cycle.

To choose an element of $\mbox{{\rm Fix}}(g)$, then, we must choose
independently for each cycle an element of $A$, to be used at all
locations in that cycle.  The generating function $||\mbox{{\rm
Fix}}(g)||$ will thus be the product of the generating functions
corresponding to the cycles of $g$.  Consider a $k$-cycle.  We are to
choose any one element of $A$.  However, whatever element we choose
will appear at $k$ locations and thus it will contribute $k$ times its
size.  In short, choosing an element of weight $x^{n}$ for use at all
locations along a $k$-cycle contributes $x^{kn}$ to the weight of the
way of choosing.  This means the generating function for choices on
our $k$-cycle will be the generating function for $A$, with $x^{k}$
substituted in place of $x$.  In other words, it is $F(x^{k})$.

Summarizing what we just said, the generating function $||\mbox{{\rm
Fix}}(g)||$ is the product, over all cycles of $g$, of $F(x^{k})$ for a
$k$-cycle.  By definition, $C(g)$ is the product over all cycles of
$t_{k}$ for a $k$-cycle, so $||\mbox{{\rm Fix}}(g)||$ is the result of
substituting $F(x^{k})$ for $t_{k}$ in $C(g)$.  Finally, summing for
all $g$ and dividing by $|G|$, we find the expression for $||\mbox{{\rm
Orb}}||$ from the Burnside Lemma to be the result of substituting
$F(x^{k})$ for $t_{k}$ in
$$ \frac{1}{|G|}\sum _{g\in G}C(g). $$
Since the above sum is by definition the cycle indicator $C_{G}$, the
Polya--Burnside theorem is proved.

\end{document}
