On the Number of Factorizations of a Full Cycle

Abstract. We give a new expression for the number of factorizations of a full cycle into an ordered product of permutations of specified cycle types. This is done through purely algebraic means, extending recent work of Biane [Nombre de factorisations d’un grand cycle, Sém. Lothar. de Combinatoire 51 (2004)]. We deduce from our result a remarkable formula of Poulalhon and Schaeffer [Factorizations of large cycles in the symmetric group, Discrete Math. 254 (2002), 433–458] that was previously derived through an intricate combinatorial argument. Résumé. Nous proposons une nouvelle formule pour le nombre de factorisations d’un grand cycle en un produit ordonné de permutations de types cycliques donnés. Nous utilisons des arguments purement algébriques, étendant un travail récent de Biane [Nombre de factorisations d’un grand cycle., Sém. Lothar. de Combinatoire 51 (2004)]. Nous déduisons de notre résultat une formule remarquable de Poulalhon et Schaeffer [Factorizations of large cycles in the symmetric group, Discrete Math. 254 (2002), 433–458] obtenue précédemment à l’aide d’arguments combinatoires complexes. 1. Notation Our notation is generally consistent with Macdonald [5]. We write λ ⊢ n (or |λ | = n) and ℓ(λ) = k to indicate that λ is a partition of n into k parts; that is, λ = (λ1,..., λk) with λ1 ≥ · · · ≥ λk ≥ 1 and λ1+...+λk = n. If λ has exactly mi parts equal to i then we write λ = [1m12m2 · · ·], suppressing terms with mi = 0. We also define zλ = � i imimi! and Aut(λ) = � i mi!. A hook is a partition of the form [1b, a + 1] with a, b ≥ 0. We use Frobenius notation for hooks, writing (a|b) in place of [1b, a + 1]. The conjugacy class of the symmetric group Sn consisting of all n!/zλ permutations of cycle type λ ⊢ n will be denoted by Cλ. The irreducible characters χλ of Sn are naturally indexed by partitions λ of n, and we use the usual notation χλ µ for the common value of χλ at any element of Cµ. We write fλ for the degree χλ [1n] of χλ. For vectors j = (j1,...,jm) and x = (x1,..., xm) we use the abbreviations j! = j1! · · ·jm! and xj = x j1 1 · · · xjm m. Finally, if α ∈ Q and f ∈ Q[[x]] is a formal power series, then we write [αxj] f(x) for the coefficient of the monomial αxj in f(x)