Inversions of Permutations in Symmetric, Alternating, and Dihedral Groups

Dexter Jane L. Indong and Gilbert R. Peralta Department of Mathematics and Computer Science University of the Philippines Baguio Governor Pack Road Baguio City 2600 Philippines

                  dlindong@upb.edu.ph
                 grperalta@upb.edu.ph

Abstract

We use two methods to obtain a formula relating the total number of inversions of all permutations and the corresponding order of symmetric, alternating, and dihedral groups. First, we define an equivalence relation on the symmetric group S_{n} and consider each element in each equivalence class as a permutation of a proper subset of {1, 2, …, n}. Second, we look at certain properties of a backward permutation, a permutation obtained by reversing the row images of a given permutation. Lastly, we employ the first method to obtain a recursive formula corresponding to the number of permutations with k inversions.

1 Introduction

Let n be a positive integer and A be the finite set {1, 2, …, n}. The group of all permutations of A is the symmetric group on n elements and it is denoted by S_{n}. A permutation σ ∈ S_{n} can be represented by

σ = ( \begin{matrix}1 & 2 & ⋯ & n \\ σ(1) & σ(2) & ⋯ & σ(n) \end{matrix} ) .

Note that S_{n} has n! elements and the identity element is given by ι(i) = i for all i ∈ A.

An inversion induced by a permutation σ is an ordered pair (σ(i), σ(j)) such that i < j and σ(i) > σ(j). For purposes of computations later, we represent an inversion (σ(i), σ(j)) just by the ordered pair (i, j). The number of inversions of a permutation is a way to measure the extent to which the permutation is “out of order”. Inversions are important in sorting algorithms and have applications in computational molecular biology (see [1] for example).

If we let I(σ) be the set of all inversions of a permutation σ ∈ S_{n}, then

I(σ) = {(i, j) : σ(i) > σ(j), 1 ≤ i < j ≤ n}.  (1)

It now follows from Eq. (1) that if N(σ) is the number of all inversions induced by σ ∈ S_{n}, then N(σ) = |I(σ)|. Observe that the only permutation with no inversion is the identity permutation and so, N(σ) = 0 if and only if σ = ι. Further, the number of inversions of a permutation and its inverse are equal.

In general, to determine the total number of inversions of a permutation σ ∈ S_{n}, we count the number of j’s such σ(1) > σ(j) for 1 < j ≤ n, then the number of j’s such that σ(2) > σ(j) for 2 < j ≤ n, up to the number of j’s such that σ(n − 1) > σ(j) for n − 1 < j ≤ n, and thus, a formula for N(σ) is given by

N(σ) = ∑_{i=1}^{n−1} |{j : σ(i) > σ(j), i < j ≤ n}| .  (2)

Let β ∈ S_{n} be the permutation defined by

β = ( \begin{matrix}1 & 2 & ⋯ & n \\ n & n − 1 & ⋯ & 1 \end{matrix} ) .  (3)

Note that for 1 ≤ i ≤ n we have β(i) = n − i + 1. Thus, i < j implies that β(i) > β(j). It now follows that (i, j) ∈ I(β) for 1 ≤ i < j ≤ n and the permutation β defined by Eq. (3) gives the maximum number of inversions in any permutation. Hence,

max_{σ∈S_{n}} N(σ) = N(β) = ∑_{i=1}^{n−1}(n − i) = \binom{n}{2}.

For each positive integer n, if we let S_{n} be the total number of inversions of all permutations σ ∈ S_{n} then

S_{n} = ∑_{σ∈S_{n}} N(σ).  (4)

Using formulas (2) and (4) to determine S_{n} would take at most \binom{n}{2}n! steps and thus inefficient for large values of n. This paper introduces two methods to determine S_{n} and eventually use these methods to generate explicit formulas for the total number of inversions of all permutations to two specific subgroups of S_{n}, namely the alternating group A_{n} and the dihedral group D_{n}.

2 Partitioning the symmetric group

Let {a_{j}}_{j=1}^{n} be an increasing sequence of n distinct positive integers, that is, for j < k, we have a_{j} < a_{k}, and S({a_{j}}_{j=1}^{n}) be the group of all permutations of {a_{j}}_{j=1}^{n}. Notice that S({a_{j}}_{j=1}^{n}) ≃ S_{n} and in particular S({a_{j}}_{j=1}^{n}) = S_{n} if {a_{j}}_{j=1}^{n} = {1, 2, …, n}. As a consequence,

S_{n} = ∑_{σ∈S({a_{j}}_{j=1}^{n})} N(σ).

Two permutations σ_{1} and σ_{2} in S_{n} are related, written as σ_{1} ∼ σ_{2}, if and only if σ_{1}(1) = σ_{2}(1). It can be verified that ∼ is an equivalence relation on S_{n}. The equivalence relation ∼ induces equivalence classes O_{j} = {σ ∈ S_{n} : σ(1) = j}, j = 1, …, n, of S_{n}. It follows that O_{i} ∩ O_{j} = ∅ for i ≠ j and S_{n} = ⋃_{j=1}^{n} O_{j} and thus, the total number of inversions of all permutations in S_{n} is the same as the sum of the number of inversions of all permutations in each equivalence classes O_{j}. In symbols, we have

S_{n} = ∑_{j=1}^{n} ∑_{σ∈O_{j}} N(σ).  (5)

Let σ ∈ O_{j} and {a_{k}}_{k=1}^{n−1} be an arrangement in increasing order of elements of A − {j}. The permutation τ defined by

τ = ( \begin{matrix}a_{1} & a_{2} & ⋯ & a_{n−1} \\ σ(2) & σ(3) & ⋯ & σ(n) \end{matrix} )

is an element of S(A − {j}). If we define the permutation σ_{τ,j} by

σ_{τ,j} = ( \begin{matrix}1 & 2 & ⋯ & n \\ j & τ(a_{1}) & ⋯ & τ(a_{n−1}) \end{matrix} ) ,

then σ = σ_{τ,j} and

N(σ_{τ,j}) = (j − 1) + N(τ).  (6)

Equations (5) and (6) give us a recursive formula for S_{n} and we state it as a lemma.

Lemma 1. We have S_{1} = 0 and

S_{n} = \frac{n!(n − 1)}{2} + nS_{n−1}, n ≥ 2.

Proof. Since S_{1} = {ι}, then S_{1} = N(ι) = 0. Now suppose n ≥ 2. Note that for each j = 1, …, n

∑_{σ∈O_{j}} N(σ) = ∑_{τ∈S(A−{j})} N(σ_{τ,j})
= ∑_{τ∈S(A−{j})}[(j − 1) + N(τ)]
= (j − 1)|S(A − {j})| + ∑_{τ∈S(A−{j})} N(τ)
= (j − 1)(n − 1)! + S_{n−1}.

From Eq. (5), we get

S_{n} = ∑_{j=1}^{n}[(j − 1)(n − 1)! + S_{n−1}]

= (n − 1)! ∑_{j=1}^{n}(j − 1) + nS_{n−1}

= \frac{n!(n − 1)}{2} + nS_{n−1}.

Theorem 2. For n ≥ 1, we have

S_{n} = \frac{|S_{n}|}{2}\binom{n}{2} = \frac{n!}{2}\binom{n}{2}.

Proof. The case where n = 1 is trivial. Assuming that the formula holds for some fixed integer k, we go on to show that it must hold for k + 1 too. Using Lemma 1 and the induction hypothesis,

S_{k+1} = \frac{(k + 1)!k}{2} + (k + 1)S_{k}
= \frac{(k + 1)!k}{2} + (k + 1)\frac{k!}{2}\binom{k}{2}
= \frac{(k + 1)!}{2} (k + \frac{k(k − 1)}{2})
= \frac{(k + 1)!}{2}\binom{k + 1}{2},

which is the formula in the case n = k + 1. This establishes the theorem.

A permutation σ is said to be even if N(σ) is even, otherwise it is said to be odd. Let A_{n} be the set of all even permutations in S_{n}. Note that A_{n} is a subgroup of index 2 of S_{n} called the alternating group of degree n. Similarly, we let A({a_{j}}_{j=1}^{n}) be the corresponding alternating group of all even permutations of {a_{j}}_{j=1}^{n}. If we denote A_{n} to be the number of inversions of all permutations in A_{n} then

A_{n} = ∑_{σ∈A_{n}} N(σ) = ∑_{σ∈A({a_{j}}_{j=1}^{n})} N(σ)  (7)

For small values of n, A_{n} can easily be determined using Eq. (7). Indeed, A_{1} = A_{2} = 0 and A_{3} = 4. A drawback of counting, however, occurs when n is large.

Because A_{n} is a subset of S_{n}, if σ ∈ A_{n}, then σ ∈ O_{j} for some j. Thus, the method used to determine S_{n} can as well be extended to determine A_{n}. It should be noted, however, that if an even permutation σ is an element of O_{j}, it is not true that all other permutations in O_{j} are also even. Thus, some minor modifications in counting are necessary.

Theorem 3. For all n ≥ 4 we have

A_{n} = \frac{|A_{n}|}{2}\binom{n}{2} = \frac{n!}{4}\binom{n}{2}.

Proof. Recall that every permutation σ ∈ S_{n} can be uniquely represented by σ_{τ,j} for some τ ∈ S(A − {j}), where 1 ≤ j ≤ n. It follows from Eq. (6) that σ_{τ,j} is even if and only if j and N(τ) have different parity. For simplicity, we let A(j) = A(A − {j}) and (A(j))^{c} be the complement of A(A − {j}) with respect to S(A − {j}), in other words, it is the set of permutations of A − {j} with an odd number of inversions.

First, consider the case where n ≥ 4 is even, and so

A_{n} = ∑_{j=1}^{n/2} ∑_{τ∈A(2j−1)}[(2j − 2) + N(τ)] + ∑_{j=1}^{n/2} ∑_{τ∈(A(2j))^{c}}[(2j − 1) + N(τ)]

= ∑_{j=1}^{n/2}[(2j − 2)|A_{n−1}| + ∑_{σ∈A_{n−1}} N(σ) + (2j − 1)|A_{n−1}^{c}| + ∑_{σ∈A_{n−1}^{c}} N(σ)]

= ∑_{j=1}^{n/2} [\frac{(4j − 3)(n − 1)!}{2} + A_{n−1} + (S_{n−1} − A_{n−1})]

= \frac{(n − 1)!}{2} ∑_{j=1}^{n/2} [(4j − 3) + \binom{n − 1}{2}]

= \frac{n!}{4}\binom{n}{2}.

Now suppose n ≥ 5 is odd so that n − 1 is even. From the previous result, we have

A_{n−1} = \frac{(n − 1)!}{4}\binom{n − 1}{2}.

Similarly, we compute as follows

A_{n} = ∑_{j=1}^{(n−1)/2} ∑_{τ∈A(2j−1)}[(2j − 2) + N(τ)] + ∑_{τ∈A(n)}[(n − 1) + N(τ)]

+ ∑_{j=1}^{(n−1)/2} ∑_{τ∈(A(2j))^{c}}[(2j − 1) + N(τ)]

= ∑_{j=1}^{(n−1)/2} [\frac{(4j − 3)(n − 1)!}{2} + S_{n−1}] + \frac{(n − 1)(n − 1)!}{2} + A_{n−1}

= \frac{(n − 1)!}{2} ∑_{j=1}^{(n−1)/2} [(4j − 3) + \binom{n − 1}{2}] + \frac{(n − 1)!}{2} [(n − 1) + \frac{(n − 1)(n − 2)}{4}]

= \frac{n!}{4}\binom{n}{2}.

The following corollary, which relates S_{n} and A_{n}, follows immediately from the previous theorems.

Corollary 4. If n ≥ 1, then A_{n} = ⌊S_{n}/2⌋.

3 Backward permutations

A backward inversion of a permutation σ ∈ S_{n} is a pair (σ(i), σ(j)) such that 1 ≤ i < j ≤ n and σ(i) < σ(j). Again, for computation purposes, we represent a backward inversion (σ(i), σ(j)) just by the ordered pair (i, j). If we let M(σ) denotes the total number of backward inversions of a permutation σ, then

M(σ) = |{(i, j) : σ(i) < σ(j) , 1 ≤ i < j ≤ n}|
= |{(i, j) : 1 ≤ i < j ≤ n}| − |{(i, j) : σ(i) > σ(j) , 1 ≤ i < j ≤ n }|
= \binom{n}{2} − N(σ).

Therefore, for any permutation σ ∈ S_{n}, the sum of the total number of inversions and backward inversions is \binom{n}{2}, that is,

N(σ) + M(σ) = \binom{n}{2}.  (8)

An immediate consequence of Eq. (8) is stated as a theorem which characterizes a permutation in terms of backward inversions.

Theorem 5. Let σ ∈ S_{n}.

(i) If n ≡ 0, 1 (mod 4), then σ ∈ A_{n} if and only if M(σ) is even.

(ii) If n ≡ 2, 3 (mod 4), then σ ∈ A_{n} if and only if M(σ) is odd.

Proof. If n ≡ 0, 1 (mod 4) then \binom{n}{2} is even, and it follows from Eq. (8) that M(σ) is even if and only if N(σ) is even. If n ≡ 2, 3 (mod 4) then \binom{n}{2} is odd, and so M(σ) is odd if and only if N(σ) is even.

Given a permutation σ ∈ S_{n}, the backward permutation of σ, denoted by \overline{σ}, is defined as

\overline{σ} = ( \begin{matrix}1 & 2 & ⋯ & n − 1 & n \\ σ(n) & σ(n − 1) & ⋯ & σ(2) & σ(1) \end{matrix} ) .  (9)

It is clear from the definition that any backward permutation \overline{σ} is also in S_{n}.

Let B be the bijective mapping B : S_{n} → S_{n} that sends every permutation onto its backward permutation, that is, B(σ) = \overline{σ}. Thus, S_{n} = \{\overline{σ} : σ ∈ S_{n}\} and B(\overline{σ}) = \overline{\overline{σ}} = σ. It now follows that N(\overline{σ}) = M(σ) and from Eq. (8), we have

N(\overline{σ}) + N(σ) = \binom{n}{2}.  (10)

The power of backward permutations and backward inversions can be best illustrated by offering an alternative proof of Theorem 2. Because S_{n} = \{\overline{σ} : σ ∈ S_{n}\}, we have

2S_{n} = 2 ∑_{σ∈S_{n}} N(σ) = ∑_{σ∈S_{n}} N(σ) + ∑_{σ∈S_{n}} N(\overline{σ})
= ∑_{σ∈S_{n}}[N(σ) + N(\overline{σ})]

= ∑_{σ∈S_{n}} \binom{n}{2} = n!\binom{n}{2},

and the result follows.

Using Theorem 5, one can check that if n ≡ 0, 1 (mod 4) then B[A_{n}] = A_{n} and if n ≡ 2, 3 (mod 4) then B[A_{n}] = A_{n}^{c}. Thus, the concept of backward permutations seems inappropriate for computing A_{n} for any values of n. It will, however, be most useful in the next section.

4 Backward permutations in dihedral groups

Consider the regular n-gon, with n ≥ 3. Label successive vertices of the n-gon by 1, 2, …, n. The Dihedral group D_{n} of isometries of the plane which map a regular n-gon onto itself can be considered as a subgroup of S_{n}. To see this, first let us represent the elements of D_{n} as permutations. A (360/n)^{o} clockwise rotation (about the center of the n-gon) is represented by the permutation

ρ = ( \begin{matrix}1 & 2 & ⋯ & n − 1 & n \\ 2 & 3 & ⋯ & n & 1 \end{matrix} ) .

Thus, for each 1 ≤ k < n, a (360k/n)^{o} clockwise rotation can be represented as the permutation ρ^{k} given by

ρ^{k} = ( \begin{matrix}1 & 2 & ⋯ & n − k & n − k + 1 & ⋯ & n \\ k + 1 & k + 2 & ⋯ & n & 1 & ⋯ & k \end{matrix} ) ,  (11)

and ρ^{n} = ι. Note that ⟨ρ⟩ is the subgroup of D_{n} consisting of all rotations. Further, for each k = 1, …, n, one can see from Eq. (11) that N(ρ^{k}) = k(n − k) and so

∑_{σ∈⟨ρ⟩} N(σ) = ∑_{k=1}^{n} N(ρ^{k}) = ∑_{k=1}^{n} k(n − k) = \frac{n + 1}{3}\binom{n}{2}.

If n is odd, for each 1 ≤ k ≤ n, let μ_{k} be the mirror reflection whose axis bisects the angle corresponding to the vertex k of the n-gon. Case 1. If 2k − 1 ≤ n then

μ_{k} = ( \begin{matrix}1 & 2 & ⋯ & k & ⋯ & 2k − 2 & 2k − 1 & 2k & ⋯ & n \\ 2k − 1 & 2k − 2 & ⋯ & k & ⋯ & 2 & 1 & n & ⋯ & 2k \end{matrix} ) .

It follows that

\overline{μ_{k}} = ( \begin{matrix}1 & 2 & ⋯ & n − 2k + 1 & n − 2k + 2 & n − 2k + 3 & ⋯ & n \\ 2k & 2k + 1 & ⋯ & n & 1 & 2 & ⋯ & 2k − 1 \end{matrix} ) ,

and so \overline{μ_{k}} = ρ^{2k−1}. Case 2. If 2k − 1 > n then

μ_{k} = ( \begin{matrix}1 & ⋯ & 2k − n − 1 & 2k − n & ⋯ & k & k + 1 & ⋯ & n \\ 2k − n − 1 & ⋯ & 1 & n & ⋯ & k & k − 1 & ⋯ & 2k − n \end{matrix} )

and

\overline{μ_{k}} = ( \begin{matrix}1 & 2 & ⋯ & 2n − 2k + 1 & 2n − 2k + 2 & ⋯ & n \\ 2k − n & 2k − n + 1 & ⋯ & n & 1 & ⋯ & 2k − n − 1 \end{matrix} ) .

and thus, \overline{μ_{k}} = ρ^{2k−n−1}.

Suppose now that n is even. For 1 ≤ k ≤ n, we have μ_{k} = μ_{k+n/2} and thus we only need to consider those reflections μ_{k} for 1 ≤ k ≤ n/2. Similarly, it can be shown that \overline{μ_{k}} = ρ^{2k−1} for all 1 ≤ k ≤ n/2.

Aside from the mirror reflection μ_{k} defined above, there are mirror reflections whose axis bisects two parallel sides of the n-gon, when n is even. For each k = 1, 2, …, n/2, denote μ_{k,k+1} be the mirror reflection whose axis bisects the two sides of the n-gon, one having vertices k and k + 1. Then

μ_{k,k+1} = ( \begin{matrix}1 & ⋯ & 2k & 2k + 1 & ⋯ & n \\ 2k & ⋯ & 1 & n & ⋯ & 2k + 1 \end{matrix} ) .

Taking the backward permutation yields

\overline{μ_{k,k+1}} = ( \begin{matrix}1 & ⋯ & n − 2k & n − 2k + 1 & ⋯ & n \\ 2k + 1 & ⋯ & n & 1 & ⋯ & 2k \end{matrix} ) .

and thus \overline{μ_{k,k+1}} = ρ^{2k}.

Hence, the backward permutation of any mirror reflection is a rotation. If M be the set of all mirror reflections in D_{n}, it follows that B[M] is the set of all rotations in D_{n}. We state these results as a theorem.

Theorem 6. If n ≥ 3 and M is the set of all mirror reflections in D_{n}, then {M, B[M]} partitions D_{n}.

Similarly, we define

D_{n} = ∑_{σ∈D_{n}} N(σ)

and the following theorem gives an explicit formula for D_{n}. Theorem 7. For all n ≥ 3 we have

D_{n} = \frac{|D_{n}|}{2}\binom{n}{2} = n\binom{n}{2}.

Proof. Using the previous theorem, we get

D_{n} = ∑_{σ∈D_{n}} N(σ) = ∑_{σ∈M} N(σ) + ∑_{σ∈B[M]} N(σ)
= ∑_{σ∈M} N(σ) + ∑_{σ∈M} N(\overline{σ})
= ∑_{σ∈M} [N(σ) + N(\overline{σ})]
= |M|\binom{n}{2} = n\binom{n}{2}.

Corollary 8. If t_{n} denotes the nth triangular number, then for all n ≥ 3 we have

D_{n} = ∑_{t_{n−1}<i<t_{n}} i.

Using Theorems 2, 3 and 7, we can generate the following table :

n  1  2  3  4  5  6  7  8  9
S_{n}  0  1  9  72  600  5400 52920 564480 6531840
A_{n}  0  0  4  36  300  2700 26460 282240 3265920
D_{n}  9  24  50  90  147  224  324

5 Number of permutations with k inversions

Let I_{n}(k) denotes the number of permutations in S_{n} having k inversions. It was shown that the sequence \{I_{n}(k) : 0 ≤ k ≤ \binom{n}{2}\} has the generating function

\begin{matrix}( & {n \atop 2} & ) \\ ∑ \\ k=0 \end{matrix} I_{n}(k)x^{k} = ∏_{j=1}^{n} \frac{1 − x^{j}}{1 − x} ,

and using this polynomial, one can find the value of I_{n}(k) for k = 0, 1, …, \binom{n}{2}, (see [3]). Also, asymptotic formulas of the sequence {I_{n+k}(n) : n ∈ ℕ} for a fixed integer k ≥ 0 were discussed in [2] and [3]. In this paper, we employ the partitioning method to provide a recursive formula in finding these inversion numbers.

Lemma 9. For each 0 ≤ k ≤ \binom{n}{2}, there exists σ ∈ S_{n} such that N(σ) = k.

Proof. If n = 1, 2, the statement clearly holds. Assume that the lemma is true for n − 1. Let 0 ≤ k ≤ \binom{n}{2}. For all 1 ≤ j ≤ n and 0 ≤ l ≤ \binom{n−1}{2} there exists τ ∈ S(A − \{j\}) such that N(σ_{τ,j}) = (j − 1) + N(τ) and N(τ) = l. Observe that the possible values of (j − 1) + N(τ) are 0, 1, …, \binom{n}{2}. Therefore, one can find a j and a τ such that σ_{τ,j} ∈ S_{n} and N(σ_{τ,j}) = (j − 1) + N(τ) = k.

We note that S_{n} and A_{n} can be represented by the inversion numbers. Indeed, we have

S_{n} = \begin{matrix}( & {n \atop 2} & ) \\ ∑ \\ k=0 \end{matrix} kI_{n}(k) and A_{n} = ∑_{k=0}^{⌊ \frac{1}{2} \binom{n}{2}⌋} 2kI_{n}(2k).

Theorem 10. For 0 ≤ k ≤ \binom{n}{2} where n ≥ 2, we have the following recurrence relation

I_{1}(0) = I_{2}(0) = I_{2}(1) = 1  (12)

and

I_{n}(k) = ∑_{i=max\{0,k−n+1\}}^{min\{k,\binom{n−1}{2}\}} I_{n−1}(i), n ≥ 3.  (13)

Proof. Eq. (12) is clear. Now suppose n ≥ 3. Recall that N(σ_{τ,j}) = (j − 1) + N(τ). Let N(σ_{τ,j}) = k and N(τ) = i then 0 ≤ i ≤ \binom{n−1}{2} and 0 ≤ j − 1 ≤ n − 1. We find those i such that given j, N(σ_{τ,j}) = k and I_{n}(k) can be formed by adding I_{n−1}(i) for all values of i that we found. We have j − 1 + i = k or equivalently i = k − j + 1 ≤ k. Because i ≤ \binom{n−1}{2}, then i ≤ min \{k, \binom{n−1}{2}\}. Now i = k − j + 1 ≥ k − n + 1. But i must be nonnegative and thus i ≥ max {0, k − n + 1}. Hence, we have Eq. (13).

With the aid of the previous theorem, we can generate the following table:

I_{n}(k)

n\k 0 1 2 3 4 5 6 7  8 9 10 11 12 13 14 15
1 1
2 1 1
3 1 2 2 1
4 1 3 5 6 5 3 1
5 1 4 9 15 20 22 20 15 9 4 1
6 1 5 14 29 49 71 90 101 101 90 71 49 29 14 5 1

Let n > 1. Using Theorem 10, if the value of I_{n−1}(k) for 0 ≤ k ≤ \binom{n−1}{2} is known, then the values of I_{n}(k) for 0 ≤ k ≤ \binom{n}{2} can be determined by the following formula

I_{n}(k) = \{ \begin{matrix}1, & if k = 0; \\ I_{n}(k − 1) + I_{n−1}(k), & if 1 ≤ k ≤ n − 1; \\ I_{n}(k − 1) + I_{n−1}(k) − I_{n−1}(k − n), & if n ≤ k ≤ \binom{n−1}{2}; \\ I_{n}(k − 1) − I_{n−1}(k − n), & if \binom{n−1}{2} < k ≤ \binom{n}{2}. \end{matrix}  (14)

Theorem 11. For all 0 ≤ k ≤ \binom{n}{2} we have I_{n} (\binom{n}{2} − k) = I_{n}(k).

Proof. Let K_{1} = \{σ ∈ S_{n} : N(σ) = k\} and K_{2} = \{σ ∈ S_{n} : N(σ) = \binom{n}{2} − k\}, and by Lemma 5.1, K_{1} and K_{2} are both nonempty. The mapping B_{1} : K_{1} → K_{2} defined by B_{1}(σ) = \overline{σ} is clearly bijective. Therefore |K_{1}| = |K_{2}| and so I_{n} (\binom{n}{2} − k) = I_{n}(k).

Corollary 12. If n ≡ 2, 3 (mod 4) and C = \frac{1}{2} [\binom{n}{2} − 1] then ∑_{k=0}^{C} I_{n}(k) = \frac{n!}{2}.

As an application of Eq. (14), we will consider the sequence {I_{n+k}(k) : n ≥ 0}, where k ≥ 1 is fixed. One can verify, using the second case in Eq. (14), that I_{n+1}(1) = n, I_{n+2}(2) = n(n+3)/2 and I_{n+3}(3) = (n+3)(n^{2} +6n+2)/6, for all n ≥ 0. Suppose I_{n+k}(k) = ∑_{i=0}^{k} a_{ki}n^{i}, where a_{kk} ≠ 0 so that deg I_{n+k}(k) = k. Thus

I_{n+k+1}(k + 1) = I_{k+1}(k + 1) + ∑_{j=1}^{n} I_{j+1+k}(k)

= C_{k+1} + ∑_{j=1}^{n} ∑_{i=0}^{k} a_{ki}(j + 1)^{i}

= C_{k+1} + ∑_{j=1}^{n} ∑_{i=0}^{k} ∑_{h=0}^{i} \binom{i}{h}a_{ki}j^{h}

= C_{k+1} + ∑_{i=0}^{k} ∑_{h=0}^{i} \binom{i}{h}a_{ki}P_{h+1}(n),

for all n ≥ 0, where C_{k+1} = I_{k+1}(k+1) and P_{h+1}(n) = ∑_{j=1}^{n} j^{h}. It can be shown that P_{h+1}(n) is a polynomial of degree h + 1. From these, it follows that I_{n+k+1}(k + 1) is a polynomial of degree k + 1. Thus we have shown that, I_{n+k}(k) is a polynomial of degree k for all k ≥ 1. This result implies that I_{n}(k) = O(n^{k}) for all k ≥ 1.

References

[1] N. Eriksen, (1+ϵ)-approximation of sorting by reversals and transpositions, Theor. Comput. Sci. 289 (2002), 517–529.

[2] G. Louchard and H. Prodinger, The number of inversions in permutations: a saddle point approach, J. Integer Sequences 6 (2003), Article 03.2.8.

[3] B. H. Margolius, Permutations with inversions, J. Integer Sequences 4 (2001), Article 01.2.4.

2000 Mathematics Subject Classification: Primary 05A10; Secondary 20B35. Keywords: inversions, permutations, symmetric groups, alternating groups, dihedral groups.

(Concerned with sequences \underline{A001809} and \underline{A006002}.)

Received May 11 2008; revised version received September 29 2008. Published in Journal of Integer Sequences, October 4 2008.

Return to Journal of Integer Sequences home page.