Séminaire Lotharingien de Combinatoire 55 (2006), Article B55d

On the formula of Goulden and Rattan for Kerov polynomials

Philippe Biane

Abstract. We give a simple proof of an explicit formula for Kerov polynomials. This explicit formula is closely related to a recent formula of Goulden and Rattan.

1. Kerov polynomials

Kerov polynomials are universal polynomials which express the characters of symmetric groups evaluated on cycles, in terms of quantities known as the free cumulants of a Young diagram. We now explain these notions.

Let λ = λ_{1} ≥ λ_{2} ≥ ⋯ be a Young diagram, to which we associate a piecewise affine function ω : ℝ → ℝ, with slopes ±1, such that ω(x) = |x| for |x| large enough, as in Figure 1 below, which corresponds to the partition 8 = 4 + 3 + 1. We can encode the Young diagram using the local minima and local maxima of the function ω, denoted by x_{1}, …, x_{m} and y_{1}, …, y_{m−1} respectively, which form two interlacing sequences of integers. These are (−3, −1, 2, 4) and (−2, 1, 3) respectively in the picture. To the Young diagram we associate the rational fraction

G_{λ}(z) = \frac{∏_{i=1}^{m−1}(z − y_{i})}{∏_{i=1}^{m}(z − x_{i})}

and the formal power series K_{λ}, inverse to G for composition,

K_{λ}(z) = G_{λ}^{(−1)}(z) = z^{−1} + ∑_{k=2}^{∞} R_{k}(λ)z^{k−1}.

The quantities R_{k}(λ), k = 2, 3, …, are called the free cumulants of the diagram λ. Note that R_{1}(λ) = 0 for any Young diagram, so we do not include it in the series of free cumulants. These quantities arise in the asymptotic study of representations of symmetric groups, see [B1]. It turns out that there exist universal polynomials Σ_{2}, Σ_{3}, … in the

x_{1} y_{1} x_{2} y_{2} x_{3} y_{3} x_{4} Figure 1

variables R_{2}, R_{3}, … such that for any Young diagram λ the normalized character χ_{λ} evaluated at a cycle c_{k} of length k is given by

(n)_{k}χ_{λ}(c_{k}) = Σ_{k}(R_{2}(λ), R_{3}(λ), …).

The remarkable fact here is that these polynomials do not depend on the size of the symmetric group. We list the first such polynomials below.

Σ_{1} = R_{2},
Σ_{2} = R_{3},
Σ_{3} = R_{4} + R_{2},
Σ_{4} = R_{5} + 5R_{3},
Σ_{5} = R_{6} + 15R_{4} + 5R_{2}^{2} + 8R_{2}.

We refer to [B2] and [GR] for more information about results and conjectures on the coefficients of these polynomials. We take from [B2], Section 5, the following expression for Kerov polynomials. Here [z^{−k}] f(z) denotes the coefficient of z^{−k} (the residue if k = 1) of a Laurent series f(z).

Proposition 1.1. Consider the formal power series

H(z) = z − ∑_{j=2}^{∞} B_{j}z^{1−j}.

Define

Σ_{k} = −\frac{1}{k} [z^{−1}] H(z)H(z − 1) ⋯ H(z − k + 1)  (1)

and

R_{k+1} = −\frac{1}{k} [z^{−1}] H(z)^{k},  (2)

then the expression of Σ_{k} in terms of the R_{k} ′s is given by Kerov’s polynomials.

Recently I. P. Goulden and A. Rattan [GR] have given an explicit expression for Kerov polynomials, from which they have deduced a certain number of positivity properties of the coefficients of these polynomials. Their proof uses the Lagrange inversion formula. In the next section we use the invariance of the residue under change of variables to derive in a simple way a closely related formula, and show how to recover Goulden and Rattan’s formula.

2. Explicit expression for Kerov polynomials

We use the notations of Proposition 1.1 above. Let us introduce the power series

L(z) = z + ∑_{j=2}^{∞} R_{j}z^{1−j}.

From Equation (2) one gets H ∘ L(z) = z, by Lagrange inversion formula. We use the invariance of the residue under change of variables, namely if u, f are Laurent series, and if u is invertible for composition, then

[z^{−1}] f(z) = [ζ^{−1}] u′(ζ)f ∘ u(ζ).

Using Taylor’s formula about j = 0 for H(z − j) as well as the change of variables z = L(ζ) in the residue, one gets from (1) that

Σ_{k} = −\frac{1}{k} [z^{−1}] ∏_{j=0}^{k−1} (∑_{r=0}^{∞} \frac{(−j)^{r}}{r!} H^{(r)}(z))

= −\frac{1}{k} [ζ^{−1}] L′(ζ) ∏_{j=0}^{k−1} (∑_{r=0}^{∞} \frac{(−j)^{r}}{r!} H^{(r)} ∘ L(ζ)) .

Using H′ ∘ L(ζ) = \frac{1}{L′(ζ)}, one gets

H^{(r)} ∘ L(ζ) = (\frac{1}{L′(ζ)} \frac{d}{dζ} )^{r−1} \frac{1}{L′(ζ)}.

Therefore,

Σ_{k} = −\frac{1}{k} [ζ^{−1}] L′(ζ) ∏_{j=0}^{k−1} (ζ + ∑_{r=1}^{∞} \frac{(−j)^{r}}{r!} (\frac{1}{L′(ζ)} \frac{d}{dζ} )^{r−1} \frac{1}{L′(ζ)}) .

Putting F (ζ) = \frac{1}{L′(ζ)}, we obtain the following proposition.

Proposition 2.1. Let

F (ζ) = \frac{1}{L′(ζ)} = \frac{1}{1 − ∑_{k=2}^{∞}(k − 1)R_{k}ζ^{−k}} ,

then Kerov’s polynomials are given by the expression

Σ_{k} = −\frac{1}{k} [ζ^{−1}] \frac{1}{F (ζ)} ∏_{j=0}^{k−1} (ζ + ∑_{r=1}^{∞} \frac{(−j)^{r}}{r!} (F (ζ)\frac{d}{dζ} )^{r−1} F (ζ)) . (3)

3. The formula of Goulden and Rattan

Goulden and Rattan give various equivalent formulas for Σ_{k}. They introduce the series C(ζ) = F (ζ^{−1}), and define polynomials

P_{m}(z) = −\frac{1}{m!}C(z)(D + (m − 2)I) [C(z) ⋯ (D + I) [C(z)DC(z)] ⋯] ,

where D = z \frac{d}{dz}. The generating function form of their formula now reads

Σ_{k} = −\frac{1}{k}[z^{k+1}]\frac{1}{C(z)} ∏_{j=1}^{k−1}(1 + ∑_{i=1}^{∞} j^{i}P_{i}(z)z^{i}).

We recover this formula using (3). For this, we factor out ζ^{k} in the expression in the right-hand side of (3), and use the change of variable z = ζ^{−1}. This gives

Σ_{k} = −\frac{1}{k} [ζ^{−1−k}] \frac{1}{F (ζ)} ∏_{j=1}^{k−1} (1 + ∑_{r=1}^{∞} \frac{(−j)^{r}}{r!} ζ^{−1} (F (ζ)\frac{d}{dζ} )^{r−1} F (ζ))

= −\frac{1}{k} [z^{k+1}] \frac{1}{C(z)} ∏_{j=1}^{k−1} (1 + ∑_{r=1}^{∞} \frac{(−j)^{r}}{r!} z (−C(z)z^{2} \frac{d}{dz} )^{r−1} C(z))

= −\frac{1}{k} [z^{k+1}] \frac{1}{C(z)} ∏_{j=1}^{k−1} (1 − ∑_{r=1}^{∞} \frac{j^{r}z}{r!} (C(z)zD)^{r−1}C(z)) .

Now observe that z^{−j}Dz^{j} = D + jI, to get

z(C(z)zD)^{r−1}C(z)

= z^{r}C(z)(D + (r − 2)I) [C(z) ⋯ (D + I) [C(z)DC(z)] ⋯]

= −r!P_{r}(z).

References

[B1] P. Biane, Representations of symmetric groups and free probability. Adv. Math. 138 (1998), no. 1, 126–181.

[B2] P. Biane, Characters of symmetric groups and free cumulants. Asymptotic combinatorics with applications to mathematical physics (St. Petersburg, 2001), 185–200, Lecture Notes in Math., 1815, Springer, Berlin, 2003.

[GR] I. P. Goulden, A. Rattan, An explicit form for Kerov’s character polynomials.

math.CO/0505317.

CNRS, Département de Mathématiques et Applications, École Normale Supérieure, 45, rue d’Ulm 75005 paris, FRANCE

E-mail address: Philippe.Biane@ens.fr