ON THE NUMBER OF EVEN PERMUTATIONS WITH ROOTS

M. R. POURNAKI

Abstract. Let π be an even permutation on n letters which has a root, that is, there exists an even permutation ξ such that π = ξ^{2}. In this article the number of this kind of π is found by using generating function techniques. This is the analogue of a result for the number of all permutations with roots.

1. Introduction and statement of the result

Let A_{n} be the group of all even permutations on n letters. We say that π ∈ A_{n} has a root, if there exists ξ ∈ A_{n} such that π = ξ^{2}. Clearly, a given π may have one or more roots, or it may have none. Let A_{n}^{2} be the set of all elements of A_{n} which have at least one root, that is, A_{n}^{2} = {ξ^{2} : ξ ∈ A_{n}}. In this article our central aim will be to find the number of elements of A_{n}^{2} by constructing a generating function of the sequence {|A_{n}^{2}|/n!}_{n≥2}. As usual, for a given finite set X, the number of elements of X is denoted by |X|. We recall that, by definition, f(t) is the generating function of the sequence {a_{n}}_{n≥l} if we can expand f(t) formally in the form ∑_{n=0}^{l−1} b_{n}t^{n} + ∑_{n=l}^{∞} a_{n}t^{n}. Therefore the formal power series of the generating function of a given sequence gives us the sequence. We can now state the main result of this article:

Theorem 1.1. The generating function of the sequence {|A_{n}^{2}|/n!}_{n≥2} is

f(t) = (\frac{1 + t}{1 − t})^{\frac{1}{2}} ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m} ) − \frac{1}{2}( ∏_{m=1}^{∞} (1 + \frac{t^{2m−1}}{2m − 1}))( ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m} ) − ∏_{m=1}^{∞} cos (\frac{t^{2m}}{2m} )).

Using Theorem 1.1, the first terms of the Taylor series expansion of f(t),

1 + t + \frac{1}{2}t^{2} + \frac{1}{2}t^{3} + \frac{3}{8}t^{4} + \frac{3}{8}t^{5} + \frac{3}{8}t^{6} + \frac{1}{3}t^{7} + \frac{9}{32}t^{8} + \frac{143}{480}t^{9} + ⋯,

give us the first terms of the sequence {|A_{n}^{2}|}_{n≥2}:

1, 3, 9, 45, 270, 1680, 11340, 108108, ….

The number of all permutations with roots is already computed by constructing a generating function of the sequence {|S_{n}^{2}|/n!}_{n≥1}, where S_{n}^{2} = {σ^{2} : σ ∈ S_{n}}. In fact, in [5, Page 148], the generating function of the sequence {|S_{n}^{2}|/n!}_{n≥1} is given by the function

2000 Mathematics Subject Classification. 05A05, 05A15.

Key words and phrases. Even permutation, Generating function.

The research of the author was in part supported by a grant from IPM (No. 84200111).

(\frac{1 + t}{1 − t})^{\frac{1}{2}} ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m}).

Therefore our result is an analogue of such a classical formula. Note that |S_{n}^{2}|/n! =: P_{n}, n ≥ 1, is the probability that a randomly chosen permutation on n letters has a root and therefore this latter function is in fact the generating function of this probability. The first terms of the Taylor series expansion of this latter function,

1 + t + \frac{1}{2}t^{2} + \frac{1}{2}t^{3} + \frac{1}{2}t^{4} + \frac{1}{2}t^{5} + \frac{3}{8}t^{6} + \frac{3}{8}t^{7} + \frac{7}{20}t^{8} + \frac{7}{20}t^{9} + ⋯,

now give us the first terms of the probability sequence {P_{n}}_{n≥1}:

1, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{3}{8}, \frac{3}{8}, \frac{7}{20}, \frac{7}{20}, ….

The properties of {P_{n}}_{n≥1} have been studied by some authors. Asymptotic properties of {P_{n}}_{n≥1} were studied in [1], [2], [4] and in [3]; the latter is devoted to the proof of a conjecture of Wilf [5] that {P_{n}}_{n≥1} is monotonically non-increasing.

Using Theorem 1.1 the analogue result for P_{n} := 2|A_{n}^{2}|/n!, n ≥ 2, the probability that a randomly chosen even permutation on n letters has a root can be calculated:

Corollary 1.2. The generating function of the sequence {P_{n}}_{n≥2} is

g(t) = 2(\frac{1 + t}{1 − t})^{\frac{1}{2}} ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m} ) − ( ∏_{m=1}^{∞} (1 + \frac{t^{2m−1}}{2m − 1}))( ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m} ) − ∏_{m=1}^{∞} cos (\frac{t^{2m}}{2m} )).

The first terms of the Taylor series expansion of g(t),

2 + 2t + t^{2} + t^{3} + \frac{3}{4}t^{4} + \frac{3}{4}t^{5} + \frac{3}{4}t^{6} + \frac{2}{3}t^{7} + \frac{9}{16}t^{8} + \frac{143}{240}t^{9} + ⋯,

now give us the first terms of the probability sequence {P_{n}}_{n≥2}:

1, 1, \frac{3}{4}, \frac{3}{4}, \frac{3}{4}, \frac{2}{3}, \frac{9}{16}, \frac{143}{240}, ….

We now consider the asymptotics of {P_{n}}_{n≥2}, as done for {P_{n}}_{n≥1} in [3], that is, lim_{n→+∞} P_{n} = 0. To do so, note that A_{n}^{2} is a subset of S_{n}^{2}, so |A_{n}^{2}| ≤ |S_{n}^{2}| and hence P_{n} ≤ 2P_{n}. Now lim_{n→+∞} P_{n} = 0 implies that lim_{n→+∞} P_{n} = 0.

Note that there are some results for {P_{n}}_{n≥1} which have no analogue for {P_{n}}_{n≥2}. For example, P_{2n} = P_{2n+1} holds true for all n ≥ 1 (see [5, Page 148]), but from the first terms of the sequence {P_{n}}_{n≥2}, we see that the above fails in this case. In fact, for example, P_{6} ≠ P_{7}.

2. Proof of the main result

In the following for a given σ ∈ S_{n}, c(σ)_{i} denotes the number of cycles of length i in the disjoint cycle decomposition of σ.

Consider π as a permutation on n letters. Suppose that π ∈ A_{n}^{2}. Take a ξ ∈ A_{n} with π = ξ^{2}. Clearly, the square of a cycle of length k is a cycle of length k if k is odd, and is the product of two cycles of lengths k/2 if k is even. Therefore a cycle of length 2k in π can only be obtained by squaring a cycle of length 4k of ξ. This gives the product of two cycles of lengths 2k in π. Therefore c(π)_{2k} is even. Now suppose for each j, we have c(π)_{2j−1} ≤ 1. Then the disjoint cycle decomposition of π will consist of l = ∑_{k} c(π)_{2k} cycles of even order of lengths 2k_{1}, …, 2k_{l} and possibly some cycles of odd length, each length 2j − 1 appearing only once. Therefore ξ consists of l/2 cycles of lengths 4k_{1}, …, 4k_{l/2} and maybe some cycles of odd length. Since ξ ∈ A_{n}, l/2 is even, it follows that l = ∑_{k} c(π)_{2k} is a multiple of 4. In fact, we have just proved that if π ∈ A_{n}^{2}, then we have

(1) c(π)_{2k} is even for all k, and

(2) l = ∑_{k} c(π)_{2k} is a multiple of 4 or c(π)_{2j−1} > 1 for some j.

We now prove that the converse of the above argument is also true. More precisely, we prove that if both of the conditions (1) and (2) hold true for a given π, then we have π ∈ A_{n}^{2}. To do so, first consider the following two constructions. If a cycle (a_{1} a_{2} a_{3} … a_{k}) has an odd length, then it is the square of the cycle (b_{1} b_{2} b_{3} … b_{k}), where b_{1} = a_{1}, b_{3} = a_{2}, b_{5} = a_{3}, …, and the subscripts are taken modulo k. Thus, any cycle of odd length is the square of a cycle of the same length. Moreover, for any two cycles (a_{1} a_{2} … a_{k}) and (b_{1} b_{2} … b_{k}) of the same arbitrary length, consider (a_{1} b_{1} a_{2} b_{2} … a_{k} b_{k}). Then (a_{1} b_{1} a_{2} b_{2} … a_{k} b_{k})^{2} = (a_{1} a_{2} … a_{k})(b_{1} b_{2} … b_{k}). Therefore the product of two cycles of the same length is the square of a single cycle of doubled length. Now suppose π has properties (1) and (2) as in the assertion. We shall construct ξ ∈ A_{n} such that π = ξ^{2}. According to (1), we can write π as the product of an even number of cycles of even lengths and some number of cycles of odd length. Divide these cycles of even length into groups of two cycles of equal length, using the scheme explained above. Now if l = ∑_{k} c(π)_{2k} = 4s for some s, this product of cycles can be represented as the square of l/2 cycles of even length. Similarly, each of the cycles of odd length is the square of a cycle of the same length. Therefore we obtain a permutation ξ such that π = ξ^{2} and ξ has l/2 cycles of even length and some cycles of odd length, so ξ ∈ A_{n}. Otherwise, if l = ∑_{k} c(π)_{2k} = 4s + 2 for some s, then by (2), there are at least two cycles of the same odd length, say 2j − 1. Now divide the cycle decomposition of π into the following groups: groups of two cycles of equal even lengths (there are l/2 such groups), a group of two cycles of length 2j − 1, and the rest, which are of odd length. Each of these groups is a square of a cycle, but note in particular that we write the two cycles of length 2j − 1 as the square of a single cycle of length 4j − 2, while we write the other cycles of odd length as the square of a cycle of the same length. Thus, we obtain ξ such that π = ξ^{2} and ξ consists of l/2 cycles of even length, another cycle of length 4j − 2 (even), and some cycles of odd length, so ξ ∈ A_{n}.

Therefore we obtain the following characterization for the elements of A_{n}^{2}. We have π ∈ A_{n}^{2} if and only if the following two conditions are satisfied:

(1) c(π)_{2k} is even for all k, and

(2) l = ∑_{k} c(π)_{2k} is a multiple of 4 or c(π)_{2j−1} > 1 for some j.

Here we illustrate this fact by a simple example. Consider π as a permutation on 9 letters:

π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 2 & 8 & 1 & 7 & 6 & 9 & 3 & 5 \end{matrix} ) .

The disjoint cycle decomposition of π is π = (2)(6)(1 4)(3 8)(5 7 9). Therefore for this permutation we have c(π)_{1} = 2, c(π)_{2} = 2 and c(π)_{3} = 1. Since c(π)_{2} is even and c(π)_{1} > 1, both of the above conditions are satisfied and therefore π ∈ A_{9}^{2}. In fact, here we have π = ((2 6)(1 3 4 8)(5 9 7))^{2}.

Consider the cycle type vector (c(σ)_{1}, c(σ)_{2}, …) of the permutation σ of n letters. By Theorem 4.7.2 of [5, Page 143], the coefficient of

( ∏_{m=1}^{n} x_{m}^{c(σ)_{m}})\frac{t^{n}}{n!}

in the product

∏_{m=1}^{∞} exp(x_{m} \frac{t^{m}}{m})

is the number of permutations of n letters whose cycle type is (c(σ)_{1}, c(σ)_{2}, …). The infinite products and infinite sums occurring in the assertion and in the present proof are considered as elements of the ring ℂ[x_{1}, x_{2}, …][[t]] of formal power series in the variable t over the polynomial ring ℂ[x_{1}, x_{2}, …] in infinitely many variables x_{1}, x_{2}, …. The elements exp, cosh, and cos are certain formal power series, which coincide with those derived by the Taylor expansion of corresponding analytical functions. Using this, it is easily checked that all products and sums occurring here are indeed welldefined.

We calculate |S_{n}^{2} \ A_{n}^{2}|. By the mentioned characterization for the elements of A_{n}^{2}, σ ∈ S_{n}^{2} \ A_{n}^{2} if and only if c(σ)_{2k} is even for all k, c(σ)_{2j−1} is 0 or 1 for all j, and the number of cycles of even length is 2 (mod 4). Therefore with an argument similar to that in [5, Page 147], one can obtain the generating function of the sequence {|S_{n}^{2} \ A_{n}^{2}|}_{n≥2}. As c(σ)_{2k} should be even for all k and c(σ)_{2j−1} ≤ 1 for all j, the terms exp (x_{m}t^{m}/m) in the product

∏_{m=1}^{∞} exp (x_{m} \frac{t^{m}}{m} )

should be replaced by 1 + x_{m}t^{m}/m and cosh (x_{m}t^{m}/m) for odd and even m’s, respectively. The obtained expression is

( ∏_{m=1}^{∞} (1 + x_{2m−1} \frac{t^{2m−1}}{2m − 1}))( ∏_{m=1}^{∞} cosh (x_{2m} \frac{t^{2m}}{2m})).

To impose condition ∑_{m} c(σ)_{2m} ≡ 2 (mod 4), we need some more tricks. Replacing each x_{2m} in

∏_{m=1}^{∞} cosh (x_{2m} \frac{t^{2m}}{2m})

by sx_{2m}, it is trivial that we only need to compute powers of s of the form s^{4l−2} in

F (t, s) = ∏_{m=1}^{∞} cosh (x_{2m} \frac{st^{2m}}{2m} ).

But since F contains only even powers of s, it is enough to compute powers of s in

\frac{1}{2}(F (t, s) − F (t, is)) = \frac{1}{2}( ∏_{m=1}^{∞} cosh (x_{2m} \frac{st^{2m}}{2m} ) − ∏_{m=1}^{∞} cos (x_{2m} \frac{st^{2m}}{2m} )).

Now if we replace s by 1, we obtain the generating function of {|S_{n}^{2} \ A_{n}^{2}|}_{n≥2}:

( ∏_{m=1}^{∞} (1 + x_{2m−1} \frac{t^{2m−1}}{2m − 1}))(\frac{1}{2}(F (t, 1) − F (t, i))) =

\frac{1}{2}( ∏_{m=1}^{∞} (1 + x_{2m−1} \frac{t^{2m−1}}{2m − 1}))( ∏_{m=1}^{∞} cosh (x_{2m} \frac{t^{2m}}{2m}) − ∏_{m=1}^{∞} cos (x_{2m} \frac{t^{2m}}{2m})).

Therefore |S_{n}^{2} \ A_{n}^{2}| for n ≥ 2 is equal to the coefficient of t^{n}/n! in

\frac{1}{2}( ∏_{m=1}^{∞} (1 + \frac{t^{2m−1}}{2m − 1}))( ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m}) − ∏_{m=1}^{∞} cos (\frac{t^{2m}}{2m})).

On the other hand, by [5, Page 148], |S_{n}^{2}| for n ≥ 2 is equal to the coefficient of t^{n}/n! in

(\frac{1 + t}{1 − t})^{\frac{1}{2}} ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m}).

Hence, |A_{n}^{2}| for n ≥ 2 is equal to the coefficient of t^{n}/n! in

f(t) = (\frac{1 + t}{1 − t})^{\frac{1}{2}} ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m} ) − \frac{1}{2}( ∏_{m=1}^{∞} (1 + \frac{t^{2m−1}}{2m − 1}))( ∏_{m=1}^{∞} cosh (\frac{t^{2m}}{2m} ) − ∏_{m=1}^{∞} cos (\frac{t^{2m}}{2m} )).

Therefore f(t) is the generating function of the sequence {|A_{n}^{2}|/n!}_{n≥2} as required.

References

[1] E. A. Bender, Asymptotic methods in enumeration, SIAM Rev. 16 (1974), 485–515.

[2] J. Blum, Enumeration of the square permutations in S_{n}, J. Combinatorial Theory Ser. A 17 (1974), 156–161.

[3] M. Bóna, A. McLennan, D. White, Permutations with roots, Random Structures Algorithms 17 (2000), no. 2, 157–167.

[4] N. Pouyanne, On the number of permutations admitting an m-th root, Electron. J. Combin. 9 (2002), no. 1, Research Paper 3, 12 pp. (electronic).

[5] H. S. Wilf, Generatingfunctionology, Second Edition, Academic Press, Boston, MA, 1994.

M. R. Pournaki, Department of Mathematical Sciences, Sharif University of Technology, P.O. Box 11155-9415, Tehran, Iran, and School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran.

 E-mail address: pournaki@ipm.ir
 URL: http://math.ipm.ac.ir/pournaki/