Minimal transitive products of transpositions — the reconstruction of a proof of A. Hurwitz

Volker Strehl

Computer Science Department (Informatik 8) Universität Erlangen-Nürnberg D-91058 Erlangen, Germany

               email: strehl@informatik.uni-erlangen.de

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 Hurwitz[14]. Current work on related problems is contained e.g. in the article by El Marraki et al. [9] in this volume.

Let A denote a set with cardinality #A = n, let τ_{1}, τ_{2}, …, τ_{μ} be (not necessarily distinct) transpositions on A, and let G_{τ_{1},... ,τ_{μ}} = (A, {τ_{1}, …, τ_{μ}}) denote the graph on A whose edges correspond to the vertex pairs exchanged by the transpositions. Denote by ρ the number of cyles of the permutation τ_{1} ∘…∘τ_{μ}, and let γ denote the number of connected components of the graph G_{τ_{1},... ,τ_{μ}}. The following inequality can be proved by an easy induction:

Lemma 1 n − μ + ρ ≤ 2 γ

We will say that the sequence τ_{1}, …, τ_{μ} is minimal (w.r.t. the number μ of transpositions) if n − μ + ρ = 2 γ, and we will say that τ_{1}, …, τ_{μ} is transitive if γ = 1 holds. Here we are concerned with minimal transitive products of transpositions, i.e., sequences τ_{1}, τ_{2}, …, τ_{μ} of transpositions of {1, 2, …, n} such that the set {τ_{1}, τ_{2}, …, τ_{μ}} generates the symmetric group S_{n}, i.e., G_{τ_{1},... ,τ_{μ}} is connected, and such that the permutation τ_{1} ∘ τ_{2} ∘ … ∘ τ_{μ} has precisely ρ = μ − n + 2 cycles, where μ (≥ n − 1) is the minimum number of transpositions needed to represent a permutation with ρ cycles under this requirement of connectedness.

The simplest case to consider is the situation where ρ = 1, i.e., where G_{τ_{1},... ,τ_{μ}} is a tree. The following result is well known:

Proposition 2 A cyclic permutation of an n-element set has precisely n^{n−2} distinct factorisations as a product of n − 1 transpositions.

This result is usually attributed to Dénes [7], and it apprears at various places in the literature, see e.g., Berge [3], Comtet [5], and Eden, Schützenberger [8]. Bijective proofs of this result have been given by Moszkowski [16] and by Goulden, Pepper [13]. Extensions of this result can be found e.g. in articles by Biane [4], Goulden [10], Goulden, Jackson [11], and the recent thesis by Poulalhon [17].

Here we are interested in the general problem: in how many ways can a permutation σ ∈ S_{n} be represented as a minimal transitive product of transpositions. Let \underline{k} = (k_{1}, k_{2}, …, k_{ρ}) denote a composition of n and let σ ∈ S be a permutation of \{1, 2, …, n\} of type \underline{k}, i.e., σ has ρ cycles of lengths given by k_{1}, k_{2}, …, k_{ρ}, so that in particular k_{1} + … + k_{ρ} = n. Now we define

f(k_{1}, …, k_{ρ}) := \{ \begin{matrix}the number of factorisations \\ τ_{1} · τ_{2} · . . . · τ_{n+ρ−2} = σ \\ of the permutation σ into a product of \\ transpositions τ_{i} of \{1, 2, …, n\}, \\ where ⟨τ_{1}, …, τ_{n+ρ−2}⟩ = S_{n} \end{matrix}

It is obvious that f(k_{1}, …, k_{ρ}) only depends on the type \underline{k} and that it is a symmetric function of the variables k_{1}, …, k_{ρ}.

The following special cases have appeared in the literature:

\underline{k} = (n) : f(n) = n^{n−2}  (Dénes [7])
\underline{k} = (\underbrace{1, …, 1}_{n}) : f(1^{n}) = (2n − 2)! n^{n−3}  (Crescimanno, Taylor [6])

\underline{k} = (p, q) : f(p, q) = p^{p} q^{q} \frac{(p + q − 1)!}{(p − 1)! (q − 1)!}  (Arnol’d [2])

Quite recently the general solution to our problem has been published by Goulden and Jackson in [12]:

Theorem 3

f(k_{1}, …, k_{ρ}) = (n + ρ − 2)! · n^{ρ−3} \frac{k_{1}^{k_{1}+1} ⋯ k_{ρ}^{k_{ρ}+1}}{k_{1}! ⋯ k_{ρ}!}  (1)

In the following, it will be instructive to take a look at the Goulden— 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 Poulalhon [17]).

The combinatorial picture is quite obvious: let τ_{1}, …, τ_{μ−1}, τ_{μ} be a minimal transitive sequence of transpositions on {1, 2, …, n}, then there are two possibilities:

• τ_{μ} is a “split”:

this means that the sequence τ_{1}, …, τ_{μ−1} is already minimal transitive on {1, 2, …, n} and τ_{μ} decomposes a cycle of length i + j of τ_{1} ∘ … ∘ τ_{μ−1} into a cycle of length i and a cycle of length j.

• τ_{μ} is a “join”:

this means that the graph G_{τ_{1},... ,τ_{μ−1}} has two connected components, A and B, say, such that A ⊎ B = {1, 2, …, n}, such that τ_{1}, …, τ_{μ−1} is a shuffle of the two subsequences τ′_{1}, …, τ′_{μ′}, minimal transitive on A, and τ′′_{1}, …, τ′′_{μ′′}, minimal transitive on B. Here τ_{μ} joins a cycle of length i of τ′_{1} ∘ … ∘ τ′_{μ′} and a cycle of length j of τ′′_{1} ∘ … ∘ τ′′_{μ′′} into a cycle of length i + j of τ_{1} ∘ … ∘ τ_{μ−1}

Now introduce commuting variables p_{1}, p_{2}, p_{3}, … and for any composition \underline{k} = (k_{1}, …, k_{ρ}) put p\underline{k} := p_{k_{1}} · . . . · p_{k_{ρ}}. Correspondingly, for any permutation σ of type \underline{k} we put p_{σ} := p\underline{k} and for any sequence of transpositions τ_{1}, …, τ_{μ} we consider the weight function

w(τ_{1}, …, τ_{μ}) := \frac{t^{μ}}{μ!} p_{τ_{1}∘...∘τ_{μ}}

The main object of study is now the generating function

F̃ = F̃(p_{1}, p_{2}, …; z, t) ∑_{n≥1} \frac{z^{n}}{n!} := ∑_{τ_{1},... ,τ_{μ} m.t.} w(τ_{1}, …, τ_{μ})

where the inner summation runs over all minimal transitive sequences of transpositions on {1, 2, …, n}.

It is not difficult to see that the above combinatorial consideration materializes into the following partial differential equation:

Lemma 4

\frac{∂F̃}{∂t} = \frac{1}{2} ∑_{i,j} \underbrace{p_{i+j} · i · \frac{∂F̃}{∂p_{i}} · j · \frac{∂F̃}{∂p_{j}}}_{τ_{μ} join} + \underbrace{p_{i} · p_{j} · (i + j) · \frac{∂F̃}{∂p_{i+j}}}_{τ_{μ} split}

Putting t = 1 this turns into Corollary 5 For F = F (p_{1}, p_{2}, …; z) := F̃(p_{1}, p_{2}, …; z, 1)

z \frac{∂F}{∂z} + ∑_{i} p_{i} \frac{∂F}{∂p_{i}} − 2 F =

= \frac{1}{2} ∑_{i,j} p_{i+j} · i · \frac{∂F}{∂p_{i}} · j · \frac{∂F}{∂p_{j}} + p_{i} · p_{j} · (i + j) · \frac{∂F}{∂p_{i+j}}

since μ = n + ρ − 2 and ρ = ∑_{j} k_{j} = ∑_{i} \underbrace{#\{j; k_{j} = i\}}_{=: ℓ_{i}}

Now we put for any composition \underline{k} = (k_{1}, …, k_{ρ}) :

σ(\underline{k}) := the number of permutations of type \underline{k}
= \frac{n!}{k_{1} · . . . · k_{ρ} · ℓ_{1}! · . . . · ℓ_{n}!}
π(\underline{k}) := the number of partitions of type \underline{k}
= \frac{n!}{k_{1}! · . . . · k_{ρ}! · ℓ_{1}! · . . . · ℓ_{n}!}
μ(\underline{k}) := ∑_{i} k_{i} + ρ − 2 = n + ρ − 2

where ℓ_{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}, …; z) = ∑_{n≥1} \frac{z^{n}}{n!} ∑_{\underline{k} ⊢ n} \frac{σ(\underline{k}) · f(\underline{k})}{μ(\underline{k})!} p\underline{k}

Now, if we define

G(p_{1}, p_{2}, …; z) = ∑_{n≥1} \frac{z^{n}}{n!} ∑_{\underline{k} ⊢ n} n^{ρ−3} ∏_{j=1}^{ρ} k_{j}^{k_{j}} · π(\underline{k}) p\underline{k}

then one has to show that

F (p_{1}, p_{2}, …; z) = G(p_{1}, p_{2}, …; z)

i.e., one has to show that

G = ∑_{n≥1} \frac{z^{n}}{n!} · \frac{1}{n^{3}} [\frac{y^{n}}{n!} ] exp (n · ∑_{i} \frac{i^{i}}{i!} p_{i} y^{i})
= ∑_{n≥1} \frac{z^{n}}{n^{3}} [y^{n}] exp (n · ∑_{i} \frac{i^{i}}{i!} p_{i} y^{i})

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 … ”.

Goulden–Jackson proceed by introducing the function

ϕ(y) := exp (n · ∑_{i} \frac{i^{i}}{i!} p_{i} y^{i})

and they let w = w(p_{1}, p_{2}, …; y) denote the solution of the implicit equation

w = z · ϕ(w)

Then, by Lagrange’s formula, applied to log(y/z), it turns out that G can be written as

G = ∑_{n≥1} \frac{z^{n}}{n^{2}} [z^{n}] ∑_{i≥1} \frac{i^{i}}{i!} p_{i} w^{i}

Goulden-Jackson go on and derive various formulas for

\frac{∂w}{∂p_{k}} , \frac{∂w}{∂z} , \frac{∂G}{∂z} , \frac{∂^{2}G}{∂z∂p_{k}} , \frac{∂G}{∂p_{k}} …

in terms of implicitly defined function w, such as

z \frac{∂G}{∂z} = ∑_{i≥1} \frac{i^{i−1}}{i!} p_{i} w^{i} − \frac{1}{2} (∑_{i≥1} \frac{i^{i}}{i!} p_{i}w^{i})^{2}

which they use to show that G (and F, of course) satisfy

(z \frac{∂}{∂z} ) (z \frac{∂Y}{∂z} + ∑_{i} p_{i} \frac{∂Y}{∂p_{i}} − 2 Y ) =

= (z \frac{∂}{∂z} ) \frac{1}{2} \{∑_{i,j} p_{i+j} · i · \frac{∂Y}{∂p_{i}} · j · \frac{∂Y}{∂p_{j}} + p_{i} · p_{j} · (i + j) · \frac{∂Y}{∂p_{i+j}} \}

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

Lemma 6 Let

S_{m} := ∑_{\begin{matrix}i,j≥1 \\ i+j=m \end{matrix}} \frac{i^{i}}{i!} \frac{j^{j−1}}{j!}

Then

S_{m} = \frac{m^{m}}{m!} − \frac{m^{m−1}}{m!}

This (easy) statement is in fact a version of Abel’s binomial theorem. Quite a bit more intricate is

Lemma 7 Let

T_{k,m} := \frac{k^{k+1}}{k!} ∑_{\begin{matrix}i≥1,j≥0 \\ i+j=m \end{matrix}} \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)!}

As a matter of fact, the main result (1) was already presented as early as 1891 by Hurwitz in his big article ([14], p. 21). Indeed, Hurwitz does not present a complete proof, he only mentions that he has been guided to formulate (1) as a conjecture as the result of a very laborious induction (...durch eine sehr mühsame Induktion zu der Vermutung geführt...), 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

f(k_{1}, …, k_{ρ}) =

∑_{1≤i<j≤ρ} k_{i} k_{j} f(…, k_{i} + k_{j}, …) + \frac{1}{2} ∑_{1≤i≤ρ} k_{i} ∑_{r=1}^{k_{i}−1} Φ_{r}(k_{i}|k_{1}, …, k̂_{i}, … k_{ρ}) (2)

where

Φ_{r}(k_{i}|k_{1}, …, k̂_{i}, … k_{ρ}) = ∑_{(α,β)} \frac{(n + ρ − 3)!}{σ! τ!} f(r, k_{α_{1}}, …, k_{α_{λ}}) f(s, k_{β_{1}}, …, k_{β_{μ}})

Here k̂_{i} indicates that the term k_{i} is missing. The summation in ∑_{(α,β)} runs over all decompositions of {1, 2, …, ρ} \ {i} into two disjoint subsets {α_{1}, …, α_{λ}} , {β_{1}, …, β_{μ}} where

s = k_{i} − r
ρ = λ + μ + 1
σ = r + k_{α_{1}} + … + k_{α_{λ}} + λ − 1
τ = s + k_{β_{1}} + … + k_{β_{μ}} + μ − 1
σ + τ = n + λ + μ − 2 = n + ρ − 3

Since the solution of the recurrence equation (2) is determined once the initial value f(1) = 1 has been fixed, it suffices, as remarked by Hurwitz, that after substituting (1) 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 (6),(7) below.

It is the purpose of this present note to carry through this proposal by Hurwitz and thus, ,in a sense, to reconstruct Hurwitz’ proof of (1).

The assertion to be proved reads

(n + ρ − 2)! · n^{ρ−3} \frac{k_{1}^{k_{1}+1} ⋯ k_{ρ}^{k_{ρ}+1}}{k_{1}! ⋯ k_{ρ}!}

= ∑_{i<j} k_{i} · k_{j} · (n + ρ − 3)! · n^{ρ−4} \frac{k_{1}^{k_{1}+1} ⋯ (k_{i} + k_{j})^{k_{i}+k_{j}+1} ⋯ k_{ρ}^{k_{ρ}+1}}{k_{1}! ⋯ (k_{i} + k_{j})! ⋯ k_{ρ}!}

+ \frac{1}{2} ∑_{i} k_{i} ∑_{r=1}^{k_{i}−1} ∑_{(α,β)}(n + ρ − 3)! (σ − λ + 1)^{λ−2}(τ − μ + 1)^{μ−2} ×

×\frac{r^{r+1}k_{α_{1}}^{k_{α_{1}}+1} ⋯ k_{α_{λ}}^{k_{α_{λ}}+1} · s^{s+1}k_{β_{1}}^{k_{β_{1}}+1} ⋯ k_{β_{μ}}^{k_{βμ}+1}}{r! k_{α_{1}}! ⋯ k_{α_{λ}}! s! k_{β_{1}}! ⋯ k_{β_{μ}}!}

Dividing both sides by

(n + ρ − 3)! · n^{ρ−4} \frac{k_{1}^{k_{1}+1} ⋯ k_{ρ}^{k_{ρ}+1}}{k_{1}! ⋯ k_{ρ}!}

one obtains

(n + ρ − 2) · n = ∑_{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−ρ}}{2} ∑_{i} k_{i} ∑_{r=1}^{k_{i}−1} ∑_{(α,β)}(σ − λ + 1)^{λ−2}(τ − μ + 1)^{μ−2} \frac{r^{r+1} s^{s+1} k_{i}!}{r! s! k_{i}^{k_{i}+1}}

= ∑_{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−ρ}}{2} ∑_{i} \frac{k_{i}!}{k_{i}^{k_{i}}} ∑_{r=1}^{k_{i}−1} \frac{r^{r+1}s^{s+1}}{r! s!} F_{−2,−2}(r, s | k_{1}, …, k̂_{i}, …, k_{ρ}) (3)

where the following notation is used

F_{r,s}(u, v | x_{1}, …, x_{n}) := ∑_{(α,β)}(u + x_{α_{1}} + … + x_{α_{λ}})^{r+λ}(v + x_{β_{1}} + … + x_{β_{μ}})^{s+μ}

using the same convention as above, i.e., the Σ_{α,β} runs over all decompositions {α_{1}, …, α_{λ}}, {β_{1}, …, β_{μ}} of {1, …, n}, where 0 ≤ λ ≤ n and μ = n − λ.

These functions have been investigated by Hurwitz in [15]. He uses in particular

F_{r,s} = u · F_{r−1,s} + ∑_{k=1}^{n} x_{k} · F_{r,s}(u + x_{k}, v | x_{1}, …, x̂_{k}, …, x_{n})  (4)

and similarly

F_{r,s} = v · F_{r,s−1} + ∑_{k=1}^{n} x_{k} · F_{r,s}(u, v + x_{k} | x_{1}, …, x̂_{k}, …, x_{n})  (5)

and he evaluates the following special cases (see also [5])

F_{−1,−1}(u, v | x_{1}, …, x_{n}) = (\frac{1}{u} + \frac{1}{v}) (u + v + x_{1} + … + x_{n})^{n−1} (6)
F_{−1,0}(u, v | x_{1}, …, x_{n}) = \frac{1}{u} · (u + v + x_{1} + … + x_{n})^{n}  (7)

the second of which is a generalization of Abel’s celebrated generalization [1] of the binomial identity:

∑_{λ=0}^{n} \binom{n}{λ}(u + λ x)^{λ−1}(v − λ x)^{n−λ} = \frac{1}{u} · (u + v)^{n}  (8)

A combinatorial treatment of identity (8) by Abel, of identities (6),(7) by Hurwitz, and of many other generalisations of Abel’s binomial identity has been given by the present author in [18].

From (4) and (5) one obtains

r · F_{−2,−2}(r, s | k_{1}, …, k̂_{i}, …, k_{ρ}) = F_{−1,−2}(r, s | k_{1}, …, k̂_{i}, …, k_{ρ})

− ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} k_{j} · F_{−1,−2}(r + k_{j}, s | k_{1}, …, k̂_{i}, …, k̂_{j}, …, k_{ρ})

and r · s · F_{−2,−2}(r, s | k_{1}, …, k̂_{i}, …, k_{ρ})

= s · F_{−1,−2}(r, s | k_{1}, …, k̂_{i}, …, k_{ρ})

− ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} k_{j} · s · F_{−1,−2}(r + k_{j}, s | k_{1}, …, k̂_{i}, …, k̂_{j}, …, k_{ρ})

= F_{−1,−1}(r, s | k_{1}, …, k̂_{i}, …, k_{ρ})

− ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} k_{j} · F_{−1,−1}(r, s + k_{j} | k_{1}, …, k̂_{i}, …, k̂_{j}, …, k_{ρ})

− ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} k_{j} · F_{−1,−1}(r + k_{j}, s | k_{1}, …, k̂_{i}, …, k̂_{j}, …, k_{ρ})

+ ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} ∑_{\begin{matrix}l=1 \\ l≠i,j \end{matrix}}^{ρ} k_{j} · k_{ℓ} · F_{−1,−1}(r + k_{j}, s + k_{ℓ} | k_{1}, …, k̂_{i}, …, k̂_{j}, …, k̂_{ℓ}, …, k_{ρ})

and the evaluation of F_{−1,−1} mentioned in (6) leads to r · s · F_{−2,−2}(r, s | k_{1}, …, k̂_{i}, …, k_{ρ})

= n^{ρ−2} (\frac{1}{r} + \frac{1}{s}) − ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} k_{j} · n^{ρ−3} (\frac{1}{r} + \frac{1}{s + k_{j}} )

− ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} k_{j} · n^{ρ−3} (\frac{1}{r + k_{j}} + \frac{1}{s}) + ∑_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{ρ} ∑_{\begin{matrix}ℓ=1 \\ ℓ≠j,i \end{matrix}}^{ρ} k_{j} · k_{ℓ} · n^{ρ−4} (\frac{1}{r + k_{j}} + \frac{1}{s + k_{ℓ}} )

= n^{ρ−2} (\frac{1}{r} + \frac{1}{s}) − n^{ρ−3} \frac{n − k_{i}}{r} − n^{ρ−3} \frac{n − k_{i}}{s}

− n^{ρ−3} ∑_{j≠i} \frac{k_{j}}{s + k_{j}} − n^{ρ−3} ∑_{j≠i} \frac{k_{j}}{r + k_{j}}

+ n^{ρ−4} ∑_{\begin{matrix}j,ℓ \\ j≠ℓ≠i≠j \end{matrix}} k_{j} · k_{ℓ} (\frac{1}{r + k_{j}} + \frac{1}{s + k_{j}} )

= n^{ρ−3} · k_{i} (\frac{1}{r} + \frac{1}{s}) − n^{ρ−3} ∑_{j≠i} (\frac{k_{j}}{s + k_{j}} + \frac{k_{j}}{r + k_{j}} )

+ n^{ρ−4} (∑_{j,ℓ} \frac{k_{j}}{r + k_{j}} (n − k_{i} − k_{j}) + ∑_{j,ℓ} \frac{k_{ℓ}}{s + k_{ℓ}} (n − k_{i} − k_{ℓ}))

= n^{ρ−3} · k_{i} · (\frac{1}{r} + \frac{1}{s}) − n^{ρ−4} (∑_{j≠i} \frac{k_{j} (k_{i} + k_{j})}{r + k_{j}} + ∑_{ℓ≠i} \frac{k_{ℓ} (k_{i} + k_{ℓ})}{s + k_{ℓ}})

Thus the second sum on the r.h.s. of (3) equals

\frac{n}{2} ∑_{i} \frac{k_{i}!}{k_{i}^{k_{i}−1}} ∑_{r=1}^{k_{i}−1} (\frac{1}{r} + \frac{1}{s}) \frac{r^{r}}{r!} \frac{s^{s}}{s!}

−\frac{1}{2} ∑_{i} \frac{k_{i}!}{k_{i}^{k_{i}}} ∑_{r=1}^{k_{i}−1} (∑_{j≠i} \frac{k_{j}(k_{i} + k_{j})}{r + k_{j}} + ∑_{ℓ≠i} \frac{k_{ℓ}(k_{i} + k_{ℓ})}{s + k_{ℓ}})

= n · ∑_{i}(k_{i} − 1) − ∑_{i} \frac{1}{k_{i}^{k_{i}}} ∑_{j≠i} k_{j}(k_{i} + k_{j}) ∑_{r=1}^{k_{i}−1} \binom{k_{i}}{r, s}\frac{1}{r + k_{j}} r^{r}s^{s}
= n · (n − ρ) − ∑_{i} …

where the first equality uses the known identity

∑_{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 [12], here mentioned as Lemma 6, and which is in fact an immediate consequence of Abel’s binomial identity (8).

The identity to be verified now reads

2 n (ρ − 1) =

∑_{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})!} − ∑_{i} \frac{1}{k_{i}^{k_{i}}} ∑_{j≠i} k_{j}(k_{i} + k_{j}) ∑_{r=1}^{k_{i}−1} \binom{k_{i}}{r, s}\frac{1}{r + k_{j}} r^{r} s^{s} (9)

It obviously suffices to prove this in the special case ρ = 2, i.e.,

2 (a + b) = \frac{(a + b)^{a+b+1} a! b!}{a^{a} b^{b} (a + b)!}

− \frac{b(a + b)}{a^{a}} ∑_{r=1}^{a−1} \binom{a}{r, s}\frac{1}{r + b} r^{r} s^{s} − \frac{a(a + b)}{b^{b}} ∑_{r=1}^{b−1} \binom{b}{r, s}\frac{1}{r + a} r^{r} s^{s} (10)

because summing the \binom{ρ}{2} equalities (10) for a = k_{i}, b = k_{j} with 1 ≤ i < j ≤ ρ yields (9) since

∑_{1≤i<j≤ρ}(k_{i} + k_{j}) = (ρ − 1)(k_{1} + … + k_{n}) = (ρ − 1) · n

(10) is obviously equivalent to

\frac{(a + b)^{a+b} a! b!}{a^{a} b^{b} (a + b)!} = \frac{b}{a^{a}} ∑_{r=0}^{a−1} \binom{a}{r, s}\frac{1}{r + b} r^{r} s^{s} + \frac{a}{b^{b}} ∑_{r=0}^{b−1} \binom{b}{r, s}\frac{1}{r + b} r^{r} t^{t} (11)

with s = a − r in the first sum and t = b − r in the second. Setting

T_{k,m} := \frac{k^{k+1}}{k!} ∑_{\begin{matrix}i≥1,j≥0 \\ i+j=m \end{matrix}} \frac{i^{i} j^{j}}{i! j!} · \frac{1}{k + j}

one has

\frac{b}{a^{a}} ∑_{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 (11) follows from

T_{k.m} + T_{m,k} = \frac{(k + m)^{k+m}}{(k + m)!}

which is proved by Goulden and Jackson in [12] using Lagrange inversion (Proposition 3.2, part 2, here Lemma 7), and which was most probably already known to Hurwitz. Thus (1) is proved.

References

[1] N.H. Abel, Beweis eines Ausdrucks von welchem die Binomial-Formel ein einzelner Fall ist. Crelles Journal für die Reine und Angewandte Mathematik, vol 1 (1826), 159-160.

[2] V. I. Arnol’d, Topological classifications of trigonometrical polynomials and combinatorics of graphs. Functional Analysis and its Applications, vol 30 (1996), 1-17.

[3] C. Berge, Principes de combinatoire. Dunod, Paris, 1968.

[4] P. Biane, Minimal factorizations of a cycle and central multiplicative functions on the infinite symmetric group. J. Combinatorial Theory, Series A, vol. 76 (1996), 197-212.

[5] L. Comtet, Advanced Combinatorics. D. Reidel Publ. Comp., Dordrecht, 1974.

[6] M. Crescimanno and W. Taylor, Large N phases of chiral QCD_{2}. Nuclear Phys. B, vol. 437 (1995), 3-24.

[7] J. Dénes, The representation of a permutation as the product of a minimal number of transpositions and its connection with the theory of graphs. Publ. Math. Inst. Hungar. Acad. Sci., vol. 4 (1959), 63-70.

[8] M. Eden and M.P. Schützenberger, Remark on a theorem of Dénes. Publ. Math. Inst. Hungar. Acad. Sci., vol. 7, ser. A (1962), 353-355.

[9] M. El Marraki, N. Hanusse, J. Zipperer and A. Zvonkin, Cacti, braids and complex polynomials. Séminaire Lotharingien de Combinatoire, vol. 37 (B37b)(1996), 36p.

[10] I.P. Goulden, A differential operator for symmetric functions and the combinatorics of multiplying transpositions. Trans. Amer. Math. Soc., vol. 344 (1994), 421-440.

[11] I.P. Goulden and D. Jackson, Symmetric functions and Macdonald’s result for top connexion coefficients in the symmetric group. J. Algebra, vol. 166 (1994), 364-378.

[12] I.P. Goulden and D.M. Jackson, Transitive factorisations into transpositions and holomorphic mappings on the sphere. Proc. Amer. Math. Soc., vol. 125 (1997), 51-60.

[13] I.P. Goulden and S. Pepper, Labelled trees and factorisations of a cycle into transpositions. Discrete Math., vol. 113 (1993), 263-268.

[14] A. Hurwitz, Über Riemann’sche Flächen mit gegebenen Verzweigungspunkten. Mathematische Annalen, vol. 39 (1891), 1-66.

[15] A. Hurwitz, Über Abels Verallgemeinerung der binomischen Formel. Acta Mathematica, vol. 26 (1902), 199-203.

[16] P. Moszkowski, A solution of a problem of Dénes, a bijection between trees and factorizations of cyclic permutations. European J. Combin., vol. 101 (1989), 13-16.

[17] D. Poulalhon, Graphes et décompositions de permutations. Mémoire de DEA, École Polytechnique, 1997.

[18] V. Strehl, Identities of Rothe-Abel-Schläfli-Hurwitz-type. Discrete Math., vol. 99 (1992), 321-340.