\documentstyle{amsppt}\magnification=\magstephalf \hsize=16truecm \vsize=23 truecm
 \TagsOnRight \nologo 
\def\C{\Bbb C}  \def\Z{\Bbb Z} \def\Q{\Bbb Q} \def\s{S}   \def\N{\Cal N} \def\Y{\Cal Y}  \def\n{\Z_{>0}} \def\n{\Bbb N}
 \def\Hom{\text{\rm Hom}}  \def\HG{\Hom_G} \def\HC{\Hom_{\C}} \def\End{\text{\rm End}}  \def\wS{\widehat S}
\def\a{\alpha} \def\c{\Cal C}  \def\r{\Cal R} \def\l{\lambda} \def\P{\Phi} \def\wP{\widetilde P} \def\wF{\widetilde\P}
\def\1{\bold 1} \def\e{\pmb\varepsilon}  \def\St{\text{\bf St}}  \def\i{^{-1}}
\def\={\;=\;}   \def\+{\,+\,}   \def\endpf{$\quad\square$\enddemo}

%\def\fatrule{\noalign{\smallskip\hrule height0.5pt\smallskip}}
%\def\thinrule{\noalign{\smallskip\hrule height0.2pt\smallskip}}  \def\norule{\noalign{\medskip}} 

\null\medskip\centerline{\bf Applications of the representation theory of finite groups}\medskip
\centerline{\bf Appendix by D.~Zagier to}
\centerline{\bf ``Graphs on Surfaces and Their Applications", by S.~Lando and A.~Zvonkin}\bigskip

%\topmatter\title Appendix. Applications of the representation theory of finite groups \endtitle
%\author Don Zagier\endauthor\endtopmatter


This appendix consists of two sections.  In the first we give a self-contained and fairly complete introduction
to the representation and character theory of finite groups, including Frobenius's formula and a higher
genus generalization.  In the second we give several applications related to topics treated in this book.\smallskip

\heading 1. Representation theory of finite groups \endheading
\subheading{1.1. Irreducible representations and characters}
Let $G$ be a finite group.  A (finite-dimensional; we will always assume this) {\it representation} $(V,\pi)$
of $G$ is a finite-dimensional complex vector space $V$ and a homomorphism $\pi:\,G\to GL(V)$.  Thus 
each $g\in G$ defines a linear map $v\mapsto\pi(g)v$ from $V$ to $V$, with $\pi(g_1g_2)=\pi(g_1)\pi(g_2)$.
One often drops the ``$\pi$" and writes the action simply as $v\mapsto gv$.  
Alternatively, one often drops the ``$V$" and simply denotes the representation itself by $\pi$.
The definition given here corresponds to left representations; one also has right representations
(where $v\mapsto vg$ with $v(g_1g_2)=(vg_1)g_2$); this leads to an isomorphic theory, by replacing $g$ by $g\i$.

We call two representations $V$ and $V'$ {\it isomorphic}, denoted $V\simeq V'$, if there is a
$G$-equivariant isomorphism from $V$ to $V'$, and write $V\cong V'$ if such an isomorphism has been fixed.
If $V$ is a (left) representation of $G$ and $A$ a complex vector space, then both $V\otimes_\C A$ and
$\Hom_\C(A,V)$ are (left) representations in the obvious way ($g(v\otimes a)=(gv)\otimes a$,
$(g\phi)(a)=g\phi(a)$).  If $\dim_\C A=k$, then both of these representations are isomorphic to
$V\oplus\cdots\oplus V$ ($k$ copies), the isomorphisms being canonical if one has chosen a basis of $A$.
Similarly,  the dual space $V^*=\Hom_\C(V,\C)$ is in a natural way a right representation of $G$ via 
$(\phi g)(v)=\phi(gv)$ and the space $\Hom_\C(V,A)$ is also a right representation,
isomorphic to $k$ copies of $V^*$. 
% If $V$ and $V'$ are two representations of $G$, then $V\otimes_GV'$ 
% (= quotient of $V\otimes_\C V'$ by the relation $gv\otimes v'=v\otimes gv'$) and $\HG(V,V')$ (= set of
% {$G$-equivariant} linear maps from $V$ to $V'$) are simply vector spaces, without any natural $G$-action.
Finally, if $V$ and $V'$ are two representations of $G$, then we write $V\otimes_GV'$ 
for the quotient of $V\otimes_\C V'$ by the relation $gv\otimes v'=v\otimes gv'$ and $\HG(V,V')$ for the set of
$G$-equivariant linear maps from $V$ to $V'$; these are simply vector spaces, without any natural $G$-action.


A representation $V$ of $G$ is called {\it irreducible} if it contains no proper subspace which
is invariant under the action of $G$.  As a simple example, let $G=\s_n$ and $V=\C^n$ with the obvious
action of $G$ by permutation of the coordinates.  Then $V$ is not irreducible, since it contains the two
subspaces $W_1=\{(x,\ldots,x)\mid x\in\C\}$ and $W_2=\{(x_1,\ldots,x_n)\in\C^n\mid x_1+\cdots+x_n=0\}$,
of dimensions 1 and $n-1$ respectively, which are obviously invariant under the action of $G$.  On the other
hand, these two representations are irreducible and $V$ is their direct sum.  More generally, one has:
\proclaim{Lemma 1} Any representation of $G$ is a direct sum of irreducible ones.\endproclaim
\demo{Proof} Pick a $G$-invariant non-degenerate scalar product on $V$.  (To obtain one, start with
any positive-definite scalar product and replace it by the obvious average over $G$.)  If $V$
is not already irreducible, it contains a proper $G$-invariant subspace $W$.  But then the orthogonal
complement $W^\perp$ of $W$ is also $G$-invariant, and $V=W\oplus W^\perp$.  The result now follows by
induction on the dimension.\endpf
This will be used in conjunction with the following property of irreducible representations:
\proclaim{Lemma 2 (Schur's Lemma)} Let $V$ and $V'$ be two irreducible representations of $G$.  Then
the complex vector space $\HG(V,V')$ is $0$-dimensional if $V\not\simeq V'$ and $1$-dimensional if $V\simeq V'$.
The space $\HG(V,V)$ is canonically isomorphic to $\C$.\endproclaim
\demo{Proof} Since neither $V$ nor $V'$ has a non-trivial $G$-invariant subspace, any non-zero $G$-equivariant
map $\phi:V\to V'$ has trivial kernel and cokernel.  Hence $\HG(V,V')=\{0\}$ if $V$ and $V'$ are not isomorphic.
If they are, then we may assume that $V'=V$. Then for any eigenvalue $\l$ of $\phi$, the map $\phi-\l$ has
a kernel and therefore is zero. Hence $\HG(V,V)\cong\C$ canonically. \endpf

These two lemmas already suffice to prove one of the first basic facts of the theory, the ``first orthogonality 
relation for characters."  If $(V,\pi)$ is an irreducible representation, we define its {\it character}
as the function $\chi_\pi(g)=\text{tr}(\pi(g),V)$ from $G$ to $\C$. Then we have:
\proclaim{Corollary (First orthogonality relation)} Let $(V,\pi)$ and $(V',\pi')$ be two irreducible
representations of $G$.  Then
$$ \frac1{|G|}\,\sum_{g\in G}\,\chi_\pi(g)\,\overline{\chi_{\pi'}(g)} 
 \=\cases 1&\text{if $\pi\simeq\pi'$,}\\ 0&\text{otherwise.}\endcases \tag1$$  \endproclaim
\demo{Proof} The dimension of the space $V^G$ of $G$-invariant vectors in any representation $V$ of $G$ is
given by $\dim(V^G)=|G|\i\sum_{g\in G}\text{tr}(g,V)$.
({\it Proof.} The linear map $v\mapsto|G|\i\sum_{g\in G}gv$ is a projection from $V$ to $V^G$,
so its trace equals $\dim V^G$.)  Apply this to the $G$-representation $\Hom_\C(V,V')\cong V\otimes_\C{V'}^*$,
with $G$ acting by $g(v,\phi)=(gv,\phi\circ g\i)$.  (Recall that ${V'}^*$ is naturally a right
representation of $G$, so that we have to replace $g$ by $g\i$ when we act from the left.) Then the
trace of $g\in G$ equals $\chi_\pi(g)\overline{\chi_{\pi'}(g)}$, and the dimension of 
$\bigl(\Hom(V,V')\bigr)^G=\HG(V,V')$ is~1 or~0 by Schur's Lemma. \endpf

Now let $\{(V_i,\pi_i)\}_{i\in I}$ be a full set of non-isomorphic irreducible representations of $G$. Lemma~1
tells us that any representation $V$ of $G$ is isomorphic to a direct sum $\bigoplus\limits_{i\in I}
\undersetbrace k_i\to{V_i\oplus\cdots\oplus V_i}$ of the representations $V_i$ or equivalently,
by what was said above, that 
$$V\cong\bigoplus_i\,V_i\otimes_\C A_i\cong\bigoplus_i\,\Hom_\C(B_i,V_i)\tag2$$
for some $k_i$-dimensional vector spaces $A_i$ and $B_i$ over $\C$, but we do not yet know that these spaces,
or even the multiplicities $k_i$, are independent of the decomposition chosen.  The following lemma shows
that this is true and gives a canonical description of the spaces $A_i$ and $B_i$.
\proclaim{Lemma 3} Let $V$ be an arbitrary representation of $G$. Then we have canonical $G$-equivariant isomorphisms
$$ \bigoplus_{i\in I}V_i\otimes_\C\HG(V_i,V)\,\overset\sim\to\longrightarrow\,V\,,\qquad
V \,\overset\sim\to\longrightarrow\,\bigoplus_{i\in I}\Hom_\C(\HG(V,V_i),\,V_i)\tag3$$
given by sending $x\otimes\phi\in V_i\otimes\HG(V_i,V)$ to $\phi(x)$ and $v\in V$
to the homomorphism $\phi\mapsto\phi(v)$ from $\HG(V,V_i)$ to $V_i$. Conversely, given any
decompositions of $V$ of the form~$(2)$, there are canonical isomorphisms $A_i\cong\HG(V_i,V)$
and $B_i\cong\HG(V,V_i)$ as complex vector spaces. \endproclaim
\demo{Proof} Since both isomorphisms in (2) are additive under direct sums, we may assume by Lemma~1 that
$V$ is irreducible, say $V=V_j$ for some $j\in I$.  Then both statements in (3) follow immediately from 
Lemma~2, since $V_j\otimes_\C\C\cong\Hom_\C(\C,V_j)\cong V_j\,$.  The proof of the last
statement, which will not be used in what follows, is similar and will be left to the reader. \endpf

We next introduce the {\it group algebra} $\C[G]$.  This is the set of linear combinations $\sum_{g\in G}\a_g[g]$
($\a_g\in\C$) of formal symbols $[g]$ ($g\in G$), with the obvious addition and multiplication. It can be identified
with $\,\text{Maps}(G,\C)$ via $\a(g)=\a_g$.  The group algebra is a left {\it and} right representation of $G$ via
$g_1[g]g_2=[g_1gg_2]$, or equivalently $(g_1\a g_2)(g)=\a(g_1\i gg_2\i )$ if $\a$ is a map from $G$ to $\C$.
The central result of the representation theory of finite groups is the following assertion.
\proclaim{Theorem 1}  Let $G$ be a finite group.  Then there is a canonical $(G\times G)$-equivariant algebra isomorphism 
$$\C[G]\;\cong\;\,\bigoplus_{i\in I}\End_\C(V_i)\tag4$$
sending $[g]$ to the collection of linear maps $\pi_i(g):V_i\to V_i$. \endproclaim
\demo{Proof}  For any representation $V$ of $G$,  $\HG(\C[G],V)\cong V$ as $G$-representations, since
an equivariant map $\phi:\C[G]\to V$ is uniquely determined by $\phi([1])\in V$, which is arbitrary. 
Applying this to $V=V_i$ ($i\in I$) and then applying the second isomorphism in (3) to $V=\C[G]$,
we obtain the assertion of the theorem. We can also obtain the isomorphism~(4), in the reverse direction,
by applying the first isomorphism in~(3) to $V=\C[G]$ and using the canonical isomorphisms
 $\HG(V_i,\C[G])\cong V_i^*$ and $V_i\otimes_\C V_i^*\cong\Hom_\C(V_i,V_i)\cong\End_\C(V_i)$.  \endpf
Essentially all important general facts about representations of finite groups are corollaries of
this theorem. To state them, let us introduce the notation $\c$ for the set of conjugacy classes in $G$
and $\r$ for the set of isomorphism classes of irreducible representations. (Of course $\r$ and the index set $I$ 
used above are in canonical bijection, but we will no longer need to have picked representatives for the elements
of $\r$.) Since the value of the character $\chi_\pi(g)$ depends only on the isomorphism class of $\pi$ and the
conjugacy class of $g$, we can write, with some abuse of notation, $\chi_\pi(C)$ for any $\pi\in\r$ and
$C\in\c$. For instance, with these notations the first orthogonality relation~(1) becomes
$$\sum_{C\in\c}\,|C|\,\chi_\pi(C)\,\overline{\chi_{\pi'}(C)}\=|G|\,\delta_{\pi,\pi'}\qquad(\pi,\,\pi'\in\r)\,.\tag5$$
Then Theorem~1 has the following consequences.
\proclaim{Corollary 1} The cardinality of $\r$ is finite and
 $$\sum_{\pi\in\r}(\dim\pi)^2\,=\,|G|\,.\tag6$$  \endproclaim
\demo{Proof} Compare the dimensions on both sides of (4).\endpf
\proclaim{Corollary 2} The sets $\c$ and $\r$ have the same cardinality: there are as many irreducible
representations of $G$ as there are conjugacy classes in $G$. \endproclaim
\demo{Proof} A basis for the center $Z(\C[G])$ of $\C[G]$ is clearly given by the elements 
$e_C=\sum_{g\in C}[g]$ ($C\in\c$).  On the other hand, $\End_\C(V_i)$ is the matrix algebra $M_{\dim V_i}(\C)$,
with 1-dimensional center. Hence the algebra isomorphism (4) tells us that $|\c|=\dim_\C Z(\C[G])=|\r|$.\endpf
\proclaim{Corollary 3 (Second orthogonality relation)}Let $C_1,\,C_2\in\c$. Then
$$\sum_{\pi\in\r}\chi_\pi(C_1)\overline{\chi_\pi(C_2)}
  \=\cases |G|/|C_1|&\text{if $\,C_1=C_2$,}\\ \quad0&\text{otherwise.}\endcases\tag7$$  \endproclaim 
\noindent Notice that this formula agrees with~(6) when $C_1=C_2=\{1\}$, since $\,\chi_\pi(1)=\dim\pi$.
\demo{Proof} This follows from equation~(5) and Corollary~2, since these imply that the matrix 
$\bigl(|C|^{1/2}|G|^{-1/2}\chi_\pi(C)\bigr)_{\pi\in\r,\,C\in\c}$ is square and unitary, and the inverse of
a unitary matrix is also unitary.  But we can also obtain~(7) directly (and then, if we wish, deduce~(5) 
from it) by computing the trace of the action of $(g_1,g_2)\in C_1\times C_2$ on both sides of~(4).
The action of $(g_1,g_2)$ on the basis $\{[g]\}_{g\in G}$ of $\C[G]$ is given by the permutation 
$[g]\mapsto[g_1gg_2\i ]$ (as before, we have to invert $g_2$ to turn the right action
into a left one), so its trace is the number of fixed points of this permutation, which is clearly
$|G|/|C_1|$ if $g_1$ and $g_2$ are conjugate and 0 otherwise.  On the other hand, the trace of
$(g_1,g_2)$ on $\End_\C(\pi)=\pi\otimes_\C\pi^*$ equals $\chi_\pi(g_1)\overline{\chi_\pi(g_2)}$. \endpf

\newpage
\subheading{1.2. Examples} We illustrate the theory explained in \S1.1 in a few important special cases.

\subheading{Abelian groups} If $G$ is a cyclic group of order $n$, with generator $\gamma$,
then there are $n$ obvious 1-dimensional (and hence irreducible!) representations of $G$ given by
$V=\C$ and $\gamma v=\zeta v$ with $\zeta\in\C$ a (not necessarily primitive) $n$th root of unity.
By the dimension formula~(6), these are the only irreducible representations. More generally, for any
finite abelian group one sees easily that all irreducible representations of $G$ are 1-dimensional
(because the commuting operators $\pi(g)$ on any representation $V$ have a common eigenvector, or 
alternatively by reducing to the cyclic case) and that the corresponding characters are simply the
homomorphisms from $G$ to~$\C^*$.

\subheading{Symmetric groups of small order}  The symmetric group $\s_n$ has two 1-dimensional
representations $\1$ (the trivial representation, $V=\C$ with all elements of $G$ acting as $+1$)
and $\e_n$ (the {\it sign} representation, $V=\C$ with odd permutations acting as $-1$) and an
$(n-1)$-dimensional irreducible representation $\St_n$ which is the space $W_2\subset\C^n$ mentioned at the
beginning of this section.  For $n=2$ and $n=3$, the dimension formula~(6) shows that these are
the only irreducible representations (and $\St_n\simeq\e_n$ for $n=2$), with character tables given by
$$\vbox{\setbox\strutbox=\hbox{\vrule width 0pt height 10pt depth 5pt}\tenrm\tabskip=0pt \offinterlineskip
\halign{\strut \hfil$#\;$\tabskip=.4em plus 0em&\vrule#&\hfil$#$\hfil& #&\hfil$#$\hfil& #&\hfil$#$\quad\hfil& #&\hfil$#$\hfil& #&\hfil$#$
\hfil&\vrule#&\hfil\qquad\quad$#$\hfil&\vrule#&\hfil$#$\hfil& #&\hfil$#$\hfil& #&\hfil$#$\hfil& #&\hfil$#$\quad\hfil& #&\hfil$#$\hfil& #&#\cr
 &\omit&\1&\omit&\e_2&\omit&\omit&\omit&|C|&\omit&\omit&\omit&\omit&\omit&\1&\omit&\e_3&\omit&\St_3&\omit&\omit&\omit&|C|\cr 
\omit&\multispan5\hrulefill&\omit&\multispan3\hrulefill&\omit&\omit&\omit&\multispan7\hrulefill&\omit&\multispan3\hrulefill\cr
\text{Id}&&1&&\phantom{-}1&&&&1&&\omit&\omit&\text{Id}&&1&&\phantom{-}1&&\phantom{-}2&&&&1&\cr 
(12)&&1&&-1&&&&1&&\omit&\omit&\text{(12)}&&1&&-1&&\phantom{-}0&&&&3&\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\text{(123)}&&1&&\phantom{-}1&&-1&&&&2&\cr}}$$
(Here the numbers on the right show the size of the conjugacy classes, needed as weights to make
the columns of the table orthogonal; the rows are orthogonal as they stand.)
For $n=4$, the orthogonality relations again have a unique solution and the character table must take the form
$$\vbox{\setbox\strutbox=\hbox{\vrule width 0pt height 10pt depth 5pt}\tenrm\tabskip=0pt \offinterlineskip
\halign{\strut \hfil$#\;$\tabskip=.4em plus 0em&\vrule#&\hfil$#$\hfil& #&\hfil$#$\hfil& #&\hfil$#$\hfil&
 #&\hfil$#$\hfil& #&\hfil$#$\hfil& #&\hfil\quad$#$\hfil& #&\hfil$#$\hfil&
 #&\hfil$#$\hfil&\vrule#&\hfil$#$\hfil&\vrule#&\hfil$#$\hfil&\vrule#&#\cr
 &\omit&\1&\omit&\e_4&\omit&A&\omit&\St_4&\omit&\St_4\otimes\e_4&\omit&\omit&\omit&|C|\cr 
\omit&\multispan{11}\hrulefill&\omit&\multispan3\hrulefill&\cr
\text{Id}&&1&&\phantom{-}1&&\phantom{-}2&&\phantom{-}3&&\phantom{-}3&&&&1&\cr 
\text{(12)}&&1&&-1&&\phantom{-}0&&\phantom{-}1&&-1&&&&6&\cr 
\text{(123)}&&1&&\phantom{-}1&&-1&&\phantom{-}0&&\phantom{-}0&&&&8&\cr 
\text{(12)(34)}&&1&&\phantom{-}1&&\phantom{-}2&&-1&&-1&&&&3&\cr 
\text{(1234)}&&1&&-1&&\phantom{-}0&&-1&&\phantom{-}1&&&&6&\cr}}$$
for some 2-dimensional irreducible representation $A$ of $\s_4$. We can construct $A$ explicitly
as $\{(x_s)_{s\in S}\mid\sum x_s=0\}$, where $S$ is the 3-element set of
decompositions of $\{1,2,3,4\}$ into two (unordered) subsets of cardinality~2.
The reader may wish to attempt constructing ``by hand" the $7\times7$ character table for the group $\s_5$,
where the dimensions of the irreducible representations are 1, 1, 4, 4, 5, 5 and 6.  

Observe that in the above tables for $\s_n$ the character values $\chi_\pi(g)$ are all integers.  This
is a general fact. For arbitrary finite group representations, $\chi_\pi(g)$ is a sum of roots of
unity and hence an algebraic integer, and its Galois conjugates are simply the values of $\chi_\pi(g^\ell)$
with $\ell\in\Z$ prime to the order of $g$.  (This is because the action of $\,\text{Gal}(\overline\Q/\Q)$ on 
roots of unity is given by $\zeta\mapsto\zeta^\ell$ with $\ell$ prime to the order of $\zeta$.) For
$G=\s_n$, however, $g^\ell$ and $g$ are conjugate since they have the same cycle structure, so $\chi_\pi(g)$
is Galois invariant and hence belongs to $\Z$.

\subheading{Symmetric groups of arbitrary order} We will not give a complete account of the general representation
theory of $\s_n$ here, since it is a little complicated and there are many good accounts, but will only mention some
highlights, following the approach given in the beautiful paper [OV], which we highly recommend to the reader.  The
statements given here will be used only in \S2.3.  We denote by $\r_n$ the sets of isomorphism classes of irreducible
representations of $\s_n$.  We will also consider $\s_{n-1}$ as a subgroup of $\s_n$ (namely, the set of elements
fixing $n$), and similarly for all $\s_i$, $i<n$.
\smallskip
{\bf A.} The first basic fact is that each irreducible representation of $\s_n$, when restricted to the
subgroup $\s_{n-1}$, splits into the direct sum of distinct irreducible
representations of $\s_{n-1}$. For $\pi\in\r_n$ and $\pi'\in\r_{n-1}$ we write $\pi'\prec\pi$ if $\pi'$
occurs in $\pi|_{\s_{n-1}}$, so $\pi|_{\s_{n-1}}=\oplus_{\pi'\prec\pi}\pi'$.  Similarly, each $\pi'\prec\pi$
when restricted to $\s_{n-2}$ splits into a sum of irreducible rerpresentations $\pi''$ of $\s_{n-2}$, and continuing
this process, we see that $\pi$ splits canonically into a direct sum of 1-dimensional spaces $V_\xi$ indexed
by all possible chains $\xi:\pi_1\prec\cdots\prec\pi_n=\pi$ with $\pi_i\in\r_i$.  (Specifically, we have
$V_\xi=V_1\subset\cdots\subset V_n=\pi$ where each $V_i$ is $\s_i$-invariant and isomorphic to $\pi_i$.) Notice how 
unusual this behavior is: for general finite groups $G$ it is more modern, and of course better, to think of representations
as actions of $G$ on abstract vector spaces, without any choice of basis, rather than as collections of matrices
satsifying the same relations as the elements of $G$, but for the symmetric groups the irreducible representations
come equipped with their own nearly (i.e., up to scalar multiples) canonical bases, and we have matrices after all!
\smallskip
{\bf B.} The next key idea is to introduce the so-called {\it Jucys-Murphy element}
$$ X_n\=(1\;n)\+(2\;n)\+\cdots\+(n-1\;n)$$
of the group algebra $\Z[S_n]$.  We can write this element as $e_{[T]_n}-e_{[T]_{n-1}}$, where $e_{[T]_n}\in Z(\Z[S_n])$
as in the proof of Corollary~2 above is the sum of all elements in the conjugacy class $[T]_n$ of $T=(1\,2)\in S_n$
and $e_{[T]_{n-1}}$ is the corresponding element for $n-1$.  Since $e_{[T]_n}$ is central, by Schur's lemma it acts on each $\pi\in\r_n$, and hence on each subrepresentation $\pi'\prec\pi$, as multiplication by a scalar $\nu_\pi(T)$ (which belongs
to $\Z$ by the remark on integrality made above), and similarly $e_{[T]_{n-1}}$ acts on $\pi'$ as a scalar $\nu_{\pi'}(T)$,
so $X_n$ acts on $\pi'$ as multiplication by the number $a_n=\nu_\pi(T)-\nu_{\pi'}(T)$.  By induction on $i$ it follows that 
for each chain $\xi=(\pi_1,\dots,\pi_n)$ each element $X_i\in\Z[S_i]\subset\Z[S_n]$ acts on $\pi_{i-1}$ as multiplication by
some integer $a_i(\xi)$, so we can associate to the chain $\xi$ a {\it weight vector} $a(\xi)=(a_1(\xi),\dots,a_n(\xi))\in\Z^n$. 
\smallskip
{\bf C.} Conversely, the weight vector $a(\xi)$ determines $\xi$ (and hence also $\pi$) completely, and there is a
complete description of which vectors $a=(a_1,\dots,a_n)\in\Z^n$ occur as weight vectors. (The conditions are 
(i) $a_1=0$, (ii) for each $j>1$, we have $|a_j-a_i|=1$ for some $i<j$, and (iii) if $a_i=a_j$ for some $i<j$ then
both $a_i-1$ and $a_i+1$ occur among the $a_k$ with $i<k<j$.) Furthermore, two weight vectors $a,\,a'\in\Z^n$ correpond
to the same representation $\pi$ if and only if they are permutations of one another, so that $\pi$ is uniquely 
characterized by the function $f:\Z\to\Z_{\ge0}$ defined by $f(r)=\#\{i\mid a_i=r\}$, and this sets up a bijection
between $\r_n$ and the set of finitely supported functions $f:\Z\to\Z_{\ge0}$ satisfying $f(r+1)-f(r)\in\{0,|r|-|r+1|\}$
for all $r$ and $\sum_{r\in\Z}f(r)=n$. These functions in turn correspond bijectively to the elements of the set $\Y_n$
of {\it Young diagrams} (= subsets $Y\subset\n^2$ such that $(x,y)\in Y\Rightarrow(x',y')\in Y$ whenever
$1\le x'\le x$, $1\le y'\le y$) of cardinality $n$, the correspondence $f\leftrightarrow Y$ being given by
$f(r)=\#\{(x,y)\in Y\mid x-y=r\}$ and $Y=\{(x,y)\in\n^2\mid\min(x,y)\le f(x-y)\}$. In the bijection between 
$\r_n$ and $\Y_n$ obtained in this way one has $\pi'\prec\pi$ if and only if the corresponding Young diagrams
$Y'\in\Y_{n-1}$ and $Y\in\Y_n$ satisfy $Y'\subset Y$.
\smallskip
{\bf D.} Finally, there is an explicit inductive procedure, given by the so-called {\it Murnaghan-Nakayama rule}, to compute
the value of the character $\chi_\pi(C)$ for any $\pi\in\r_n$ and conjugacy class $C\subset S_n$ in terms of the Young diagram
associated to $\pi$ and the partition of $n$ associated to $C$.  However, we will not use this and do not give the 
details here, noting only that the case $C=[T]_n$, which will be needed in \S2.3, follows from {\bf B.} and {\bf C.} above.


 \newpage
\subheading{1.3. Frobenius's formula}
We end \S1 by describing a formula which has applications to combinatorial problems in many parts of
mathematics and in particular to several of the topics treated in this book; some of these applications
will be discussed in \S2.  This formula computes the number
$$ \N(G;C_1,\dots,C_k) := \#\,\bigl\{(c_1,\dots,c_k)\in C_1\times\dots \times C_k\mid c_1\cdots c_k=1\bigr\}$$
for arbitrary conjugacy classes $C_1,\ldots,C_k\in\c$ in terms of the
characters of the irreducible representations of $G$.  
Note that $\N(G;C_1,\dots,C_k)$ is independent of the order of the arguments, because the identity
$c_ic_{i+1}=c_{i+1}(c_{i+1}\i c_ic_{i+1})$ lets us interchange $C_i$ and $C_{i+1}$.

\proclaim{Theorem 2 (Frobenius's formula)} Let $G$ be a finite group and $C_1,\ldots,C_k$ 
conjugacy classes in $G$. Then
$$\N(G;C_1,\dots,C_k)= \frac{|C_1|\cdots|C_k|}{|G|} \sum_\chi \frac{\chi(C_1)\cdots\chi(C_k)}{\chi(1)^{k-2}}\,,\tag 8$$
where the sum is over all characters of irreducible representations of $G$. \endproclaim
Before giving the proof, we note three special cases.  If $k=1$ or $k=2$, then~(8) reduces to
the orthogonality relation~(7), applied to $(C_1,1)$ or $(C_1,C_2\i )$, respectively.  For $k=3$,
we write  $(C_1,C_2,C_3)=(A,B,C\i )$ with $A,\,B,\,C\in\c$.  Then $\N(G;C_1,C_2,C_3)=n_{AB}^C$, where
$$ n_{AB}^C\=\#\bigl\{(a,b)\in A\times B\mid ab\in C\bigr\}\,.$$
The integers $n_{AB}^C$ are nothing but the structure constants (i.e., the numbers defined by
$e_Ae_B=\sum_C n_{AB}^Ce_C$) of the center of the group ring $\Z[G]$ with respect to the basis $\{e_C\}$
defined in the proof of Corollary 2 above.  Formula~(8) therefore describes the ring structure of this
commutative ring in terms of the character theory of $G$.  This formula plays a role in mathematical
physics in connection with the so-called ``fusion algebras." 
\demo{Proof} If $C$ is any conjugacy class of $G$, then the element $e_C=\sum_{g\in C}[g]$ is central
and hence, by Schur's lemma, acts on any irreducible representation $\pi$ of $G$ as multiplication by
a scalar $\nu_\pi(C)$.  Since each element $g\in C$ has the same trace $\chi_\pi(g)=\chi_\pi(C)$, we find
$$  |C|\,\chi_\pi(C)\=\sum_{g\in C}\chi_\pi(g)\=\text{tr}(\pi(e_C),V)
  \=\text{tr}(\nu_\pi(C)\cdot\text{Id},V)\= \nu_\pi(C)\,\dim\pi$$
and hence
$$ \nu_\pi(C)\=\frac{|C|}{\dim\pi}\,\chi_\pi(C)\=\frac{\chi_\pi(C)}{\chi_\pi(1)}\,|C|\,.\tag9$$
Now we compute the trace of the action by left multiplication of the product of the elements
$e_{C_1},\ldots,e_{C_k}$ on both sides of (4).  On the one hand, this product is the sum of
the elements $[c_1\cdots c_k]$ with $c_i\in C_i$ for all $i$, and since the trace of left multiplication
by $[g]$ on $\C[G]$ is clearly $|G|$ for $g=1$ and 0 otherwise, the trace equals $|G|\N(G;C_1,\ldots,C_k)$.  
On the other hand, the product of the $e_{C_i}$ acts as scalar multiplication by $\prod\nu_\pi(C_i)$
on $\pi$ and hence also on the $(\dim\pi)^2$-dimensional space $\End_\C(\pi)$.  
Formula (8) follows immediately. \endpf

Theorem 2 has a clear topological interpretation.  Let $X$ be the 2-sphere
with $k$ (numbered) points $P_1,\ldots,P_k$ removed.  Then $\pi_1(X)$ is
a (free) group on $k$ generators $x_1,\ldots,x_k$ with $x_1\cdots x_k=1$,
and $\N(G;C_1,\ldots,C_k)$ simply counts the number of homomorphisms $\rho$
from $\pi_1(X)$ to $G$ with $\rho(x_i)\in C_i$ for each $i$.  As explained
in the text of the book, if $G$ acts faithfully on some finite set $F$, then
each such homomorphism corresponds to a (not necessarily connected) Galois covering
of $X$ with fibre $F$, Galois group~$G$, and ramification points $P_i$, 
such that for each $i$ the permutation of the elements of a fixed fibre induced
by the local monodromy at $P_i$ belongs to the conjugacy class $C_i$.
Hence $\N(G;C_1,\dots,C_k)$ counts the coverings with these properties. Observe
that the above-mentioned invariance of $\N(G;C_1,\dots,C_k)$ under permutation of its
arguments is clear from this topological point of view.

A natural idea is now to generalize this to ramified coverings of
Riemann surfaces of arbitrary genus $g\ge0$. In view of the structure of
the fundamental group of a $k$-fold punctured surface of genus~$g$, this
boils down to computing the number
$$ \align \N_g(G;C_1,\dots,C_k)&\=\#\bigl\{(a_1,\dots,a_g,b_1,\dots,b_g,c_1,\dots,c_k)\in
G^{2g}\times C_1\times\dots\times C_k\mid \\
  &\qquad\qquad [a_1,b_1]\cdots[a_g,b_g]\,c_1\cdots c_k\,=\,1\}\,.\endalign$$
The result, given in the theorem below, turns out to be surprisingly simple, but was apparently not
given in the classical group-theoretical literature and was discovered first in the context of mathematical
physics ([DW], [FQ]).  The proof is an almost immediate consequence of the special case $g=0$.

\proclaim{Theorem 3} With the same notations as above, we have for all $g\ge0$
$$\N_g(G;C_1,\dots,C_k) \= |G|^{2g-1}\,|C_1|\cdots|C_k|\,
  \sum_\chi \frac{\chi(C_1)\cdots\chi(C_k)}{\chi(1)^{k+2g-2}}\,.\tag10$$
\endproclaim
\demo{Proof} Note that $[a_1,b_1]\cdots[a_g,b_g]=a_1(b_1a_1b_1\i)\i\cdots a_g\,(b_g a_gb_g\i)\i$ and that,
for $a$ and $a'$ in the same conjugacy class $A$, there are $|G|/|A|$ elements $b\in G$ with $bab\i=a'$. Hence
$$ \N_g(G;C_1,\dots,C_k)\= \sum_{A_1,\dots, A_g\in\c}\frac{|G|}{| A_1|}\cdots\frac{|G|}{| A_g|}\, 
\N(G;A_1, A_1\i,\dots,A_g,A_g\i,C_1,\dots,C_k)\,.$$
Now applying Theorem~2 we find 
$$\align \N_g(G;C_1,\dots,C_k)&\= |G|^{g-1} |C_1|\cdots|C_k| \times \\
   &\qquad\sum_{ A_1,\dots, A_g\in \c}| A_1|\cdots| A_g| 
  \sum_\chi\frac{\chi(A_1)\overline{\chi(A_1)}\cdots\chi(A_g)\overline{\chi(A_g)}\chi(C_1)\cdots\chi(C_k)}
  {\chi(1)^{k+2g-2}}\\
 &\= |G|^{g-1} |C_1|\cdots|C_k| \sum_\chi\frac{\chi(C_1)\cdots\chi(C_k)}{\chi(1)^{k+2g-2}}\,
   \biggl(\sum_{A\in\c}|A|\,\chi(A)\,\overline{\chi(A)}\biggr)^g\,. \endalign $$
The theorem now follows from the case $\pi=\pi'$ of the orthogonality relation~(5). \endpf

We observe that, by formula (9), both Frobenius's formula and its higher genus generalization 
can be written more naturally in terms of the eigenvalues $\nu_\pi(C)$ than the character values $\chi_\pi(C)$.
In particular, equation (10) when expressed in terms of the $\nu_\pi(C)$ takes the simple form
$$\N_g(G;C_1,\dots,C_k)= |G|^{2g-1}\,\sum_{\pi\in\r}\frac{\nu_\pi(C_1)\cdots\nu_\pi(C_k)}{(\dim\pi)^{2g-2}}\,.\tag11$$

\newpage
\heading 2. Applications \endheading
In this section we give several applications of the character theory of finite groups in the
case when $G=\s_n$, the symmetric group on $n$ letters.  In this case the conjugacy classes are
described simply by the partitions of $n$, the conjugacy class of an element $g\in\s_n$ with 
$d_1$ one-cycles, $d_2$ two-cycles, etc., corresponding to the partition $\l=1^{d_1}2^{d_2}\cdots$ of $n$.
It turns out that much of the part of the information which we are interested in can be captured by
any of three polynomials $\P_g(X)$, $P_g(r)$ or $Q_g(k)$ which mutually determine each other but which
encode the interesting combinatorial information about $g$ in different ways. 

\subheading{2.1. Representations of $\s_n$ and canonical polynomials associated to partitions}
%
% We associate to each conjugacy class $C$ of $\s_n$ or partition $\l$ of $n$ 
% three polynomials $P_C$, $\P_C$ and $Q_C$ (or $P_\l$,\dots) which are related to each other 
% by canonical, $\Z/2\Z$-equivariant isomorphisms of three canonical $n$-dimensional spaces of polynomials.
%
In this subsection we define the three polynomials  $\P_g(X)$, $P_g(r)$ or $Q_g(k)$ mentioned above
and prove their main properties.  Applications to several of the topics treated in the main text of
the book will then be given in 2.2--2.4.  Since each of these three polynomials depends
only on the conjugacy class $C$ of $g\in \s_n$ or equivalently only on the partition $\l\vdash n$
corresponding to $C$, we will also use the notations  $\P_C(X)$, $P_C(r)$ or $Q_C(k)$ and
 $\P_\l(X)$, $P_\l(r)$ or $Q_\l(k)$. 

We recall from \S1.2 the standard irreducible representation $\St_n=\C^n/\C$ of $\s_n$ of dimension $n-1$.
We define $\P_g(X)$ as the characteristic polynomial of $g$ on $\St_n$:
$$ \P_g(X) \= \det\bigl(1\,-\,g\,X,\,\St_n)\,.\tag 12$$
It is easy to see that, if $g$ has the cycle structure $1^{d_1}2^{d_2}\cdots$, then the characteristic
polynomial of $g$ on $\C^n=\St_n\oplus\1$ is simply $\prod(1-X^i)^{d_i}$, so in terms of $\l$ we have
$$ \P_\l(X) \= \frac{(1-X)^{d_1}(1-X^2)^{d_2}\cdots}{1\,-\,X}\qquad\qquad(\l=1^{d_1}2^{d_2}\cdots)\,.\tag 13$$
This is the first of our three polynomials.

From linear algebra, we know that the coefficient of $X^r$ in the characteristic polynomial of any
endomorphism $\phi$ of a finite-dimensional vector space $V$ equals $(-1)^r$ times the trace of the
endomorphism induced by $\phi$ on the $r$th exterior power $\bigwedge^r(V)$.  We therefore have
$$ \P_g(X) \= \sum_{r=0}^{n-1}(-1)^r\,\chi_r(g)\,X^r\,,\tag 14$$
where we have abbreviated 
$$ \chi_r(g)\,:=\,\text{tr}(g,\,\pi_r)\,,\qquad \pi_r\,:=\,\tsize\bigwedge^r(\St_n)\qquad\qquad(0\le r\le n-1)\,.$$
We shall show below that the representations $\pi_r$ are irreducible and distinct, so the $\chi_r$ are
distinct characters of $\s_n$. We have $\chi_r(1)=\dim\pi_r=\binom{n-1}r$.  Now,
since there is a unique polynomial of degree $n-1$ having specified values at
any $n$ specified points, we can define a polynomial $P_g(r)$ by the requirements that $\,\deg P_g\le n-1$ and that
$$ P_g(r)\=\frac{\chi_r(g)}{\chi_r(1)}\={\tsize\binom{n-1}r}\i\chi_r(g)\qquad(0\le r\le n-1)\,.\tag 15$$
This is our second polynomial attached to (the conjugacy class of) $g$.

Finally, we recall the notations $\ell(g)=\sum d_i$ and $v(g)=\sum(i-1)d_i$ for the number of cycles of
an element $g$ of $\s_n$ and for its complement $v(g)=n-\ell(g)$.  (Again, since both depend only on the
conjugacy class of $g$, we will use the alternative notations $\ell(C)$, $v(C)$ or $\ell(\l)$, $v(\l)$ as
the situation requires.)  Let $\sigma$ denote the cyclic element $(1\,2\,\dots\,n)$ of $\s_n$.  We then define 
$$ Q_C(k)\=\frac1{|C|}\,\sum_{g\in C}\,k^{\ell(g\sigma)}\tag 16$$
for any conjugacy class $C$ of $\s_n$.  This is our third polynomial.

\newpage
Before stating the main result, which describes how each of the three polynomials just defined determines
the other two, we need two simple (and well-known) lemmas concerning the representations $\pi_r$.
\proclaim{Lemma 4} The representations $\pi_r=\bigwedge^r(\St_n)$ $(0\le r\le n-1)$ of $\s_n$ are irreducible
and distinct.\endproclaim
\demo{Proof} Set $V=\pi_0\oplus\cdots\oplus\pi_{n-1}$, a representation of $G=\s_n$ of dimension
$2^{n-1}$. By the results of \S1, we know that $V$ can be decomposed uniquely as $\oplus_{\pi\in\r}m(\pi)\,\pi$,
where $\r$ is a set of representatives of the isomorphism classes of irreducible representations of $G$
and the multiplicities $m(\pi)$ are non-negative integers. Since $V$ is by construction a sum of $n$ non-trivial 
representations, we have $\sum m(\pi)\ge n$.  Define $\chi_V:\s_n\to\C$ by $\chi_V(g)=\text{tr}(g,V)$. 
Then $\chi_V$ decomposes as $\chi_V=\sum m(\pi)\chi_\pi$. We define a scalar product on the vector space of
conjugacy-invariant functions $f:\s_n\to\C$ by $(f_1,f_2)=|G|\i\sum_{g\in G}f_1(g)\overline{f_2(g)}\,$.  By equation~(1)
(first orthogonality relation) we know that the characters $\chi_\pi$ of the irreducible representations
of $G$ form an orthogonal basis for this vector space with respect to this scalar product, so $(\chi_V,\chi_V)
=\sum m(\pi)^2$.  If we can show that $(\chi_V,\chi_V)=n$, it will follow that $\sum(m(\pi)^2-m(\pi))\le 0$
and hence that each multiplicity $m(\pi)$ equals~0 or~1, with $m(\pi)=1$ for exactly $n$ distinct irreducible
representations of $G$, proving the lemma.

To calculate $(\chi_V,\chi_V)$, we first use equations~(14) and~(13) to obtain that
$$\chi_V(g)\=\sum_{r=0}^{n-1}\chi_r(g)\=\P_g(-1)\=\cases 2^{(d_1+d_3+\cdots)-1}&\text{if $d_2=d_4=\dots=0$},\\
0&\text{otherwise}\endcases$$
for $g$ with the cycle structure $\prod i^{d_i}$.  Since the number of elements with this cycle structure
is $n!/\prod\bigl(d_i!\,i^{d_i})$, we obtain
$$\align (\chi_V,\,\chi_V)&\=\frac1{n!}\,\sum_{g\in \s_n}|\chi_V(g)|^2
\=\frac14\sum\Sb d_1,\,d_3,\,d_5,\dots\ge0\\ d_1+3d_3+5d_5+\cdots=n\endSb
\frac{4^{d_1+d_3+d_5+\cdots}}{d_1!\,d_3!\,d_5!\,\cdots\,1^{d_1}\,3^{d_3}\,5^{d_5}\,\cdots} \\
&\= \frac14\cdot\text{coefficient of $x^n$ in }\prod\Sb i\ge1\\ \text{$i$ odd}\endSb 
 e^{4x^i/i}\quad=\quad n\,,\endalign $$
since $4\sum\limits_{\text{$i$ odd}}\dfrac{x^i}i=2\,\log\dfrac{1+x}{1-x}$ 
and $\bigl(\dfrac{1+x}{1-x}\bigr)^2=1+4\sum\limits_{n\ge1}nx^n$. \endpf

\proclaim{Lemma 5} The value of the character of an irreducible representation $\pi$ of $\s_n$ on the
conjugacy class of the cyclic element $\sigma\in \s_n$ is given by
$$ \chi_\pi(\sigma)\=\cases(-1)^r&\text{if $\pi\simeq\pi_r$ for some $r$, $0\le r\le n-1$,}
  \\ \quad0 &\text{otherwise.}\endcases $$ \endproclaim
\demo{Proof} The first statement follows immediately from formulas (14) and (13), since
$$\sum_{r=0}^{n-1}(-1)^r\,\chi_r(\sigma)\,X^r\=\P_\sigma(X)\=\frac{1-X^n}{1-X}\=\sum_{r=0}^{n-1}X^r\,.$$
The second then follows immediately from the second orthogonality relation for characters, since
$\sum_{\pi\in\r}|\chi_\pi(\sigma)|^2=n!/(n-1)!=n=\sum_{r=0}^{n-1}|\chi_r(\sigma)|^2\,$. \endpf

\newpage
\proclaim{Theorem 4} For any integer $n\ge1$ there are canonical linear isomorphisms between the three
$n$-dimensional vector spaces
$$\langle 1,\,X,\ldots,\,X^{n-1}\rangle\,,\qquad\langle1,\,r,\ldots,\,r^{n-1}\rangle\,,
 \qquad\langle k,\,k^2,\ldots,\,k^n\rangle\,,$$
such that the three polynomials $\P_C(X)$, $P_C(r)$ and $Q_C(k)$ correspond to one another for every conjugacy
class $C$ in $\s_n$. These isomorphisms are given by $\P\leftrightarrow P\leftrightarrow Q$, where
$\P(X)$, $P(r)$ and $Q(k)$ are related by the generating function identities
$$ \P(X)\=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}rP(r)X^r\=(1-X)^{n+1}\,\sum_{k=1}^\infty Q(k)\,X^{k-1}\,,\tag 17$$
or alternatively in terms of bases of the three vector spaces by      \def\sp{\quad\leftrightarrow\quad}
$$ (1-X)^{n-1-s}\sp\binom{n-1-r}s\big/\binom{n-1}s\sp\binom{s+k}{s+1}\qquad(0\le s\le n-1)\tag 18$$  
or
$$ X^s(1-X)^{n-1-s}\sp(-1)^s\binom rs\big/\binom{n-1}s\sp\binom k{s+1}\qquad(0\le s\le n-1)\,.\tag 19$$  
These isomorphisms are equivariant with respect to the three involutions $*$ defined by
$$\P^*(X)=(-X)^{n-1}\P(1/X),\qquad P^*(r)=P(n-1-r),\qquad Q^*(k)=-Q(-k)\,,\tag 20$$
under which the polynomials $\P_C(X)$, $P_C(r)$ and $Q_C(k)$ are invariant or anti-invariant 
according to whether $C$ is a conjugacy class of even or odd permutations. \endproclaim
\demo{Proof} The fact that the formulas (17) give isomorphisms between the spaces in question
can be checked either directly or by using the binomial theorem to check that the collections of
functions listed in (18) or in (19), each of which forms a basis for the relevant vector space,
satisfy the identities in (17).  The equivariance of the isomorphisms with respect to the involutions (20)
follows most easily by noting that these involutions exchange the bases given in (18) and (19) up to a factor
$(-1)^s$.  The fact that $\P_g(X)$ and $P_g(r)$ are related by the first formula in~(17) follows immediately
from equations (13) and (14) above.  The statement about the invariance or anti-invariance of $\P_g$, $P_g$
and $Q_g$ under the involutions $*$ is easy in each case (although of course it would suffice to verify only
one of them and then use the rest of the theorem): for $\P_g$ it follows immediately from formula~(13)
and the fact that $\,\text{sgn}(g)=(-1)^{v(g)}$ with $v(g)=\sum(i-1)d_i\,$; for $P_g$ it follows from~(15)
and the fact that $\wedge^{n-1-r}(\St_n)$ is dual to the tensor product of $\wedge^r(\St_n)$ with the
sign representation $\e_n$ (because $\wedge^{d-r}V\otimes\wedge^r(V)\overset\wedge\to\to\wedge^d(V)$ is a perfect
pairing for any $d$-dimensional vector space $V$ and $\wedge^{n-1}(\St_n)=\e_n$); and for $Q_g$ it follows
from the fact that $\ell(g\sigma)=n-v(g\sigma)\equiv v(g)+1\pmod2$ for any $g\in \s_n$.  The only thing we have to
show is therefore that the polynomials $\P_C(X)$ and $Q_C(k)$ are related by the generating series identity
$$ \sum_{k=1}^\infty Q_C(k)\,X^{k-1}\=\frac{\P_C(X)}{(1-X)^{n+1}}\,\,,\tag 21$$
for any conjugacy class $C$ in $\s_n$.  For this we use the following lemma.
\enddemo
\proclaim{Lemma 6} For any integers $n$, $r$ and $k$ with $0\le r\le n-1$ we have
$$\frac1{n!}\,\sum_{g\in \s_n}\,P_g(r)\,k^{\ell(g)}\=\,\text{\rm coefficient of $X^{k-1}$ in }\;
\frac{X^r}{(1-X)^{n+1}}\,.$$  \endproclaim
\demo{Proof} By a calculation similar to the one in the proof of Lemma~4, we have 
$$\align \frac1{n!}\,\sum_{g\in \s_n}\Phi_g(Y)\,k^{\ell(g)}
&\=\sum\Sb d_1,\,d_2,\,\dots\\ d_1+2d_2+\cdots=n\endSb
 \frac{k^{d_1+d_2+\cdots}}{d_1!\,d_2!\,\cdots\,1^{d_1}\,2^{d_2}\,\cdots}\cdot\frac{(1-Y)^{d_1}(1-Y^2)^{d_2}\cdots}{1-Y}\\
&\=\frac1{1-Y}\cdot\text{coefficient of $u^n$ in }\;\prod_{i=1}^\infty \exp\biggl(\frac{k(1-Y^i)u^i}i\biggr)\\
&\=\frac1{1-Y}\cdot\text{coefficient of $u^n$ in }\;\biggl(\frac{1-uY}{1-u}\biggr)^k\\
&\=\,\text{\rm coefficient of $X^{k-1}$ in }\;\,\frac{(1-XY)^{n-1}}{(1-X)^{n+1}}\,,\tag 22\endalign $$
where the last equality follows either by using residue calculus to get
$$ \align \frac1{1-Y}\,\text{Res}_{u=0}\biggl(\biggl(\frac{1-uY}{1-u}\biggr)^k\,\frac{du}{u^{n+1}}\biggr)
&\=-\,\text{Res}_{X=1}\biggl( \frac{(1-XY)^{n-1}}{(1-X)^{n+1}}\,\frac{dX}{X^k}\bigg)
     \qquad\bigl(u=\frac{1-X}{1-XY}\bigl) \\
 &\=+\,\text{Res}_{X=0}\biggl( \frac{(1-XY)^{n-1}}{(1-X)^{n+1}}\,\frac{dX}{X^k}\biggr)\endalign$$ 
or else from the geometric series identity
$$\sum_{k=1}^\infty\,X^{k-1}\,\biggl(\frac{1-uY}{1-u}\biggr)^k\=\frac{1-uY}{1-u-X+uXY}
\=\frac1{1-X}\+(1-Y)\,\sum_{n=1}^\infty\frac{(1-XY)^{n-1}}{(1-X)^{n+1}}\,u^n\,.$$
The lemma follows by comparing the coefficients of $(-1)^r\binom{n-1}rY^r$ on both sides of (22).\endpf
\subheading{Remark} Lemma 6 implies that
$$\frac1{n!}\,\sum_{g\in \s_n}\,P_g(r)\,k^{\ell(g)}\=\binom{k+n-r-1}n\,-\,\,\binom{n-r-1}n$$ 
as polynomials in $r$ and $n$, since both sides of this identity are polynomials in $k$ and $r$,
both have degree $\le n-1$ in $r$, and they agree for $k\in\n$ and for $r=0,\,1,\dots,n-1$.

\smallskip
We can now complete the proof of equation~(21) and hence of Theorem~4.  Frobenius's formula
(Theorem~2) in the case $k=3$ can be rewritten in the form
$$\frac1{|C|}\sum_{c\in C}F(bc)\=\sum_\pi\chi_\pi(b)\chi_\pi(C)\,
 \biggl(\frac1{|G|}\,\sum_{A\in\c}|A|\,\frac{\chi_\pi(A)}{\chi_\pi(1)}\,F\bigl(A^{-1}\bigr)\biggr) $$
for any finite group $G$, conjugacy classes $A$ and $C$ of $G$, and class function (= conjugacy-invariant
function) $F:G\to\C$, where the sum is over all irreducible representations of $G$.  Specializing to $G=\s_n$
and $b=\sigma$ and using Lemma 5, we find
$$\frac1{|C|}\sum_{c\in C}F(\sigma c)\=\sum_{r=0}^{n-1}(-1)^r\chi_r(C)\,
 \biggl(\frac1{n!}\,\sum_{g\in G}P_g(r)\,F\bigl(g^{-1}\bigr)\biggr)\,. $$
Now specializing further to $F(g)=k^{\ell(g)}$ and using Lemma 6 and equation (14) gives
$$ Q_C(k)\=\,\text{\rm coefficient of $X^{k-1}$ in }\;
\frac{\P_C(X)}{(1-X)^{n+1}}\,.\qquad\quad\square$$ 

We mention two simple consequences of Theorem~4 which will be used later.
\proclaim{Corollary 1} Let $\l=1^{d_1}2^{d_2}\cdots$ be a partition of $n$.  Then the polynomial
$P_\l(r)$ has degree $v(\l)=\sum(i-1)d_i$ and leading coefficient $(-1)^{v(\l)}K(\l)$, where
$$K(\l)\=\frac{(n-1-v(\l))!}{(n-1)!}\,1^{d_1}2^{d_2}\cdots n^{d_n}\,.\tag 23$$
The polynomial $Q_\l(k)$ has degree $v(\l)+1$ and leading coefficient $\bigl(\prod i^{d_i}\bigr)/(v(\l)+1)!\,$.
\endproclaim 
\demo{Proof} From equation (13) we see that $\P_\l(X)\sim\frac{(n-1)!}{(n-1-v(\l))!}\,K(\l)\,(1-X)^{n-1-v(\l)}$
as $X\to1$.  But this means that $\P_\l(X)$ is a linear combination of the basis elements~(18) with $s\le v(\l)$,
with the coefficient for $s=v(\l)$ being $\frac{(n-1)!}{(n-1-v(\l))!}\,K(\l)$.  The correspondence~(18) then
tells us that $P_\l$ and $Q_\l$ have the degrees and leading coefficients stated. \endpf
\proclaim{Corollary 2} The polynomial $Q_\l(k)$ takes integer values for $k\in\Z$.  Moreover, the
value of $Q_\l(k)$ for $k\in\n$ depends only on the numbers $n-d_1,\,d_2,\dots,d_{k-1}$, the first few being
$$ Q_\l(0)=0,\quad Q_\l(1)=1,\quad Q_\l(2)=n+2-d_1,\quad Q_\l(3)=\binom{n+3-d_1}2-d_2\,. $$
\endproclaim
\demo{Proof} Equations (21) and (13) give
$$\quad Q_C(k)\=\,\text{\rm coefficient of $X^{k-1}$ in }\;
(1-X)^{d_1-n-2}(1-X^2)^{d_2}(1-X^3)^{d_3}\cdots(1-X^{k-1})^{d_{k-1}}\,.\qquad\square$$ 
\enddemo
\subheading{Remark} The fact that $\,\deg Q_\l\le v(\l)$ says that $\ell(g\sigma)\le v(g)$ for all $g\in \s_n$.
Equivalently, $v(g)+v(g\sigma)\ge n-1=v(\sigma)$.  This is a special case of the general fact that $v(g_1)
+v(g_2)\ge v(g_3)$ for any three elements $g_1,\,g_2,\,g_3\in \s_n$ with product~1, which
can be seen most easily by noticing that $v(g_i)$ is the codimension of the fixed point set of $g_i$ acting
on $\C^n$ (or on its irreducible subspace $\St_n$) and that codimensions of subspaces behave subadditively.
The statement that the polynomial $Q_\l(k)$ depends only on $n-d_1$ and the $d_i$ with $i\ge2$ says that
it is stable under the inclusions $\s_n\subset \s_{n+1}$ and hence depends only on the class of $g$ in $\s_\infty$. 
This is not difficult to see directly from the definition, but there does not seem to be any obvious reason why
the value of $Q_\l(k)$ for $k\in\n$ depends only on the $d_i$ with $i<k$ or why it is an integer.

\bigskip
\subheading{2.2\. Examples} We give a number of examples of the polynomials introduced in \S2.1
for special conjugacy classes and for small values of $n$.

\subheading{Trivial element: $g=1$}  Here the cycle structure is simply $1^n$, so equation~(13)
gives $\P_1(X)=(1-X)^{n-1}$, while from equations~(4) and~(5) we immediately get $P_1(r)=1$
and $Q_1(k)=k$.

\subheading{Transposition: $T=(12)$} Now the cycle structure is $1^{n-2}2$, so equation~(13) gives 
$$\P_T(X)\=(1-X)^{n-3}(1-X^2)\= (1-X)^{n-2}(1+X)\,.\tag 24$$
From equation~(14) we therefore obtain
$$\chi_r(T)\=\binom{n-2}r-\binom{n-2}{r-1}\=\binom{n-3}r-\binom{n-3}{r-2}$$
(with the obvious conventions when $r<2$), so from (15) and the formula $\chi_r(1)=\binom{n-1}r$ we obtain
$$ P_T(r)\=1\,-\,\frac{2r}{n-1}\,\tag 25$$
while equation (17) or (18) or (19) gives
$$ Q_T(k)\= k^2\,.$$
Note that this last formula, unlike the formulas for $\P_T(X)$ and $P_T(r)$, is independent of $n$. This
is a special case of the above-mentioned fact that $Q_g(k)$ is stable under $\s_n\subset \s_{n+1}\,$.

\subheading{Cyclic permutation: $\sigma=(12\cdots n)$} Here the cycle structure is simply $n^1$,
so, as we have already seen, $\P_\sigma(X)=1+X+\cdots+X^{n-1}$ and $\chi_r(\sigma)=(-1)^r$.
However, the explicit forms of the polynomials $P_\sigma$ and $Q_\sigma$ are quite complicated, as can
be seen from the examples for $n=5$ and 6 below.

\subheading{Free involution: $\tau=(12)(34)\cdots(n-1\,n)$} 
Here $n$ must be even, say $n=2m$. The cycle structure of the conjugacy class of $\tau$ is $2^m$, so~(13) gives
$$ \Phi_\tau(X)\=\frac{(1-X^2)^m}{1-X}\=(1+X)(1-X^2)^{m-1}\tag 26$$
and hence
$$ \chi_r(\tau)\=(-1)^{[(r+1)/2]}\,\binom{m-1}{[r/2]}\,,$$
but here again the polynomials $P_\tau$ and $Q_\tau$ have no simple closed form.

\subheading{Small $n$} Finally, to give the reader a better feel for the 
$\Phi_\l\leftrightarrow P_\l\leftrightarrow Q_\l$ correspondence, we give a complete table of these 
three polynomials for partitions of $n$ with $1\le n\le 6$.  For convenience we tabulate the polynomial
$\wP_\l(t):=P\bigl(\frac{n-1}2-t\bigr)$ instead of $P_\l(r)$, since by the last statement of Theorem~4
this is an even or an odd polynomial in $t$ for all $\l$.  The stability of $Q_\l$ mentioned in the remark at
the end of the last section is visible in this table: for example, the first seven entries in the column giving $Q_\l(k)$
for $n=6$ agree with the values for $n=5$.

$$
\eightpoint
\boxed{\smallmatrix\format\c&\,\r\;&\ \c\;&\ \c\;\;&\ \c\\
n&\lambda&\wP_\lambda(t)& Q_\lambda(k)&\Phi_\lambda(X)\\
\hdotsfor5\\
1&1^1&1&k&1\\
\hdotsfor5\\
2&1^2&1&k&1-X\\
 &2^1&2t&k^2&1+X\\
\hdotsfor5\\
3&1^3&1&k&1-2X+X^2\\
 &1^12^1&t&k^2&1\phantom{-2X1}-X^2\\
 &3^1&\frac12(3t^2-1)&\frac12(k^3+k)&1+\phantom{2}X+X^2\\
\hdotsfor5\\
4&1^4&1&k&1-3X+3X^2-X^3\\
 &1^22^1&\frac23t&k^2&1-\phantom{3}X-\phantom{3}X^2+X^3\\
 &1^13^1&\frac18(4t^2-1)&\frac12(k^3+k)&1\phantom{-3X+3X^21}-X^3\\
 &2^2&\frac16(4t^2-3)&\frac13(2k^3+k)&1+\phantom{3}X-\phantom{3}X^2-X^3\\
 &4^1&\frac16(4t^3-5t)&\frac16(k^4+5k^2)&1+\phantom{3}X+\phantom{3}X^2+X^3\\
\hdotsfor5\\
5&1^5&1&k&1-4X+6X^2-4X^3+X^4\\
 &1^32^1&\frac12t&k^2&1-2X\phantom{+6X^21}+2X^3-X^4\\
 &1^23^1&\frac14t^2&\frac12(k^3+k)&
1-\phantom{2}X\phantom{+6X^21}-\phantom{2}X^3+X^4\\
 &1^12^2&\frac13(t^2-1)&\frac13(2k^3+k)&
1\phantom{+4X1}-2X^2\phantom{+4X^31}+X^4\\
 &1^14^1&\frac16(t^3-t)&\frac16(k^4+5k^2)&1\phantom{-4X+6X^2-4X^31}-X^4\\
 &2^13^1&\frac14(t^3-2t)&\frac14(k^4+3k^2)&
1+\phantom{4}X\phantom{+6X^21}-\phantom{4}X^3-X^4\\
 &5^1&\frac1{24}(5t^4-15t^2+4)&\frac1{24}(k^5+15k^3+8k)
 &1+\phantom{4}X+\phantom{6}X^2+\phantom{4}X^3+X^4\\
\hdotsfor5\\
6&1^6&1&k&1-5X+10X^2-10X^3+5X^4-X^5\\
 &1^42^1&\frac25t&k^2&1-3X+\phantom{2}2X^2+\phantom{2}2X^3-3X^4+X^5\\
 &1^33^1&\frac1{80}(12t^2+5)&
\frac12(k^3+k)&1-2X+\phantom{10}X^2-\phantom{10}X^3+2X^4-X^5\\
 &1^22^2&\frac1{20}(4t^2-5)&\frac13(2k^3+k)&
1-\phantom{2}X-\phantom{2}2X^2+\phantom{2}2X^3+\phantom{2}X^4-X^5\\
 &1^24^1&\frac1{60}(4t^3-t)&\frac16(k^4+5k^2)&
1-\phantom{2}X\phantom{+10X^2+10X^31}-\phantom{2}X^4+X^5\\
 &1^12^13^1&\frac1{90}(4t^3-9t)&\frac14(k^4+3k^2)&
1\phantom{-2X1}-\phantom{10}X^2-\phantom{10}X^3\phantom{-2X^41}+X^5\\
 &1^15^1&\frac1{384}(16t^4-40t^2+9)&\frac1{24}(k^5+15k^3+8k)&
1\phantom{+5X+10X^2+10X^3+5X^41}-X^5\\
 &2^3&\frac1{30}(4t^3-13t)&\frac13(k^4+2k^2)&
1+\phantom{2}X-\phantom{2}2X^2-\phantom{2}2X^3+\phantom{2}X^4+X^5\\
 &2^14^1&\frac1{240}(16t^4-64t^2+15)&\frac1{15}(k^5+10k^3+4k)&
1+\phantom{2}X\phantom{+10X^2+10X^31}-\phantom{2}X^4-X^5\\
 &3^2&\frac1{640}(48t^4-216t^2+115)&\frac1{40}(3k^5+25k^3+12k)&
1+\phantom{2}X+\phantom{10}X^2-\phantom{10}X^3-\phantom{2}X^4-X^5\\
 &6^1&\frac1{960}(48t^5-280t^3+259t)&\frac1{120}(k^6+35k^4+84k^2)
 &1+\phantom{2}X+\phantom{10}X^2+\phantom{10}X^3+\phantom{2}X^4+X^5
\endsmallmatrix}
$$
% \bigskip


\medskip
\subheading{2.3. First Application: Enumeration of polygon gluings}  This is the combinatorial 
question which was discussed in Chapter~3 in connection with the evaluation of the (orbifold)
Euler characteristic of the moduli space of curves of genus~$g$.  The problem was to count
the number $\varepsilon_g(m)$ of ways to identify in pairs (with reverse orientation) the sides
of a $(2m)$-gon such that the closed oriented surface obtained has a given genus $g$.  Clearly
this is the same as the number of free involutions in $\s_{2m}$ whose product with the standard
cyclic permutation $\sigma$ has $m+1-2g$ cycles, so formula~(16) gives
$$ Q_\tau(k)\=\frac1{(2m-1)!!}\,\sum_{0\le g\le m/2}\varepsilon_g(m)\,k^{m+1-2g}\,,\tag 27$$
where $\tau$ denotes any free involution (and where we have used that the conjugacy class
of $\tau$ has cardinality $(2m-1)!!$). On the other hand, from equations (21) and (26) we get
$$ \sum_{k=1}^\infty Q_\tau(k)\,X^{k-1}\=\frac{\P_\tau(X)}{(1-X)^{2m+1}}
  \=\frac{(1+X)^m}{(1-X)^{m+2}}\,,$$
which we can rewrite equivalently by using the same calculation as in the last line of (22)
(with $n$ replaced by $m+1$ and $Y$ by $-1$) as
$$ Q_\tau(k)\=\,\frac12\cdot\text{coefficient of $u^{m+1}$ in $\biggl(\frac{1+u}{1-u}\biggr)^k$}\,.$$ 
Since the sum on the right-hand side of (27) is the polynomial denoted $T_m(k)$ in \S3.1, this reproduces the
evaluation of $\varepsilon_g(m)$ in terms of generating functions given in Theorem~3.1.5.

The proof just given follows the exposition in [Z], where the identity~(21) was proved and a few other
applications were given.  We mention two briefly:
\smallskip$\bullet\;$ the probability that the product of two random cyclic permutations in $\s_n$
has exactly $\ell$ cycles is $(1+(-1)^{n-\ell})$ times the coefficient of $x^\ell$ in $\binom{x+n}{n+1}$. In
particular, for $n$ odd the probability that such a product is cyclic equals $\frac2{n+1}$, as opposed to the probability
that a random even element of $\s_n$ is cyclic, which equals $\frac2n\,$. 
\smallskip$\bullet\;$ the number of representations of an arbitrary even element of $\s_n$ as a product
of two cyclic permutations is $\ge\frac{2(n-1)!}{n+2}$, as opposed to the average number of such representations
for even permutations, which equals $\frac{2(n-1)!}n\,$.

\medskip
\subheading{2.4. Second Application: The Goulden-Jackson formula} Our second application, again
reproducing a result proved by a different method within the main text of the book, is the formula
of Goulden-Jackson given in various forms in Theorems 1.5.12, 1.5.15, 1.6.6 and 5.2.2. The problem,
in our present language, is to count the ``Frobenius number" $\N(\s_n;C_0,C_1,\cdots,C_k)$ of $(k+1)$-tuples
$(c_0,\dots,c_k)\in C_0\times\cdots\times C_k$ when $C_0$ is the class of the cyclic element 
$\sigma\in \s_n$ and $C_1,\dots,C_k$ are arbitrary conjugacy classes in $\s_n$.  The Goulden-Jackson
formula says that this number is 0 if $v=v(C_1)+\cdots+v(C_k)$ is less than $n-1$ and gives an explicit
formula for it when $v(C_1)+\cdots+v(C_k)=n-1$.  We give a somewhat more general result.
\proclaim{Theorem 5} Let $C_1,\dots,C_k$ be arbitrary conjugacy classes in $\s_n$ and $C_0$ the
class of the cyclic element $\sigma$.  Then
$$ \N(\s_n;C_0,C_1,\dots,C_k)\=\frac{(-1)^{n-1}}n\,|C_1|\cdots|C_k|\cdot\Delta^{n-1}\bigl(P_{C_1}\cdots P_{C_k}\bigl)(0)\,,\tag 28$$
where $P_{C_i}(r)$ is the polynomial of degree $v(C_i)$ associated to the conjugacy class $C_i$ as in \S$2.1$
and $\Delta$ denotes the forward differencing operator $\Delta P(r)=P(r+1)-P(r)$.\endproclaim
For the conjugacy class $C$ of $S_n$ corresponding to a partition $\l=1^{d_1}\cdots n^{d_n}$ of $n$, let us write
$N(C)$ for the number $\,N(\l)=\frac{(d_1+\cdots+d_n-1)!}{d_1!\,\cdots\,d_n!}\,$ defined in 1.5.11. Then we have:
\proclaim{Corollary (Goulden-Jackson formula)} Let the $C_i$ be as in the theorem. Then the number 
$\N(\s_n;C_0,C_1,\dots,C_k)$ vanishes if the number $v:=v(C_1)+\cdots+v(C_k)$ is less than $n-1$ and is given by
$$ \frac1{(n-1)!}\,\N(\s_n;C_0,C_1,\dots,C_k)\=n^{k-1}\,N(C_1)\cdots N(C_k)\tag29$$
if $v=n-1$. \endproclaim
\demo{Proof} The theorem is an immediate consequence of Frobenius's formula (Theorem~2) and
Lemma~5, which says that $\chi(C_0)$ equals $(-1)^r$ if $\chi=\chi_r$ and vanishes for all other 
irreducible characters, together with definition~(15), which together give
$$ \N(\s_n;C_0,C_1,\dots,C_k)\=\frac1n\,|C_1|\cdots|C_k|\,
    \sum_{r=0}^{n-1}(-1)^r\,\binom{n-1}r\,P_{C_1}(r)\cdots P_{C_k}(r)\,.$$
The corollary follows immediately from the theorem together with Corollary~1 above and the formula
$|C_i|K(\l_i)=nN(\l_i)$ (compare equation~(23) and the definition of $N(\l)$), since the polynomial
$P_{C_1}(r)\cdots P_{C_k}(r)$ has degree $v$ and the $m$th difference of a polynomial of degree $v$
is 0 for $m>v$ and equal to $m!$ times the leading coefficient of the polynomial if $m=v$. \endpf

\subheading{Remarks. 1} The fact that $\N(\s_n;C_0,\,C_1,\dots,C_k)=0$ unless $v\ge n-1$ is also obvious from the
remark at the end of \S2.1, which says that the function $v$ satisfies the triangle inequality and
hence necessarily $v(c_1)+\cdots+v(c_k)\ge v(c_0)$ if $c_0c_1\cdots c_k=1$.  It also follows from the
topological interpretation of $\N(\s_n;C_0,\,C_1,\dots,C_k)$ as the counting function for ramified coverings
of $S^2$ with ramification types $C_i$, since $v-n-1$ equals the Euler characteristic of the total space
of the covering, which has the form $2-2g\le 2$ because a covering one of whose ramification types
is cyclic is necessarily connected.  This shows also that the number $\N(\s_n;C_0,\,C_1,\dots,C_k)$ vanishes
unless $v\equiv n-1\pmod2$. To see this from Theorem~5, it is convenient to rewrite formula (28) in the form
$$ \frac{n\,\N(\s_n;C_0,C_1,\dots,C_k)}{|C_1|\cdots|C_k|}\=\Delta_+^{n-1}\bigl(\wP_{C_1}\cdots\wP_{C_k}\bigl)(0)\,,\tag 30$$
where $\wP_C(t)=P_C\bigl(\frac{n-1}2-t\bigr)$ is the shifted version of $P_C(r)$ mentioned in \S2.2
and $\Delta_+$ is the symmetric difference operator $\Delta_+f(t) =f(t+\frac12)-f(t-\frac12)$. This
expression obviously vanishes if $v\not\equiv n-1\pmod2$ because of the symmetry property
$\wP_C(-t)=(-1)^{v(C)}\wP_C(t)$ and the fact that $\Delta_+$ reverses the parity of an even or odd function. 
\smallskip{\bf 2.} As a special case, we can take $C_1=\dots=C_k=[T]$, the class of transpositions in $\s_n$.
Then $\wP_{C_i}(t)=\frac{2t}{n-1}$ by formula (25), so equation (30) gives
$$ \N\bigl(\s_n;\,\sigma,\,\undersetbrace k\to{T,\dots,T}\bigr)\= n^{k-1}\,\Delta_+^{n-1}\bigl(t^k\bigr)\bigl|_{t=0}\;.$$
Using the identity
$$ \Delta_+^{n-1}\bigl(t^k\bigr)\bigl|_{t=0} \=\sum_{r=0}^{n-1}(-1)^r\binom{n-1}r\,\bigl(\frac{n-1}2-r\bigr)^k
\=\frac{d^k}{du^k}\bigl(e^{u/2}-e^{-u/2}\bigr)^{n-1}]\bigl|_{u=0}$$
and the residue theorem, we can write this equivalently as 
$$\N\bigl(G;\,\sigma,\,\undersetbrace k\to{T,\dots,T}\bigr)\=k!\cdot n^{k-1}\cdot S_g(n)\qquad\text{for $k=n-1+2g$}\qquad(g\ge0),\tag31$$
where $S_g(n)$ is the polynomial of degree $g$ in $n$ given by
$$\align S_g(n)&\=\text{coefficient of $u^{2g}$ in } \biggl(\frac{\sinh u/2}{u/2}\biggr)^{n-1} \\
&\=\frac{n-1}{n-1+2g}\cdot\text{coefficient of $s^{2g}$ in }\biggl(\frac{s/2}{\text{asinh }s/2}\biggr)^{n+2g-1}\,,\tag32\endalign$$
the first values of which are given by
$$ S_0(n)\=1, \quad S_1(n)\=\frac{n-1}{24}\,,\quad S_2(n)\=\frac{(n-1)(5n-7)}{5760}\,.\tag33$$
Formula (31) for $\N(\s_n;\sigma,T,\dots,T)$ was given in [SSV].
% &\=\quad 1,\quad\frac{n-1}{24}\,,\quad\frac{(n-1)(5n-7)}{5760}\,,\;\dots\qquad\text{ for $g=0$, 1, 2, \dots} \\ 
% &\=\cases 1&\text{if $g=0$},\\ \frac1{24}(n-1)&\text{if $g=1$},\\ \frac1{5760}(n-1)(5n-7)&\text{if $g=2$},\\   \cdots \endcases

\smallskip{\bf 3.} Another observation is that, from formula (10) together with the fact that $\chi(\sigma)=\chi(\sigma)^3$ 
% equals $(-1)^r$ for $\chi=\chi_r$ and 0 otherwise (Lemma~5),
for all irreducible characters $\chi$ of $\s_n$ (Lemma 5), we have the formula
$$\N_g(\s_n;\sigma,\,C_1,\dots,C_k)\=n^{2g}\,\N(\s_n;\undersetbrace{2g+1}\to{\sigma,\dots,\sigma},\,C_1,\dots,C_k) \tag34$$
for the ``generalized Frobenius number" of Theorem~3, for any integer $g\ge0$ and any conjugacy classes $C_1,\dots,C_k$
in $\s_n$.  This allows one to generalize Theorem~5 to the case of ramified coverings of a Riemann surface of arbitrary
genus with cyclic ramification at at least one point.  

In view of the very simple form of equation (34), it might be of interest to give a direct combinatorial or
topological proof, without using character theory.

\bigskip In the rest of this subsection, we show how one can use Theorem~5 to give explicit formulas for
$\N(\s_n;C_0,\,C_1,\dots,C_k)$ for arbitrary values of $v$.  The calculation and the results are considerably simplified
if we use the symmetric formula (30) instead of (28), but still rapidly become complicated as the number $2g=v-n+1$ grows.  

The main step in the calculation is a refinement of Corollary~1 of Theorem~4 giving more leading terms of $P_\l(r)$ (or
equivalently, of $\wP_\l(t)$) for an arbitrary conjugacy class $\l$ of $\s_n$. Write $\l=n_1+\cdots+n_s=1^{d_1}2^{d_2}\cdots\;$
and define invariants $\ell_h(\l)$ (higher moments) of $\l$ by
$$ \ell_h(\l)\=n_1^h+\cdots+n_s^h\=\sum_{i\ge1}i^h\,d_i\qquad\qquad(h=0,\,1,\,\dots), \tag 35$$
so that $\ell_0(\l)=\ell(\l)$, $\ell_1(\l)=n$.  Assign to $\ell_h(\l)$ the weight $h$.  Then we have:
\proclaim{Lemma 7} The polynomial $\wP_\l(t)=P_\l\bigl(\frac{n-1}2-t\bigr)$ has the form
$$ \wP_\l(t)\= K(\l)\,\biggl(1\+a_1(\l)\,t^{v(\l)-2}+a_2(\l)\,t^{v(\l)-4}\+\cdots\biggr)\,,$$
where $K(\l)$ is given by $(23)$ and each $a_j(\l)$ is a universal polynomial of weighted degree $\le 2j$
in $n$ and the invariants $\ell_h=\ell_h(\l)$ with $h$ even, the first two values being
$$\align a_1(\l)&\=(\ell_0+1)\ell_0\,\frac{\ell_2-1}{24}\,-\,\frac{(n-1)n(n+1)}{24}\,,\\
a_2(\l)&\=(\ell_0+3)(\ell_0+2)(\ell_0+1)\ell_0\,\frac{5(\ell_2-1)^2-2(\ell_4-1)}{5760} \\ &\qquad
  -\,\frac{(n-1)n(n+1)}{24}\,(\ell_0+1)\ell_0\,\frac{\ell_2-1}{24}\+\frac{(n-3)(n-2)(n-1)n(n+1)(5n+7)}{5760}\,.\endalign$$
\endproclaim 
\demo{Proof}  We already know that $\wP_\l(t)$ is a polynomial of degree and parity $v(\l)$ and hence has the form
$K(\l)\sum_ja_j(\l)t^{v(\l)-2j}$ for some numbers $a_j(\l)$.  Define a power series $\wF_\l(u)\in\Q[[u]]$ by
$\wF_\l(u)=e^{(n-1)u/2}\,\P_\l(e^{-u})$.  Then equations (14) and (15) give
$$\align \wF_\l(u)&\=\sum_{r=0}^{n-1}(-1)^r\,\binom{n-1}r\,\wP_\l\bigl(\frac{n-1}2-r\bigr)\;e^{(\frac{n-1}2-r)u} \\
&\=K(\l)\sum_{j\ge0} a_j(\l)\,\frac{d^{v(\l)-2j}}{du^{v(\l)-2j}}
 \biggl[\sum_{r=0}^{n-1}(-1)^r\,\binom{n-1}r\,e^{(\frac{n-1}2-r)u}\biggr]\\
&\=K(\l)\sum_{j\ge0} a_j(\l)\,\frac{d^{v(\l)-2j}}{du^{v(\l)-2j}}\biggl[\bigl(e^{u/2}-e^{-u/2}\bigr)^{n-1}\biggr] \\
&\=K(\l)\sum_{j\ge0} a_j(\l)\,\frac{d^{v(\l)-2j}}{du^{v(\l)-2j}}
  \biggl[\sum_{g\ge0}S_g(n)\,u^{n-1+2g}\biggr]\\
&\=(n-1)!\,K(\l)\sum_{j,\,g\ge0} a_j(\l)\,\wS_g(n)\,\frac{u^{n-v(\l)-1+2j+2g}}{(n-v(\l)-1+2j+2g)!} \,,\endalign$$
where $S_g(n)$ is as in (32) and 
$$\wS_g(n)\=\frac{(n-1+2g)!}{(n-1)!}\,S_g(n)\=\frac1{(n-1)!}\,\Delta_+^{n-1}\bigl(t^{n-1+2g}\bigr)\bigl|_{t=0}\,,\tag36$$
a polynomial of degree $3g$ in $n$. On the other hand,  from formula~(13) and the expansion
$$ e^{x/2}-e^{-x/2}\=x\,\exp\biggl(\sum_{h=2}^\infty \frac{B_h}h\,\frac{x^h}{h!}\biggr)
  \=x\,\exp\bigl(\frac{x^2}{24}-\frac{x^4}{2880}+\cdots\bigr)\,,$$
where $B_h$ denotes the $h$th Bernoulli number, we have
$$\align \wF_\l(u)&\=\prod_{i\ge1}\bigl(e^{iu/2}-e^{-iu/2}\bigr)^{d^*_i}\\
&\=\bigl(\prod_i i^{d_i}\bigr)\cdot u^{\ell(\l)-1}\cdot\exp\biggl(\sum_{h=2}^\infty
   \frac{B_h}h\,\ell^*_h(\l)\,\frac{x^h}{h!}\biggr)\\
&\=\frac{(n-1)!\,K(\l)}{(n-1-v(\l))!}\,u^{n-v(\l)-1}\,\biggl(1\,+\,\frac{\ell^*_2(\l)}{24}\,u^2
   \,+\,\frac{5\ell^*_2(\l)^2-2\ell^*_4(\l)}{5760}\,u^4\,+\,\cdots\biggr)\,,\endalign$$
where $d_i^*=d_i-\delta_{i,1}$ and $\ell^*_h(\l)=\sum_{i\ge1} i^hd_i^*=\ell_h(\l)-1$.
Comparing with the previous formula for $\wF_\l(u)$, we find  
$$\align a_0(\l) &\=1\,,\\
 a_1(\l)\,+\,\wS_1(n)&\=\frac{(n+1-v(\l))!}{(n-1-v(\l))!}\,\frac{\ell^*_2(\l)}{24}\,,\\
a_2(\l)\,+\,\wS_1(n)\,a_2(\l)\,+\,\wS_2(n)
  &\=\frac{(n+3-v(\l))!}{(n-1-v(\l))!}\,\frac{5\ell^*_2(\l)^2-2\ell^*_4(\l)}{5760}\,, \endalign$$
etc.  The lemma now follows by induction on $j$.  \endpf

\newpage
Returning to the situation of Theorem 5, we consider arbitrary conjugacy classes $C_i\leftrightarrow\l_i$
($i=1,\dots,k$) of $\s_n$. From Lemma~7 we get
% $$\prod_{i=1}^k\frac{\wP_{\l_i}(t)}{K(\l_i)}\=t^v\+\biggl(\sum_{1\le i\le k}a_2(\l_i)\biggr)t^{v-2}
% \+\biggl(\sum_{1\le i<j\le k}a_2(\l_i)a_2(\l_j)+ \sum_{1\le i\le k}a_4(\l_i)\biggr)t^{v-4}\+\cdots\,,$$
$$\prod_{i=1}^k\wP_{\l_i}(t)\=\biggl(\prod_{i=1}^kK(\l_i)\biggr)\,
  \biggl(t^v\+a_1(\l_1,\dots,\l_k)\,t^{v-2}\+a_2(\l_1,\dots,\l_k)\,t^{v-4}\+\cdots\biggr)$$
where $v=\sum v(\l_i)$ as before and
$$a_1(\l_1,\dots,\l_k)\=\sum_{1\le i\le k}a_1(\l_i)\,,\qquad
a_2(\l_1,\dots,\l_k)\=\sum_{1\le i<j\le k}a_1(\l_i)a_2(\l_j)+ \sum_{1\le i\le k}a_2(\l_i)\,,$$
etc. Substituting this into equation~(30) and recalling that $|C_i|K(C_i)=nN(C_i)$, we find
$$\align \frac1{(n-1)!}\,\frac{\N(\s_n;C_0,C_1,\dots,C_k)}{n^{k-1}\,N(\l_1)\cdots N(\l_k)}
&\=\frac1{(n-1)!}\,\Delta_+^{n-1}\bigl(\sum_{j\ge0} a_j(\l_1,\dots,\l_k)\,t^{v-2j}\bigr)\bigl|_{t=0} \\
&\=\sum_{j=0}^g \wS_{g-j}(n)\,a_j(\l_1,\dots,\l_k)\qquad\quad(v=n-1+2g),  \endalign $$
where the polynomials $\wS_{g-j}(n)$ are given by (36) and (32).  This is the desired generalization of the
Goulden-Jackson formula (29) to the case of ramified coverings of $S^2$ by surfaces of arbitrary genus $g$
with at least one cyclic ramification point.  We note the case $g=1$ separately since it is not too complicated:
\proclaim{Corollary} With the notations of Theorem~$5$ and its corollary, we have
$$ \frac1{(n-1)!}\,\frac{\N(\s_n;C_0,C_1,\dots,C_k)}{n^{k-1}\,N(C_1)\cdots N(C_k)}\=
 \sum_{i=1}^k\ell(C_i)\,(\ell(C_i)+1)\,\frac{\ell_2(C_i)-1}{24}\,-\,(k-1)\,\frac{n^3-n}{24}$$
if $v(C_1)+\cdots+v(C_k)=n+1$, where $\ell_2(C_i)$ denotes the sum of the squares of the lengths
of the cycles in the conjugacy class $C_i$. \endproclaim


\bigskip
\subheading{2.5. Third Application: ``Mirror symmetry in dimension one"}
``Mirror symmetry", originally discovered in the context of mathematical physics (string theory)
and intensively studied during recent years, is a predicted duality between certain families of Calabi-Yau
manifolds. It manifests itself on several levels, one of which has to do with the counting functions (Gromov-Witten
invariants) that enumerate the holomorphic mappings $\,C\to X$ of complex curves $C$ into a Calabi-Yau
manifold $X$ representing a given class in the second homology group of $X$.


A Calabi-Yau manifold of dimension $n$ is a complex (projective) $n$-manifold $X$ such that the space of holomorphic
$i$-forms on $X$ is 0-dimensional for $0<i<n$ and 1-dimensional for $i=n$.  The original mirror symmetry phenomenon
concerned the case $n=3$, but it was observed by Dijkgraaf [D1] that it also occurs in the far simpler case $n=1$.
Here ``Calabi-Yau" is just a synonym of ``genus one", and the coefficients of the counting functions merely
enumerate the generic mappings $Y\to X$, appropriately weighted, from curves of genus $g$ to a given complex 
curve $X$ of genus 1, where both $g$ and the degree $n$ of the mapping are fixed.  Here ``generic"
means that exactly two sheets of the covering come together over every ramification point, so that each point
of $X$ has either $n$ or $n-1$ preimages, and ``appropriately weighted" means, as usual, that each covering is
counted with a weight equal to the reciprocal of the number of its automorphisms over $X$.  Note that, by the
Riemann-Hurwitz formula, a covering of the above type will be ramified over precisely $2g-2$ points of $X$.  

The problem is therefore to compute $h^0(2g-2,n)$, where $h^0(k,n)$ denotes the number of (weighted) isomorphism
classes of connected $n$-sheeted coverings of a given Riemann surface $X$ of genus 1 with generic
ramification over $k$ given points of $X$.  If we denote by $h(k,n)$ the corresponding number without the
connectedness condition, then a standard argument gives the relation
$$ \sum_{n>0}\sum_{k\ge0} h^0(k,n)\,\frac{X^k}{k!}\,q^n
  \=\log\biggl(1\+\sum_{n>0}\sum_{k\ge0} h(k,n)\,\frac{X^k}{k!}\,q^n\biggr)\,,\tag37 $$
while another standard argument gives the formula
$$h(k,n)\=\frac1{n!}\,\N_1(\s_n;\undersetbrace k\to{T,\dots,T})\tag38$$
for $h(k,n)$ in terms of the generalized Frobenius number $\N_1(\s_n;T,\dots,T)$ of $(k+2)$-tuples
$(a,b,c_1,\dots,c_k)\in(\s_n)^2\times[T]^k$ with $[a,b]c_1\cdots c_k=1$ as introduced in \S1.3.  (The number $h^0(n,k)$
counts the tuples which generate a subgroup of $\s_n$ acting transitively on $\{1,\ldots,n\}$, but since we 
have no closed formula for this we must use (37) and (38) instead.)  

From formulas (38) and (11) with $g=1$ we find
$$h(k,n)\=\sum_{\pi\in\r_n}\nu_\pi(T)^k$$
where $\r_n$ as in \S1.2 denotes the set of irreducible representations of $\s_n$ and $\nu_\pi(T)$ ($\pi\in\r_n$)
as in \S1.2 and \S1.3 is the eigenvalue of $\sum_{g\in[T]_n}g$ on the representation $\pi$.  From this we obtain
$$ \sum_{k\ge0} h(k,n)\,\frac{X^k}{k!}\=\sum_{\pi\in\r_n}e^{\nu_\pi(T)X}\=H_n(e^X)\,,\tag39$$
where 
$$ H_n(u)\=\sum_{\pi\in\r_n}u^{\nu_\pi(T)}\quad\in\;\Z[u,u\i]\,,$$
a symmetric Laurent polynomial in $u$ which for small values of $n$ can be computed directly from the
information given in \S1.2:
$$\align H_2(u)&\=u+u\i\,,\\ H_3(u)&\=u^3+1+u^{-3}\,,\\ H_4(u)&\=u^6+u^2+1+u^{-2}+u^{-6}\,,\\
 H_5(u)&\=u^{10}+u^5+u^2+1+u^{-2}+u^{-5}+u^{-10}\,,\\  H_6(u)&\=u^{15}+u^9+u^5+2u^3+1+2u^{-3}+u^{-5}+u^{-9}+u^{-15}\,.\endalign $$
In general, we see from {\bf B.} and {\bf C.} of \S1.2 that, if $\pi\in\r_n$ corresponds to the function $f:\Z\to\Z_{\ge0}$
and to the Young diagram $Y\in\Y_n$, then
$$\nu_\pi(T)\=\sum_{r\in\Z}\,rf(r)\=\sum_{(x,y)\in Y}(x-y)\;.$$
Either of these descriptions leads to a formula for $H_n(u)$, but a more convenient formula is obtained by using a third
parametrization of the irreducible representations of $\s_n$: if $\pi$ corresponds to the function $f$ and the
Young diagram $Y$, denote by $s=f(0)=\max\{i\mid(i,i)\in Y\}$ the number of diagonal elements in $Y$ and let
$$ a_i\= \max\{j\mid (i+j-1,i)\in Y\}\,,\qquad b_i\=\max\{j\mid (i,i+j-1)\in Y\} $$
be the number of elements of $Y$ to the right of or above the point $(i,i)\in Y$, respectively, so that $Y$ is described
as $\bigcup_{i=1}^s\bigl([i,i+a_i-1]\!\times\!\{i\}\,\cup\,\{i\}\!\times\![i,i+b_i-1]\bigr)\,$. Then we have
$$ n\=\sum_{i=1}^s(a_i+b_i-1)\,,\qquad \nu_\pi(T)\=\sum_{i=1}^s\biggl(\binom{a_i}2-\binom{b_i}2\biggr)\,,\tag40$$
and $\r_n$ is parametrized by the set of tuples $(s,(a_1,\dots,a_s),(b_1,\dots,b_s))$ satisfying the inequalities
 $a_1>\dots>a_s>0$, $b_1>\dots>b_s>0$ and the first of equations (40).  This gives the generating function identity
$$ \sum_{n\ge0} H_n(u)\,q^n\=\text{coefficient of $\zeta^0$ in }\;
  \prod_{a\ge1}\bigl(1+u^{\binom a2}\,q^{a-1}\,\zeta\bigr)\cdot\prod_{b\ge1}\bigl(1+u^{-\binom b2}\,q^b\,\zeta\i\bigr)\,.$$
This can be written more symmetrically by shifting $a$ and $b$ by $\frac12$ to get
$$ \sum_{n\ge0} H_n(u)\,q^n\=\text{coefficient of $\zeta^0$ in }\;
  \prod_{m\in\{\frac12,\frac32,\frac52,\ldots\}}\bigl(1-u^{m^2/2}\,q^m\,\zeta\bigr)\,\bigl(1-u^{-m^2/2}\,q^m\,\zeta\i\bigr)\,.$$
(Here we have multiplied $\zeta$ by $-q^{1/2}u^{1/8}$, which does not affect the coefficient of $\zeta^0$.)
Combining this with the previous formulas, we obtain the following theorem, due to Douglas [Do] and Dijkgraaf [D1].
\proclaim{Theorem 6} For $g\ge1$, let $F_g(q)=\sum_{n\ge1}h^0(2g-2,n)\,q^n\,\in\Q[[q]]$ denote the counting function of
generically ramified coverings of a genus~$1$ Riemann surface by Riemann surfaces of genus $g$.  Then
$$\align \sum_{g=1}^\infty&\,F_g(q)\,\frac{X^{2g-2}}{(2g-2)!}\=\log\biggl(\sum_{n=0}^\infty\,H_n\bigl(e^X\bigr)\,q^n\biggr)\\
&\=\log\bigl(\text{\rm coefficient of $\zeta^0$ in }\prod_{m\in\Z_{\ge0}+\frac12}
  \bigl(1-u^{m^2/2}\,q^m\,\zeta\bigr)\bigl(1-u^{-m^2/2}\,q^m\,\zeta\i\bigr)\bigr)\;.\endalign$$
\endproclaim
% \proclaim{Theorem 6} The counting functions $F_g(q)=\sum_{n\ge1}h^0(2g-2,n)q^n$ ($g=1,\,2,\ldots$) of generically
% ramified connected coverings of a genus~1 Riemann surface by Riemann surfaces of genus $g$ are given by the   
% \endproclaim

This theorem has an interesting corollary, which was discovered and proved in the language of mathematical physics
by Dijkgraaf [D2] and Rudd [R] and proved from a purely mathematical point of view in [KZ].  Recall that a {\it modular form}
of weight $k$ on the full modular group $\Gamma=SL(2,\Z)$ is a function $F(z)$, defined for complex numbers $z$
with $\Im(z)>0$, which has a Fourier expansion of the form $F(z)=\sum_{n=0}^\infty a(n)e^{2\pi inz}$ with
coefficients $a(n)$ of polynomial growth and which satisfies the functional equation 
$F\bigl(\frac{az+b}{cz+d}\bigr)=(cz+d)^kF(z)$ for all $\bigl(\smallmatrix a&b\\c&d\endsmallmatrix\bigr)\in\Gamma$.
A {\it quasimodular form} of weight $k$ on $\Gamma$ is a function having a Fourier expansion with the same
growth condition and such that for each value of $z$ the function $(cz+d)^{-k}F\bigl(\frac{az+b}{cz+d}\bigr)$ is
a polynomial in $(cz+d)\i$ as $\bigl(\smallmatrix a&b\\c&d\endsmallmatrix\bigr)\in\Gamma$ varies.
The ring of modular forms is generated by the two functions 
$$E_4(z)\= 1+240\,\sum_{n=1}^\infty \frac{n^3\,q^n}{1-q^n}\=1+240q+2160q^2+6720q^3+\,\cdots$$
and 
$$E_6(z)\= 1-504\,\sum_{n=1}^\infty \frac{n^5\,q^n}{1-q^n}\=1-504q-16632q^2-122976q^3-\,\cdots$$
of weight 4 and 6, respectively, where $q=e^{2\pi iz}$, while the ring of quasimodular forms is generated by these
two functions together with the quasimodular form
$$E_2(z)\= 1-24\,\sum_{n=1}^\infty \frac{n\,q^n}{1-q^n}\=1-24q-72q^2-96q^3-\,\cdots$$
of weight 2.  Theorem~6 then implies:
\proclaim{Corollary}  For all $g\ge2$, $F_g(q)$ is the $q$-expansion of a quasimodular form of weight $6g-6$. 
\endproclaim
We omit the proof, referring the reader to the papers cited above.  The first example is
$$ F_2(q)\= \frac1{2^73^45}\bigl(5E_2^3 - 3E_2E_4 - 2E_6\bigr)\=q^2+8q^3+30q^4+80q^5+180q^6+\,\cdots\;,$$
which leads easily to the amusing closed formula $h^0(2,n)=\dfrac n6\,\sum_{d|n}(d^3-nd)$
for the number of coverings (generically ramified, with fixed ramification points) of an elliptic curve by
Riemann surfaces of genus $2$.  In general, however, the generating functions $F_g(q)$ do not have integral coefficients,
e.g. $F_3(q)$ begins $\frac1{12}q^2+\frac{20}3q^3+102q^4+\frac{2288}3q^5+\cdots\;$.

\vskip2cm
\heading References\endheading

\smallskip\noindent [D1]  R.~Dijkgraaf, Mirror symmetry and elliptic curves, 
in: The Moduli Spaces of Curves,  R.~Dijkgraaf, C.~Faber, G. van der
Geer eds., Progress in Mathematics, {\bf vol.~129}, Birkh\"auser,
Boston, 149--164~(1995)
\smallskip\noindent [D2]  R.~Dijkgraaf, Chiral deformations
of conformal field theories, Nuclear Phys. B, {\bf 493},
588--612~(1997)
\smallskip\noindent [Do] M.~R.~Douglas,
Conformal string theory techniques in large $N$ Yang--Mills theory,
in: Quantum field theory and string theory (Cargese 1993),
119--135, NATO Adv. Sci. Inst. Ser. B Phys., {\bf 328}, Plenum,
New York (1995)
\smallskip\noindent [DW]  R.~Dijkgraaf and E.~Witten, 
Topological gauge theories and group cohomology, 
Commun. Math. Phys., {\bf 129}, 393--429~(1990)
\smallskip\noindent [FQ] D.~Freed and F.~Quinn,
Chern--Simons gauge theory with a finite gauge group,
Commun. Math. Phys., {\bf 156}, 435--472~(1993)
\smallskip\noindent [KZ] M.~Kaneko and D.~Zagier,  
A generalized Jacobi theta function and quasimodular forms,
in: The Moduli Spaces of Curves,  R.~Dijkgraaf, C.~Faber, G. van der
Geer eds., Progress in Mathematics, {\bf vol.~129}, Birkh\"auser,
Boston, 165--172~(1995)
\smallskip\noindent [OV] A.~Okounkov and A.~Vershik,
A new approach to representation theory of symmetric groups,
Selecta Math. (N.S.), {\bf 2}, 581--605~(1996)
\smallskip\noindent [R] R.~Rudd, The string partition function
for QCD on the torus, hep-th/9407176
\smallskip\noindent [SSV] B.~Shapiro, M.~Shapiro, A.~Vainshtein, Ramified coverings of $S^2$ with one
degenerate branch point and enumeration of edge-ordered graphs,
in: Topics in singularity theory, Amer. Math. Soc. Transl. Ser. 2,
180, AMS. Providence RI, 219--227~(1997)
\smallskip\noindent [Z] D.~Zagier, 
On the distribution of the number of cycles of
elements in symmetric groups, Nieuw Arch. Wiskd., IV Ser.,
{\bf 13}, 489--495~(1995)
\end




