Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On the number of permutations admitting an m-th root. | On the number of permutations admitting an m-th root Nicolas POUYANNE Departement de mathematiques Université de Versailles - Saint-Quentin 45 avenue des Etats-Unis 78035 Versailles Cedex pouyanne@ Submitted August 28 2001 Accepted December 20 2001. MR Subject Classification Primary 05A15 05A16 Secondary 68W40 Abstract Let m be a positive integer and pn m the proportion of permutations of the symmetric group n that admit an m-th root. Calculating the exponential generating function of these permutations we show the following asymptotic formula m Pn m m x n1- m m where is the Euler function and Km an explicit constant. 1. Introduction The question consists in estimating the number of permutations of the symmetric group n which admit an m-th root when n is large. Turán gave an upperbound when m is a prime number Tu and Blum found an asymptotically equivalent form for m 2 Bl . In the general case Bender applied a theorem of Hardy Littlewood and Karamata to the exponential generating function of these permutations to obtain an asymptotic equivalent of the partial sums of the required numbers Be . In BoMcLWh it is shown that the sequence tends monotonically to zero in the case when m is prime. Whether a permutation of n admits an m-th root can be read on the partition of n determined by the lengths of the permutation s cycles because the class of such THE electronic journal of combinatorics 9 2002 R3 1 permutations is stable under conjugacy in n. This characterisation already mentioned in Be is established in section 2. The computation of the exponential generating function EGF Pm of these permutations follows from the preceding result. This EGF splits in a natural way as a product of two others EGF Pm Cm X Rm- Singularity analysis provides the asymptotics of the coefficients of Cm 52n cn m Xn because Cm has a hnite number of algebraic singularities on its circle of convergence. This asymptotics turns to be of the following form . K-m cn m _T I m m 1 on 1 y
