\documentclass[12pt]{article}

\usepackage{amsmath}

\setlength{\topmargin}{-1cm}
\setlength{\headheight}{1.5cm}
\setlength{\headsep}{0.3cm}
\setlength{\textheight}{22.5cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
\setlength{\textwidth}{14cm}

\newtheorem{lemma}{Lemma}
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{corollary}[lemma]{Corollary}

\begin{document}

\title{Minimal transitive products of transpositions ---\\
the reconstruction of a proof of A. Hurwitz}

\author{Volker Strehl}

\date{Computer Science Department (Informatik 8)\\
Universit\"at Erlangen-N\"urnberg\\
D-91058 Erlangen, Germany\\
{\small email: \texttt{strehl@informatik.uni-erlangen.de}}}

\maketitle

\begin{abstract}
We want to draw the combintorialists attention to an
important, but apparently little known paper by 
the function theorist A. Hurwitz, published in 1891,
where he announces the solution of a counting problem which has
gained some attention recently: in how many ways can a given 
permutation be written as the product of transpositions
such that the transpositions generate the full
symmetric group, and such that the number of factors is as 
small as possible (under this side condition).\\
The function theoretic origin and interest of this problem
will not be discussed in the present note --- see the original
paper by \textsc{Hurwitz}\cite{hurwitz91}. Current work
on related problems is contained e.g. in the article by
{\sc El Marraki et al.} \cite{ehzz96} in this volume.
\end{abstract}

Let $A$ denote a set with cardinality $\# A = n$, let
$\tau_1, \tau_2 , \ldots ,\tau_\mu$ be (not
necessarily distinct) transpositions on $A$, and let
$G_{\tau_1,\ldots ,\tau_\mu} = (A, \{\tau_1,\ldots,\tau_\mu\})$
denote the graph on $A$ whose edges correspond to the vertex
pairs exchanged by the transpositions. Denote by
$\rho$ the number of cyles of the permutation
$\tau_1 \circ \ldots \circ \tau_\mu$, and let
$\gamma$ denote the number of connected components of
the graph $G_{\tau_1, \ldots , \tau_\mu}$.
The following inequality can be proved by an easy induction:

\begin{lemma}
\hskip1cm
$n-\mu+\rho \leq 2\,\gamma$
\end{lemma}

We will say that the sequence
$\tau_1 , \ldots , \tau_\mu$ is 
{\em minimal} (w.r.t. the number $\mu$ of transpositions)
if $n - \mu + \rho = 2\,\gamma$,
and we will say that 
$\tau_1 , \ldots , \tau_\mu$ is {\em transitive} if $\gamma = 1$
holds. Here we are concerned with 
{\em minimal transitive} products of transpositions, i.e., sequences
$\tau_1 , \tau_2 , \ldots , \tau_{\mu}$ of transpositions
of $\{1,2,\ldots,n\}$ such that the set
$\{\tau_1 , \tau_2 , \ldots , \tau_{\mu}\}$
generates the symmetric group $\mathcal{S}_n$, i.e., 
$G_{\tau_1,\ldots ,\tau_\mu}$ is connected, and such that
the permutation
$\tau_1 \circ \tau_2 \circ \ldots \circ \tau_{\mu}$ has 
precisely $\rho = \mu - n + 2$ cycles, where
$\mu ~(\geq n-1)$ is the minimum
number of transpositions needed to represent a permutation with
$\rho$ cycles under this requirement of connectedness.

The simplest case to consider is the situation where $\rho = 1$,
i.e., where $G_{\tau_1,\ldots ,\tau_\mu}$ is a tree. The following
result is well known:

\begin{proposition}
A cyclic permutation of an $n$-element set has precisely
$n^{n-2}$ distinct factorisations as a product of $n-1$ transpositions.
\end{proposition}

This result is usually attributed to
{\sc D\'enes} \cite{denes59}, and it apprears at various
places in the literature, see e.g., 
{\sc Berge} \cite{berge68}, 
{\sc Comtet} \cite{comtet74},
and 
{\sc Eden, Sch\"utzenberger} \cite{eden_schutz62}.
Bijective proofs of this result have been given by 
{\sc Moszkowski} \cite{moszkowski89}
and by
{\sc Goulden, Pepper} \cite{gould_pepp93}.
Extensions of this result can be found e.g. in articles by
{\sc Biane} \cite{biane96},
{\sc Goulden} \cite{goulden94},
{\sc Goulden, Jackson} \cite{gould_jack94},
and the recent thesis by
{\sc Poulalhon} \cite{poula97}.

Here we are interested in the general problem: in how many ways
can a permutation $\sigma \in \mathcal{S}_n$ be represented
as a minimal transitive product of transpositions.
Let $\underline{k} = (k_1, k_2, \ldots, k_\rho)$
denote a composition of $n$ and let 
$\sigma \in \mathcal{S}$ be a permutation
of $\{1,2,\ldots,n\}$ of type $\underline{k}$, i.e.,
$\sigma$ has $\rho$ cycles of lengths given by
$k_1, k_2 , \ldots , k_{\rho}$,
so that in particular $k_1 + \ldots + k_{\rho} = n$.
Now we define
\begin{eqnarray*}
f(k_1, \ldots , k_\rho) 
& := &
\begin{cases}
&\text{the number of factorisations} \\
&\tau_1 \cdot \tau_2 \cdot \ldots \cdot \tau_{n+\rho-2}=\sigma \\
&\text{of the permutation $\sigma$ into a product of}\\
&\text{transpositions $\tau_i$ of $\{1,2,\ldots,n\}$,}\\
&\text{where
$\langle \tau_1, \ldots , \tau_{n+\rho-2} \rangle = \mathcal{S}_n$}
\end{cases}
\end{eqnarray*}
It is obvious that $f(k_1, \ldots , k_\rho)$ only depends on the
type $\underline{k}$
and that it is a symmetric function of the variables 
$k_1, \ldots , k_{\rho}$.

The following special cases have appeared in the literature:
\begin{flalign*}
\underline{k} = (n)  
&~:~ f(n) = n^{n-2} 
&\mbox{({\sc D\'enes} \cite{denes59})} \\
\underline{k} = (\underbrace{1, \ldots, 1}_n)
&~:~
f(1^n) = (2n -2)! \, n^{n-3}
&\mbox{({\sc Crescimanno, Taylor} \cite{cr_taylor95})}\\ 
\underline{k} = (p,q)  
&~:~ 
f(p,q) = p^p\,q^q\,\frac{(p+q-1)!}{(p-1)!\,(q-1)!}
&\mbox{({\sc Arnol'd} \cite{arnold96})}
\end{flalign*}
Quite recently the general solution to our problem
has been published by \textsc{Goulden} and \textsc{Jackson}
in \cite{gould_jack97}:

\begin{theorem}
\begin{equation}\label{eq1}
f(k_1, \ldots , k_\rho) = (n+\rho - 2)! \cdot n^{\rho-3}\,
\frac{k_1^{k_1+1} \cdots k_\rho^{k_\rho + 1}}
{k_1 ! \cdots k_\rho !} 
\end{equation}
\end{theorem}

In the following, it  will be instructive to take a look at the
\textsc{Goulden}---\textsc{Jackson} proof. (An exposition of this proof
and a discussion of its relation with the enumeration of maps is contained,
among other related items, in the thesis by {\sc Poulalhon} \cite{poula97}).

\bigskip

The combinatorial picture is quite obvious:
let $\tau_1, \ldots ,\tau_{\mu-1} , \tau_\mu$ be a minimal transitive
sequence of transpositions on $\{1,2,\ldots,n\}$, then
there are two possibilities:
\begin{itemize}
\item
$\tau_\mu$ is a ``split'':
\begin{quote}
this means that the sequence
$\tau_1 , \ldots , \tau_{\mu-1}$ is already minimal transitive
on $\{1,2,\ldots,n\}$ and
$\tau_{\mu}$ decomposes a cycle of length $i+j$ of
$\tau_1 \circ \ldots  \circ \tau_{\mu-1}$ into a cycle of
length $i$ and a cycle of length $j$.
\end{quote}
\item
$\tau_\mu$ is a ``join'':
\begin{quote}
this means that the graph
$G_{\tau_1, \ldots,\tau_{\mu-1}}$ has two connected components,
$A$ and $B$, say, such that $A \uplus B = \{1,2,\ldots,n\}$,  
such that
$\tau_1 , \ldots ,\tau_{\mu-1}$
is a shuffle of the two subsequences
$\tau_1' , \ldots , \tau_{\mu'}'$, minimal transitive on $A$, and 
$\tau_1'' , \ldots , \tau_{\mu''}''$, minimal transitive on $B$.
Here
$\tau_\mu$ joins a cycle of length $i$ of 
$\tau_1' \circ \ldots \circ \tau_{\mu'}'$
and a cycle of length $j$ of
$\tau_1'' \circ \ldots \circ \tau_{\mu''}''$
into a cycle of length $i+j$ of
$\tau_1 \circ \ldots \circ\tau_{\mu-1}$
\end{quote}
\end{itemize}

Now introduce commuting variables ~~$p_1,p_2,p_3 , \ldots$
and for any composition $\underbar{k} = (k_1,\ldots,k_\rho)$ put
$p_{\scriptstyle\underbar{k}} := p_{k_1} \cdot \ldots \cdot p_{k_\rho}$.
Correspondingly, for any permutation $\sigma$ of type $\underbar{k}$ 
we put $p_{\sigma} := p_{\scriptstyle\underbar{k}}$ and
for any sequence of transpositions $\tau_1 , \ldots , \tau_\mu$
we consider the weight function
\[
w(\tau_1, \ldots , \tau_\mu) :=
\frac{t^\mu}{\mu!} \; p_{\tau_1 \circ \ldots \circ \tau_\mu}
\]
The main object of study is now the generating function
\[
\tilde{F} = \tilde{F}(p_1,p_2, \ldots;z,t)
\sum_{n \geq 1} \frac{z^n}{n!} 
:=
\sum_{\tau_1,\ldots,\tau_\mu~m.t.}
w(\tau_1,\ldots,\tau_\mu)
\]
where the inner summation runs over all minimal transitive
sequences of transpositions on $\{1,2,\ldots,n\}$.

It is not difficult to see that the above combinatorial
consideration materializes into the following
partial differential equation:
\begin{lemma}
\[
\frac{\partial\tilde{F}}{\partial t}
=
\frac{1}{2}
\sum_{i,j}
\underbrace{p_{i+j}
\cdot i\cdot\frac{\partial\tilde{F}}{\partial p_i}
\cdot j\cdot\frac{\partial\tilde{F}}{\partial p_j}}_{\tau_\mu~join}
+
\underbrace{p_i \cdot p_j \cdot
(i+j) \cdot
\frac{\partial \tilde{F}}{\partial p_{i+j}}}_{\tau_\mu~split}
\]
\end{lemma}

Putting $t=1$ this turns into
\begin{corollary}
For $F = F(p_1,p_2, \ldots;z) := \tilde{F}(p_1,p_2, \ldots;z,1)$
\begin{eqnarray*}
\lefteqn{
z\,\frac{\partial F}{\partial z}
+ \sum_i p_i \, \frac{\partial F}{\partial p_i}
- 2 \, F =}\\
&=&
\frac{1}{2}
\sum_{i,j}
 p_{i+j}
\cdot i\cdot\frac{\partial F}{\partial p_i}
\cdot j\cdot\frac{\partial F}{\partial p_j} 
+
 p_i \cdot p_j \cdot
(i+j) \cdot
\frac{\partial F}{\partial p_{i+j}} 
\end{eqnarray*}
since $\mu = n + \rho -2$
and
$\rho = \sum_j k_j =
\sum_i \underbrace{\#\{ j\,;\,k_j = i \}}_{=:~ \ell_i}
$
\end{corollary}

Now we put
for any composition $\underbar{k} = (k_1,\ldots,k_\rho)$ :
\begin{eqnarray*}
\sigma(\underbar{k}) &:=&
\mbox{the number of permutations of type}~\underbar{k} \\
&=&
\frac{n!}
{k_1 \cdot \ldots \cdot k_\rho \cdot \ell_1! \cdot \ldots \cdot \ell_n !}\\
\pi(\underbar{k}) &:=&
\mbox{the number of partitions of type}~\underbar{k} \\
&=&
\frac{n!}
{k_1! \cdot \ldots \cdot k_\rho ! \cdot \ell_1! \cdot \ldots \cdot \ell_n !}\\
\mu(\underbar{k}) &:=&
\sum_i k_i + \rho -2 = n + \rho - 2 
\end{eqnarray*}
where
$\ell_i = \#\{j\,;\,k_j = i \}$. 
It is then easy to check that the above generating function
can be written as
\[
F(p_1,p_2,\ldots;z) =
\sum_{n \geq 1}
\frac{z^n}{n!}
\sum_{\underbar{k}\,\vdash\, n}
\frac{\sigma(\underbar{k}) \cdot f(\underbar{k})}{\mu(\underbar{k})!}
\; p_{\underbar{k}}
\]
Now, if we define
\[
G(p_1,p_2,\ldots;z) =
\sum_{n \geq 1}
\frac{z^n}{n!}
\sum_{\underbar{k}\,\vdash\,n}
n^{\rho-3} \prod_{j=1}^\rho k_j^{k_j} \cdot \pi(\underbar{k})
\; p_{\underbar{k}}
\]
then one has to show that
\[
F(p_1,p_2,\ldots;z) =
G(p_1,p_2,\ldots;z)
\]
i.e., one has to show that
\begin{eqnarray*}
G &=&
\sum_{n \geq 1}
\frac{z^n}{n!} \cdot \frac{1}{n^3}
\left[
\frac{y^n}{n!}
\right]
\mathsf{exp}\left(
n \cdot \sum_i \frac{i^i}{i!}\,p_i\,y^i \right) \\
&=&
\sum_{n \geq 1}
\frac{z^n}{n^3}
\left[
y^n
\right]
\mathsf{exp}\left(
n \cdot \sum_i \frac{i^i}{i!}\,p_i\,y^i \right)
\end{eqnarray*}
satisfies the same differential equation as $F$ 
(see the above corollary), 
together with appropriate initial conditions.
Here, as usual,  $[y^n]$ denotes ``the coefficient of $y^n$ in $\ldots$''.

\textsc{Goulden}--\textsc{Jackson} proceed by introducing
the function
\[
\phi(y) :=
\mathsf{exp}\left(
n \cdot \sum_i \frac{i^i}{i!}\,p_i\,y^i \right)
\]
and they let $w = w(p_1,p_2, \ldots;y)$ denote the solution of
the implicit equation
\[
w = z \cdot \phi(w)
\]
Then, by \textsc{Lagrange}'s formula, applied to $\mathsf{log}(y/z)$,
it turns out that $G$ can be written as
\[
G = 
\sum_{n \geq 1} 
\frac{z^n}{n^2} \left[
z^n
\right]
\sum_{i \geq 1} \frac{i^i}{i!}\,p_i\,w^i 
\]
\textsc{Goulden-Jackson} go on and derive various formulas for
\[
\frac{\partial w}{\partial p_k}~,~
\frac{\partial w}{\partial z}~,~
\frac{\partial G}{\partial z}~,~
\frac{\partial^2 G}{\partial z \partial p_k}~,~
\frac{\partial G}{\partial p_k}~\ldots
\]
in terms of implicitly defined function $w$, such as
\[
z\,\frac{\partial G}{\partial z} =
\sum_{i \geq 1}
\frac{i^{i-1}}{i!}\;p_i\,w^i
-
\frac{1}{2}
\left(
\sum_{i \geq 1} \frac{i^i}{i!}\;p_i w^i \right)^2
\]
which they use to show that $G$ (and $F$, of course) satisfy
\begin{eqnarray*}
\lefteqn{
\left( z\,\frac{\partial}{\partial z} \right)
\left(
z\,\frac{\partial Y}{\partial z}
+ \sum_i p_i \, \frac{\partial Y}{\partial p_i}
- 2 \, Y \right)
=}\\
&=&
\left( z\,\frac{\partial}{\partial z} \right)
\frac{1}{2}
\left\{
\sum_{i,j}
 p_{i+j}
\cdot i\cdot\frac{\partial Y}{\partial p_i}
\cdot j\cdot\frac{\partial Y}{\partial p_j} 
+
 p_i \cdot p_j \cdot
(i+j) \cdot
\frac{\partial Y}{\partial p_{i+j}}\right\} 
\end{eqnarray*}

The verification of all the detail is tedious, and it eventually
boils down to showing two particular results:

\begin{lemma}\label{firstlemma}
Let
\[
S_m := 
\sum_{\substack{i,j \geq 1\\ i+j=m}} \frac{i^i}{i!}\; \frac{j^{j-1}}{j!}
\]
Then
\[
S_m = \frac{m^m}{m!} - \frac{m^{m-1}}{m!}
\]
\end{lemma}

This (easy) statement
is in fact a version of \textsc{Abel}'s binomial theorem.
Quite a bit more intricate is

\begin{lemma}\label{secondlemma}
Let
\[
T_{k,m} := 
\frac{k^{k+1}}{k!} \sum_{\substack{i \geq 1, j\geq 0\\ i+j=m}}
\frac{1}{k+j}\;\frac{i^i}{i!}\;\frac{j^j}{j!}
\]
Then
\[
T_{k,m} + T_{m,k}
=
\frac{(k+m)^{k+m}}{(k+m)!}
\]
\end{lemma}



As a matter of fact, the main result (\ref{eq1}) was already presented 
as early as
1891 by {\sc Hurwitz} in his big article (\cite{hurwitz91}, p. 21). 
Indeed, {\sc Hurwitz} does not present a complete proof,
he only mentions that he has been guided to formulate (\ref{eq1}) 
as a conjecture as the result of a very laborious induction
(...{\em durch eine sehr m\"uhsame Induktion zu der Vermutung 
gef\"uhrt}...), and that he does not want to present a detailed proof
in his article. However, he gives a hint about the way he 
proved the result: he shows that the above combinatorial
analysis of the situation leads to the recursion
\begin{multline}\label{eq2}
f(k_1, \ldots , k_\rho) = \\
\sum_{1 \leq i < j \leq \rho}
k_i \, k_j \, f(\ldots, k_i + k_j , \ldots) + \frac{1}{2}
\sum_{1 \leq i \leq \rho} k_i
\sum_{r = 1}^{k_i - 1}
\Phi_r (k_i | k_1, \ldots , \widehat{k_i} , \ldots k_\rho)
\end{multline}
where
\[
\Phi_r (k_i | k_1 , \ldots , \widehat{k_i}, \ldots k_\rho) =
\sum_{(\alpha, \beta)}
\frac{(n+\rho - 3)!} {\sigma ! \,\, \tau !}\,
f(r, k_{\alpha_1} , \ldots , k_{\alpha_\lambda})\,
f(s, k_{\beta_1} , \ldots , k_{\beta_\mu})
\]
Here $\widehat{k_i}$ indicates that the term $k_i$ is missing.
The summation in $\sum_{(\alpha, \beta)}$  
runs over all decompositions of
$\{ 1,2, \ldots , \rho \} \setminus \{i\} $ 
into two disjoint subsets
$\{\alpha_1, \ldots, \alpha_\lambda\}$ , 
$\{\beta_1, \ldots, \beta_\mu \}$
where
\begin{eqnarray*}
s &=& k_i - r\\ 
\rho &=& \lambda + \mu + 1\\
\sigma &=& r + k_{\alpha_1} + \ldots + k_{\alpha_\lambda} + \lambda - 1\\
\tau &=& s + k_{\beta_1} + \ldots + k_{\beta_\mu} + \mu - 1\\
\sigma + \tau &=& n + \lambda + \mu - 2 = n + \rho - 3
\end{eqnarray*}
Since the solution of the recurrence equation (\ref{eq2})
is determined once the initial value $f(1)=1$ has been fixed, 
it suffices, as remarked by {\sc Hurwitz}, that 
after substituting (\ref{eq1}) into this equation it
reduces to an identity. It seems that he has found a rather
complicated way for doing that, but he mentions 
that this task would be accomplished more easily by using
(\ref{eq5a}),(\ref{eq5b}) below.

It is the purpose of this present note to carry through this
proposal by {\sc Hurwitz} 
and thus, ,in a sense, to reconstruct {\sc Hurwitz}' proof
of (\ref{eq1}).

\bigskip

The assertion to be proved reads
\begin{eqnarray*}
\lefteqn{(n+\rho - 2)! \cdot n^{\rho - 3} \,
\frac{k_1^{k_1+1} \cdots k_\rho^{k_\rho +1}} 
{k_1! \cdots k_\rho !}}\\
&=&
\sum_{i < j} k_i \cdot k_j \cdot (n + \rho - 3) ! \cdot n^{\rho-4}
\frac{k_1^{k_1+1} \cdots (k_i + k_j)^{k_i+k_j+1} \cdots k_\rho^{k_\rho+1}}
{k_1! \cdots (k_i + k_j)! \cdots k_\rho!} \\
&&+\,
\frac{1}{2} \sum_i k_i \sum_{r=1}^{k_i-1} \sum_{(\alpha, \beta)}
(n+\rho-3)! 
\,(\sigma - \lambda + 1)^{\lambda-2} (\tau-\mu+1)^{\mu-2} \times\\
&&
\hskip3cm
\times
\frac{ r^{r+1}k_{\alpha_1}^{k_{\alpha_1}+1} \cdots 
k_{\alpha_\lambda}^{k_{\alpha_\lambda} +1} \cdot
s^{s+1}k_{\beta_1}^{k_{\beta_1}+1} \cdots
k_{\beta_\mu}^{k_{\beta_\mu}+1} }
{ r! \,k_{\alpha_1}! \cdots k_{\alpha_\lambda}! \,~ 
s! \, k_{\beta_1}! \cdots k_{\beta_\mu}! }
\end{eqnarray*}
Dividing both sides by
\[
(n + \rho - 3)! \cdot n^{\rho - 4}\, 
\frac{ k_1^{k_1 +1} \cdots k_\rho^{k_\rho + 1} }
{ k_1! \cdots k_\rho ! }
\]
one obtains
\begin{multline}\label{eq3}
(n + \rho - 2) \cdot n
=
\sum_{i < j} \, k_i \, k_j
\frac{(k_i + k_j)^{k_i + k_j + 1}\,  k_i! \, k_j!}
{(k_i + k_j)! \, k_i^{k_i +1} \, k_j^{k_j +1}} \\
+\,
\frac{n^{4-\rho}}{2} \sum_i k_i 
\sum_{r=1}^{k_i -1}
\sum_{(\alpha, \beta)}
(\sigma - \lambda + 1)^{\lambda - 2} (\tau - \mu + 1)^{\mu - 2}
\frac{r^{r+1} \, s^{s+1} \, k_i!}
{r! \, s! \, k_i^{k_i + 1}} \\
=
\sum_{i< j} k_i k_j
\frac{(k_i + k_j)^{k_i + k_j + 1} \, k_i ! \,  k_j!}
{(k_i + k_j)! \, k_i^{k_i + 1} \, k_j^{k_j +1}} 
\hskip4cm{}
\\
+\,
\frac{n^{4-\rho}}{2} \sum_i
\frac{k_i!}{k_i^{k_i}}
\sum_{r=1}^{k_i-1}
\frac{r^{r+1} s^{s+1}} {r! \, s!}
F_{-2,-2}(r,s\,|\,k_1, \ldots , \widehat{k_i}, \ldots, k_{\rho})
\end{multline}
where the following notation is used
\[
F_{r,s}(u,v\,|\,x_1 , \ldots , x_n) :=
\sum_{(\alpha,\beta)}
(u+x_{\alpha_1} + \ldots + x_{\alpha_{\lambda}})^{r + \lambda}
(v+x_{\beta_1} + \ldots + x_{\beta_{\mu}})^{s + \mu}
\]
using the same convention as above, i.e., 
the $\Sigma_{\alpha,\beta}$ runs over all decompositions 
$\{\alpha_1, \ldots, \alpha_{\lambda}\}$, 
$\{\beta_1,\ldots,\beta_{\mu}\}$
of 
$\{1, \ldots, n\}$, where 
$0 \leq \lambda \leq n$ and 
$\mu = n - \lambda$.

These functions have been investigated by {\sc Hurwitz} in \cite{hurwitz02}.  
He uses in particular
\begin{equation}\label{eq4a}
F_{r,s} = u\cdot F_{r-1,s} +
\sum_{k=1}^n x_k \cdot
F_{r,s}(u + x_k,v\,|\,x_1 , \ldots , \widehat{x_k} , \ldots , x_n)
\end{equation}
and similarly
\begin{equation}\label{eq4b}
F_{r,s} = v\cdot F_{r,s-1} +
\sum_{k=1}^n x_k \cdot
F_{r,s}(u,v + x_k\,|\,x_1 , \ldots , \widehat{x_k} , \ldots , x_n)
\end{equation}
and he evaluates the following special cases (see also \cite{comtet74})
\begin{eqnarray}
F_{-1,-1}(u,v\,|\,x_1 , \ldots , x_n) &=& 
\left(\frac{1}{u} + \frac{1}{v}\right)(u+v+x_1 + \ldots + x_n)^{n-1}
\label{eq5a}\\
F_{-1,0}(u,v\,|\,x_1 , \ldots , x_n) &=& 
\frac{1}{u} \cdot (u+v+x_1 + \ldots + x_n)^{n}
\label{eq5b}
\end{eqnarray}
the second of which is a generalization of {\sc Abel}'s
celebrated generalization \cite{abel26}
of the binomial identity:
\begin{equation}\label{eq6}
\sum_{\lambda=0}^n
\binom{n}{\lambda} (u + \lambda\,x)^{\lambda-1}(v-\lambda\,x)^{n-\lambda}
=
\frac{1}{u} \cdot (u+v)^n
\end{equation}

A combinatorial treatment of identity (\ref{eq6})
by {\sc Abel}, 
of identities (\ref{eq5a}),(\ref{eq5b}) by {\sc Hurwitz}, 
and of many other generalisations of {\sc Abel}'s 
binomial identity has been given by the present author
in \cite{strehl92}.

From (\ref{eq4a}) and (\ref{eq4b}) one obtains
\begin{multline*}
r \cdot F_{-2, -2} (r,s \,|\, k_1 , \ldots , \widehat{k_i} , \ldots , k_\rho)
= 
F_{-1, -2}(r,s\,|
\,k_1 , \ldots , \widehat{k_i}, \ldots , k_{\rho}) \\
- \sum_{\substack{j=1\\ j\not=i }}^\rho k_j 
\cdot 
F_{-1,-2}(r + k_j , s \,|
\, k_1 , \ldots , \widehat{k_i} , \ldots , \widehat{k_j} , \ldots , k_\rho)
\end{multline*}
and
\begin{eqnarray*}
\lefteqn{r \cdot s \cdot 
F_{-2,-2}(r, s \,|\, k_1 , \ldots , \widehat{k_i} , \ldots , k_\rho)}\\
&=&
s \cdot 
F_{-1,-2}(r, s \,|\, k_1 , \ldots , \widehat{k_i} , \ldots , k_\rho) \\ 
&&- 
\sum_{\substack{j=1 \\ j\not=i}}^\rho
k_j \cdot s \cdot 
F_{-1,-2}(r + k_j, s \,|\, k_1 , \ldots , \widehat{k_i} , \ldots ,
\widehat{k_j} , \ldots , k_\rho) \\
&=&
F_{-1,-1}(r, s \,|\, k_1 , \ldots , \widehat{k_i} , \ldots , k_\rho ) \\
&& 
- \sum_{\substack{j=1 \\ j\not=i}}^\rho
k_j \cdot
F_{-1,-1} (r, s + k_j \,|\, k_1 , \ldots , \widehat{k_i} , \ldots , \widehat{k_j} , \ldots , k_\rho) \\
&&
- \sum_{\substack{j=1 \\ j\not=i}}^\rho
k_j \cdot
F_{-1,-1}(r + k_j , s \,|\, k_1 , \ldots , \widehat{k_i} , \ldots , \widehat{k_j} , \ldots , k_\rho)\\ 
& &
+\sum_{\substack{j=1 \\ j\not=i}}^\rho
\sum_{\substack{l=1 \\ l\not=i,j}}^\rho
k_j \cdot k_\ell \cdot
F_{-1,-1}(r + k_j, s + k_\ell \,|\, k_1 , \ldots , \widehat{k_i} , \ldots , \widehat{k_j} , \ldots , 
\widehat{k_\ell} , \ldots , k_\rho)
\end{eqnarray*}
and the evaluation of $F_{-1,-1}$ mentioned in (\ref{eq5a})  
leads to
\begin{eqnarray*}
\lefteqn{r \cdot s \cdot 
F_{-2,-2} (r,s \, |\,  k_1 , \ldots , \widehat{k_i} , \ldots , k_\rho )}\\ 
&=&
n^{\rho-2} \left(\frac{1}{r} + \frac{1}{s}\right)  -
\sum_{\substack{j=1 \\ j\not=i}}^\rho
k_j \cdot n^{\rho - 3} \left(\frac{1}{r} + \frac{1}{s+k_j}\right) \\
&&-
\sum_{\substack{j=1 \\ j\not=i}}^\rho
k_j \cdot n^{\rho-3}
\left(\frac{1}{r+k_j} + \frac{1}{s}\right) 
+ \,
\sum_{\substack{j=1 \\ j\not=i}}^\rho
\sum_{\substack{\ell=1 \\ \ell\not=j,i}}^\rho
k_j \cdot k_\ell \cdot n^{\rho-4}
\left(\frac{1}{r+k_j} + \frac{1}{s+k_\ell}\right) \\
&=& 
n^{\rho-2} \left(\frac{1}{r} + \frac{1}{s}\right)
- n^{\rho-3} \frac{n - k_i}{r}
- n^{\rho-3} \frac{n-k_i}{s} \\
&& -\,
n^{\rho-3} \sum_{j\not=i}
\frac{k_j}{s+k_j}
- n^{\rho-3} \sum_{j\not=i}
\frac{k_j}{r+k_j} \\
&& +\,
n^{\rho-4} 
\sum_{\substack{j,\ell \\ j\not=\ell\not=i\not=j}}
k_j \cdot k_\ell
\left(\frac{1}{r+k_j} + \frac{1}{s+k_j}\right) \\
&=& 
n^{\rho-3} \cdot k_i
\left(\frac{1}{r} + \frac{1}{s}\right)
- n^{\rho-3} 
\sum_{j \not=i}
\left(\frac{k_j}{s+k_j} + \frac{k_j}{r+k_j}\right) \\
&& +\,
n^{\rho-4}
\left(
\sum_{j,\ell} \frac{k_j}{r+k_j} (n-k_i-k_j) +
\sum_{j,\ell} \frac{k_\ell}{s+k_\ell} (n-k_i-k_\ell)
\right) \\
&=& 
n^{\rho-3} \cdot k_i \cdot
\left(\frac{1}{r} + \frac{1}{s}\right)
- n^{\rho-4}
\left(
\sum_{j\not=i}
\frac{k_j \,(k_i+k_j)}{r+k_j}
+ \sum_{\ell\not=i}
\frac{k_\ell \,(k_i+k_\ell)}{s+k_\ell}
\right)
\end{eqnarray*}
Thus the second sum on the r.h.s. of (\ref{eq3}) equals
\begin{eqnarray*}
\lefteqn{\frac{n}{2} \sum_i
\frac{k_i!}{k_i^{k_i-1}}
\sum_{r=1}^{k_i-1}
\left(\frac{1}{r} + \frac{1}{s}\right)
\frac{r^r}{r!} \frac{s^s}{s!}}\\
&&-
\frac{1}{2} \sum_i
\frac{k_i!}{k_i^{k_i}}
\sum_{r=1}^{k_i-1}
\left(
\sum_{j\not=i}
\frac{k_j (k_i + k_j)}{r + k_j}
+ \sum_{\ell\not=i}
\frac{k_\ell (k_i + k_\ell)}{s+k_\ell}
\right) \\
&=&
n \cdot \sum_{i} (k_i -1)  -
\sum_i \frac{1}{k_i^{k_i}} 
\sum_{j\not=i} k_j (k_i + k_j)
\sum_{r=1}^{k_i-1} \binom{k_i}{r,s}
\frac{1}{r+k_j} r^r s^s \\
&=&
n \cdot (n - \rho) - \sum_i \ldots
\end{eqnarray*}
where the first equality uses the known identity
\[
\sum_{r=1}^{k_i-1}
\binom{k_i}{r,s} r^{r-1} s^s = k_i^{k_i-1} (k_i - 1)
\]
which appears as Proposition 3.2, part 1 in \cite{gould_jack97},
here mentioned as Lemma \ref{firstlemma},
and which is in fact an immediate consequence of 
{\sc Abel}'s binomial identity (\ref{eq6}).


The identity to be verified now reads
\begin{multline}\label{eq7}
2\,n \,(\rho - 1)
=\\
\sum_{i<j}
\frac{(k_i + k_j)^{k_i+k_j+1} \, k_i!  \, k_j!}
{k_i^{k_i}\, k_j^{k_j} (k_i + k_j)!} 
-
\sum_{i} \frac{1}{k_i^{k_i}}
\sum_{j\not=i} k_j (k_i + k_j)
\sum_{r=1}^{k_i-1} \binom{k_i}{r,s}
\frac{1}{r+k_j}\, r^r\, s^s
\end{multline}
It obviously suffices to prove this in the special case $\rho = 2$,
i.e.,
\begin{multline}\label{eq8}
2\,(a+b) 
=
\frac{(a+b)^{a+b+1}\,  a! \, b!}
{a^a \, b^b\,  (a+b)!} \\
-
\frac{b(a+b)}{a^a} \sum_{r=1}^{a-1}
\binom{a}{r,s} \frac{1}{r+b}\, r^r \,s^s
-
\frac{a(a+b)}{b^b} \sum_{r=1}^{b-1}
\binom{b}{r,s} \frac{1}{r+a}\, r^r\, s^s
\end{multline}
because summing the $\binom{\rho}{2}$ equalities (\ref{eq8})
for $a = k_i, b = k_j$
with $1 \leq i < j \leq \rho$ yields (\ref{eq7}) since
\[
\sum_{1\leq i<j\leq\rho} (k_i + k_j) = (\rho -1) (k_1 + \ldots + k_n) =
(\rho - 1) \cdot n
\]
(\ref{eq8}) is obviously equivalent to
\begin{equation}\label{eq9}
\frac{(a+b)^{a+b} \,a! \,b!}{a^a\, b^b \,(a+b)!} 
=
\frac{b}{a^a}
\sum_{r=0}^{a-1} \binom{a}{r,s} \frac{1}{r+b}\,
r^r \, s^s 
+
\frac{a}{b^b} 
\sum_{r=0}^{b-1} \binom{b}{r,s} \frac{1}{r+b}\,
r^r \, t^t
\end{equation}
with $s=a-r$ in the first sum and $t=b-r$ in the second.
Setting
\[
T_{k,m} := \frac{k^{k+1}}{k!}
\sum_{\substack{i\geq 1, j \geq 0 \\ i+j=m}}
\frac{i^i \, j^j}{i! \, j!} \cdot \frac{1}{k+j}
\]
one has
\[
\frac{b}{a^a} 
\sum_{r=0}^{a-1}
\binom{a}{r,s} \frac{1}{r+b}\, r^r \, s^s =
\frac{a! \, b!}{a^a \, b^b} \, T_{b,a}
\]
and thus (\ref{eq9}) follows from
\[
T_{k.m} + T_{m,k} =
\frac{(k+m)^{k+m}}{(k+m)!}
\]
which is proved by {\sc Goulden} and {\sc Jackson} in  
\cite{gould_jack97} using Lagrange inversion
(Proposition 3.2, part 2, here Lemma \ref{secondlemma}), 
and which was most probably already known to {\sc Hurwitz}.
Thus (\ref{eq1}) is proved.



\begin{thebibliography}{9}
\bibitem{abel26}
N.H. Abel,
Beweis eines Ausdrucks von welchem die Binomial-Formel
ein einzelner Fall ist.
{\em Crelles Journal f\"ur die Reine und Angewandte Mathematik},
vol 1 (1826), 159-160.
\bibitem{arnold96}
V. I. Arnol'd,
Topological classifications of trigonometrical polynomials
and combinatorics of graphs. 
{\em Functional Analysis and its Applications}, vol 30 (1996), 1-17. 
\bibitem{berge68}
C. Berge,
{\em Principes de combinatoire}.
Dunod, Paris, 1968.
\bibitem{biane96}
P. Biane,
Minimal factorizations of a cycle and central multiplicative
functions on the infinite symmetric group.
{\em J. Combinatorial Theory}, Series A, vol. 76 (1996), 197-212.
\bibitem{comtet74}
L. Comtet,
{\em Advanced Combinatorics}.
D. Reidel Publ. Comp., Dordrecht, 1974.
\bibitem{cr_taylor95}
M. Crescimanno and W. Taylor,
Large $N$ phases of chiral $QCD_2$.
{\em Nuclear Phys.} B, vol. 437 (1995), 3-24.
\bibitem{denes59}
J. D\'enes,
The representation of a permutation as the product of a minimal
number of transpositions and its connection with the theory of
graphs.
{\em Publ. Math. Inst. Hungar. Acad. Sci.}, vol. 4 (1959), 63-70.
\bibitem{eden_schutz62}
M. Eden and M.P. Sch\"utzenberger,
Remark on a theorem of D\'enes.
{\em Publ. Math. Inst. Hungar. Acad. Sci.}, vol. 7, ser. A (1962), 353-355.
\bibitem{ehzz96}
M. El Marraki, N. Hanusse, J. Zipperer and A. Zvonkin,
Cacti, braids and complex polynomials.
{\em S\'eminaire Lotharingien de Combinatoire}, vol. 37 (B37b)(1996), 36p.
\bibitem{goulden94}
I.P. Goulden,
A differential operator for symmetric functions and the combinatorics
of multiplying transpositions.
{\em Trans. Amer. Math. Soc.}, vol. 344 (1994), 421-440.
\bibitem{gould_jack94}
I.P. Goulden and D. Jackson,
Symmetric functions and Macdonald's result for top connexion coefficients
in the symmetric group.
{\em J. Algebra}, vol. 166 (1994), 364-378.
\bibitem{gould_jack97}
I.P. Goulden and D.M. Jackson,
Transitive factorisations into transpositions
and holomorphic mappings on the sphere.
{\em Proc. Amer. Math. Soc.}, vol. 125 (1997), 51-60.
\bibitem{gould_pepp93}
I.P. Goulden and S. Pepper,
Labelled trees and factorisations of a cycle into transpositions.
{\em Discrete Math.}, vol. 113 (1993), 263-268.
\bibitem{hurwitz91} 
A. Hurwitz, 
\"Uber Riemann'sche Fl\"achen mit gegebenen Ver\-zweig\-ungs\-punk\-ten. 
{\em Mathematische Annalen}, vol. 39 (1891), 1-66.
\bibitem{hurwitz02} 
A. Hurwitz,
\"Uber Abels Verallgemeinerung der binomischen Formel.
{\em Acta Mathematica}, vol. 26 (1902), 199-203.
\bibitem{moszkowski89}
P. Moszkowski,
A solution of a problem of D\'enes,
a bijection between trees and factorizations of cyclic permutations.
{\em European J. Combin.}, vol. 101 (1989), 13-16.
\bibitem{poula97}
D. Poulalhon,
{\em Graphes et d\'ecompositions de permutations.}
M\'emoire de DEA, \'Ecole Polytechnique, 1997.
\bibitem{strehl92}
V. Strehl,
Identities of Rothe-Abel-Schl\"afli-Hurwitz-type.
{\em Discrete Math.}, vol. 99 (1992), 321-340.
\end{thebibliography}
\end{document}
