\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Inversions of Permutations in Symmetric, Alternating, and Dihedral Groups \\ \vskip .1in } \vskip 1cm \large 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\\ \href{mailto:dlindong@upb.edu.ph}{\tt dlindong@upb.edu.ph}\\ \href{mailto:grperalta@upb.edu.ph}{\tt grperalta@upb.edu.ph} \end{center} \vskip .2in \begin{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 $\mathbf{S}_{n}$ and consider each element in each equivalence class as a permutation of a proper subset of $\{1,2,\ldots , 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. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{remar}[theorem]{Remark} \newenvironment{remark}{\begin{remar}\normalfont\quad}{\end{remar}} \section{Introduction} Let $n$ be a positive integer and $A$ be the finite set $\left\{ 1, 2, \ldots , n \right\}$. The group of all permutations of $A$ is the \textit{symmetric group on \textit{n} elements} and it is denoted by $\mathbf{S}_{n}$. A permutation $\sigma \in \mathbf{S}_{n}$ can be represented by \begin{equation*} \sigma = \left( \begin{array}{cccc} 1 & 2 & \cdots & n\\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{array}\right). \end{equation*} Note that $\mathbf{S}_{n}$ has $n!$ elements and the identity element is given by $\iota(i) = i$ for all $i\in A$. An \textit{inversion} induced by a permutation $\sigma$ is an ordered pair $(\sigma(i),\sigma(j))$ such that $i < j$ and $\sigma(i) > \sigma(j)$. For purposes of computations later, we represent an inversion $(\sigma(i),\sigma(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 \cite{label1} for example). If we let $I(\sigma)$ be the set of all inversions of a permutation $\sigma \in \mathbf{S}_{n}$, then \begin{equation} I(\sigma) = \{ (i,j) : \sigma(i) > \sigma(j), 1 \leq i < j \leq n\}. \label{eq1} \end{equation} It now follows from Eq.~(\ref{eq1}) that if $N(\sigma)$ is the number of all inversions induced by $\sigma \in \mathbf{S}_{n}$, then $N(\sigma) = |I(\sigma)|.$ Observe that the only permutation with no inversion is the identity permutation and so, $N(\sigma) = 0$ if and only if $\sigma = \iota$. 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 $\sigma \in \mathbf{S}_{n}$, we count the number of $j$'s such $\sigma(1) > \sigma(j)$ for $1 < j \leq n$, then the number of $j$'s such that $\sigma(2) > \sigma(j)$ for $2 < j \leq n$, up to the number of $j$'s such that $\sigma(n-1) > \sigma(j)$ for $n-1 < j \leq n$, and thus, a formula for $N(\sigma)$ is given by \begin{equation} N(\sigma) = \sum_{i = 1}^{n-1} \left|\{ j : \sigma(i) > \sigma(j), i < j \leq n \}\right|. \label{eq2} \end{equation} Let $\beta \in \mathbf{S}_n$ be the permutation defined by \begin{equation} \beta = \left( \begin{array}{cccc} 1 & 2 & \cdots & n \\ n & n-1 & \cdots & 1 \end{array}\right). \label{eq3} \end{equation} Note that for $1 \leq i \leq n$ we have $\beta(i) = n - i + 1$. Thus, $i < j$ implies that $\beta(i) > \beta(j)$. It now follows that $(i,j) \in I(\beta)$ for $1 \leq i < j \leq n$ and the permutation $\beta$ defined by Eq.~(\ref{eq3}) gives the maximum number of inversions in any permutation. Hence, \begin{equation*} \max_{\sigma \in \mathbf{S}_n} N(\sigma) = N(\beta) = \sum_{i = 1}^{n-1} (n-i) = \binom{n}{2}. \label{eq4} \end{equation*} For each positive integer $n$, if we let $S_{n}$ be the total number of inversions of all permutations $\sigma \in \mathbf{S}_{n}$ then \begin{equation} S_n = \sum_{\sigma \in \mathbf{S}_n} N(\sigma). \label{eq5} \end{equation} Using formulas (\ref{eq2}) and (\ref{eq5}) 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 $\mathbf{S}_{n}$, namely the alternating group $\mathbf{A}_{n}$ and the dihedral group $\mathbf{D}_{n}$. \section{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 $\mathbf{S}(\{a_j\}_{j=1}^n)$ be the group of all permutations of $\{a_j\}_{j=1}^n$. Notice that $\mathbf{S}(\{a_j\}_{j=1}^n)\simeq \mathbf{S}_{n}$ and in particular $\mathbf{S}(\{a_j\}_{j=1}^n)=\mathbf{S}_{n}$ if $\{a_j\}_{j=1}^n=\left\{ 1, 2, \ldots, n \right\}$. As a consequence, \begin{equation*} S_{n} = \sum_{\sigma \in \mathbf{S}(\{a_j\}_{j=1}^n)} N(\sigma). \label{eq6} \end{equation*} Two permutations $\sigma_1$ and $\sigma_2$ in $\mathbf{S}_n$ are related, written as $\sigma_1 \sim \sigma_2$, if and only if $\sigma_1(1) = \sigma_2(1)$. It can be verified that $\sim$ is an equivalence relation on $\mathbf{S}_n$. The equivalence relation $\sim$ induces equivalence classes $\mathbf{O}_j = \{ \sigma \in \mathbf{S}_n : \sigma(1) = j\}$, $j = 1, \ldots, n$, of $\mathbf{S}_{n}$. It follows that $\mathbf{O}_i \cap \mathbf{O}_j = \emptyset$ for $i \neq j$ and $\mathbf{S}_n = \bigcup_{j=1}^n \mathbf{O}_j$ and thus, the total number of inversions of all permutations in $\mathbf{S}_{n}$ is the same as the sum of the number of inversions of all permutations in each equivalence classes $\mathbf{O}_{j}$. In symbols, we have \begin{eqnarray} S_n = \sum_{j=1}^n \sum_{\sigma\in\mathbf{O}_j} N(\sigma). \label{eq7} \end{eqnarray} Let $\sigma \in \mathbf{O}_j$ and $\{a_k\}_{k = 1}^{n-1}$ be an arrangement in increasing order of elements of $A-\{j\}$. The permutation $\tau$ defined by \begin{equation*} \tau= \left( \begin{array}{cccc} a_{1} & a_{2} & \cdots & a_{n-1} \\ \sigma(2) & \sigma(3) & \cdots & \sigma(n) \end{array}\right) \label{eq8} \end{equation*} is an element of $\mathbf{S}(A-\{j\})$. If we define the permutation $\sigma_{\tau,j}$ by \begin{equation*} \sigma_{\tau,j} = \left( \begin{array}{cccc} 1 & 2 & \cdots & n \\ j & \tau(a_{1}) & \cdots & \tau(a_{n-1}) \end{array}\right), \label{eq9} \end{equation*} then $\sigma = \sigma_{\tau,j}$ and \begin{equation} N(\sigma_{\tau,j}) = (j-1) + N(\tau). \label{eq10} \end{equation} Equations (\ref{eq7}) and (\ref{eq10}) give us a recursive formula for $S_{n}$ and we state it as a lemma. \begin{lemma} We have $S_{1}=0$ and \begin{eqnarray*} S_n &=& \frac{n!(n-1)}{2} + nS_{n-1}, \quad n\geq 2. \label{eq11} \end{eqnarray*} \label{lem1} \end{lemma} \begin{proof} Since $\mathbf{S}_1 = \{\iota\}$, then $S_1 = N(\iota) = 0$. Now suppose $n\geq 2$. Note that for each $j = 1,\ldots,n$ \begin{eqnarray*} \sum_{\sigma \in \mathbf{O}_j} N(\sigma) &=& \sum_{\tau \in \mathbf{S}(A-\{j\})} N(\sigma_{\tau,j})\\ &=& \sum_{\tau \in \mathbf{S}(A-\{j\})} [(j-1) + N(\tau)]\\ &=& (j-1)|\mathbf{S}(A-\{j\})| + \sum_{\tau \in \mathbf{S}(A-\{j\})}N(\tau)\\ &=& (j-1)(n-1)! + S_{n-1}. \end{eqnarray*} From Eq.~(\ref{eq7}), we get \begin{eqnarray*} S_n &=& \sum_{j=1}^n [(j-1)(n-1)! + S_{n-1}]\\ &=& (n-1)!\sum_{j=1}^n (j-1) + nS_{n-1}\\ &=& \frac{n!(n-1)}{2} + nS_{n-1}. \end{eqnarray*} \end{proof} \begin{theorem} For $n\geq 1$, we have \begin{equation*} S_n = \frac{|\mathbf{S}_n|}{2} \binom{n}{2} = \frac{n!}{2}\binom{n}{2}. \label{eq12} \end{equation*} \label{thm1} \end{theorem} \begin{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 \ref{lem1} and the induction hypothesis, \begin{eqnarray*} 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} \left( k + \frac{k(k-1)}{2} \right)\\ &=& \frac{(k+1)!}{2} \binom{k+1}{2}, \end{eqnarray*} which is the formula in the case $n = k+1$. This establishes the theorem. \end{proof} A permutation $\sigma$ is said to be \textit{even} if $N(\sigma)$ is even, otherwise it is said to be \textit{odd}. Let $\mathbf{A}_{n}$ be the set of all even permutations in $\mathbf{S}_{n}$. Note that $\mathbf{A}_{n}$ is a subgroup of index 2 of $\mathbf{S}_{n}$ called the \textit{alternating group of degree $n$}. Similarly, we let $\mathbf{A}(\left\{a_{j} \right\}_{j=1}^{n})$ be the corresponding alternating group of all even permutations of $\left\{a_{j}\right\}_{j=1}^{n}$. If we denote $A_{n}$ to be the number of inversions of all permutations in $\mathbf{A}_{n}$ then \begin{equation} A_{n} = \sum_{\sigma \in \mathbf{A}_{n}} N(\sigma) = \sum_{\sigma \in \mathbf{A}(\left\{a_{j}\right\}_{j=1}^{n})} N(\sigma) \label{eq13} \end{equation} For small values of $n$, $A_{n}$ can easily be determined using Eq.~(\ref{eq13}). Indeed, $A_{1} = A_{2} = 0$ and $A_{3} = 4$. A drawback of counting, however, occurs when $n$ is large. Because $\mathbf{A}_{n}$ is a subset of $\mathbf{S}_{n}$, if $\sigma \in \mathbf{A}_{n}$, then $\sigma \in \mathbf{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 $\sigma$ is an element of $\mathbf{O}_{j}$, it is not true that all other permutations in $\mathbf{O}_{j}$ are also even. Thus, some minor modifications in counting are necessary. \begin{theorem} For all $n \geq 4$ we have \begin{equation*} A_n = \frac{|\mathbf{A}_n|}{2}\binom{n}{2}= \frac{n!}{4}\binom{n}{2}. \label{eq14} \end{equation*} \label{thm2} \end{theorem} \begin{proof} Recall that every permutation $\sigma\in \mathbf{S}_{n}$ can be uniquely represented by $\sigma_{\tau,j}$ for some $\tau\in \mathbf{S}(A-\{j\})$, where $1\leq j \leq n$. It follows from Eq.~(\ref{eq10}) that $\sigma_{\tau,j}$ is even if and only if $j$ and $N(\tau)$ have different parity. For simplicity, we let $\mathbf{A}(j) = \mathbf{A}(A-\{j\})$ and $(\mathbf{A}(j))^c$ be the complement of $\mathbf{A}(A - \{j\})$ with respect to $\mathbf{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 \geq 4$ is even, and so \begin{eqnarray*} A_n &=& \sum_{j=1}^{n/2} \sum_{\tau \in \mathbf{A}(2j-1)} [(2j-2) + N(\tau)] + \sum_{j=1}^{n/2} \sum_{\tau \in (\mathbf{A}(2j))^c} [(2j-1) + N(\tau)]\\ &=& \sum_{j=1}^{n/2} \biggl[ (2j-2)|\mathbf{A}_{n-1}| + \sum_{\sigma\in\mathbf{A}_{n-1}} N(\sigma) + (2j-1)|\mathbf{A}_{n-1}^c| + \sum_{\sigma\in\mathbf{A}_{n-1}^c} N(\sigma) \biggl]\\ &=& \sum_{j=1}^{n/2} \left[ \frac{(4j-3)(n-1)!}{2} + A_{n-1} + (S_{n-1}- A_{n-1})\right]\\ &=& \frac{(n-1)!}{2}\sum_{j=1}^{n/2} \left[ (4j-3)+\binom{n-1}{2} \right] \\ &=& \frac{n!}{4}\binom{n}{2}. \end{eqnarray*} Now suppose $n \geq 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 \begin{eqnarray*} A_n &=& \sum_{j=1}^{(n-1)/2} \sum_{\tau \in \mathbf{A}(2j-1)} [(2j-2) + N(\tau)] + \sum_{\tau \in \mathbf{A}(n)} [(n-1) + N(\tau)]\\ & & +\sum_{j=1}^{(n-1)/2} \sum_{\tau \in (\mathbf{A}(2j))^c} [(2j-1) + N(\tau)]\\ &=& \sum_{j=1}^{(n-1)/2} \left[ \frac{(4j-3)(n-1)!}{2} + S_{n-1}\right] + \frac{(n-1)(n-1)!}{2} + A_{n-1} \\ &=& \frac{(n-1)!}{2}\sum_{j=1}^{(n-1)/2} \left[ (4j-3)+\binom{n-1}{2} \right] + \frac{(n-1)!}{2} \left[ (n-1) + \frac{(n-1)(n-2)}{4} \right]\\ &=& \frac{n!}{4}\binom{n}{2}. \end{eqnarray*} \end{proof} The following corollary, which relates $S_n$ and $A_n$, follows immediately from the previous theorems. \begin{corollary} If $n\geq 1$, then $A_n = \lfloor S_n/2 \rfloor$. \label{cor1} \end{corollary} \section{Backward permutations} A \textit{backward inversion} of a permutation $\sigma \in \mathbf{S}_n$ is a pair $(\sigma(i),\sigma(j))$ such that $1\leq i\sigma(j)\ , 1\leq i < j \leq n\ \}|\\ &=& \binom{n}{2} - N(\sigma). \end{eqnarray*} Therefore, for any permutation $\sigma\in\mathbf{S}_n$, the sum of the total number of inversions and backward inversions is $\binom{n}{2}$, that is, \begin{eqnarray} N(\sigma) + M(\sigma) = \binom{n}{2}. \label{eq15} \end{eqnarray} An immediate consequence of Eq.~(\ref{eq15}) is stated as a theorem which characterizes a permutation in terms of backward inversions. \begin{theorem} Let $\sigma\in \mathbf{S}_{n}$. \begin{enumerate} \item[$($i$)$] If $n \equiv\, 0,1 \pmod{4}$, then $\sigma\in \mathbf{A}_n$ if and only if $M(\sigma)$ is even. \item[$($ii$)$] If $n \equiv\, 2,3 \pmod{4}$, then $\sigma\in \mathbf{A}_n$ if and only if $M(\sigma)$ is odd. \end{enumerate} \label{thm3} \end{theorem} \begin{proof} If $n \equiv\, 0,1 \pmod{4}$ then $\binom{n}{2}$ is even, and it follows from Eq.~(\ref{eq15}) that $M(\sigma)$ is even if and only if $N(\sigma)$ is even. If $n \equiv\, 2,3 \pmod{4}$ then $\binom{n}{2}$ is odd, and so $M(\sigma)$ is odd if and only if $N(\sigma)$ is even. \end{proof} Given a permutation $\sigma \in\mathbf{S}_n$, the \textit{backward permutation} of $\sigma$, denoted by $\overline{\sigma}$, is defined as \begin{equation} \overline{\sigma} = \left( \begin{array}{ccccc} 1 & 2 & \cdots & n-1 & n \\ \sigma(n) & \sigma(n-1) & \cdots & \sigma(2) & \sigma(1) \end{array} \right). \label{eq16} \end{equation} It is clear from the definition that any backward permutation $\overline{\sigma}$ is also in $\mathbf{S}_{n}$. Let $B$ be the bijective mapping $B:\mathbf{S}_n \rightarrow \mathbf{S}_n$ that sends every permutation onto its backward permutation, that is, $B(\sigma) = \overline{\sigma}$. Thus, $\mathbf{S}_n = \{ \overline{\sigma}:\, \sigma\in\mathbf{S}_n \}$ and $B(\overline{\sigma}) =\overline{\overline{\sigma}}= \sigma$. It now follows that $N(\overline{\sigma}) = M(\sigma)$ and from Eq.~(\ref{eq15}), we have \begin{equation} N(\overline{\sigma}) + N(\sigma) = \binom{n}{2}. \label{eq17} \end{equation} The power of backward permutations and backward inversions can be best illustrated by offering an alternative proof of Theorem \ref{thm1}. Because $\mathbf{S}_n = \{ \overline{\sigma}:\, \sigma\in\mathbf{S}_n \}$, we have \begin{eqnarray*} 2S_n \ = \ 2\sum_{\sigma\in\mathbf{S}_n} N(\sigma) & = & \sum_{\sigma\in\mathbf{S}_n} N(\sigma) + \sum_{\sigma\in\mathbf{S}_n} N(\overline{\sigma})\\ & = & \sum_{\sigma\in\mathbf{S}_n} [N(\sigma) + N(\overline{\sigma})]\\ & = & \sum_{\sigma\in\mathbf{S}_n} \binom{n}{2}\ \, =\ \, n!\binom{n}{2}, \end{eqnarray*} and the result follows. Using Theorem \ref{thm3}, one can check that if $n \equiv\, 0,1 \pmod{4}$ then $B[\mathbf{A}_n] = \mathbf{A}_n$ and if $n \equiv\, 2,3 \pmod{4}$ then $B[\mathbf{A}_n] = \mathbf{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. \section{Backward permutations in dihedral groups} Consider the regular $n$-gon, with $n\geq 3$. Label successive vertices of the $n$-gon by $1,2,\ldots,n$. The \textit{Dihedral group} $\mathbf{D}_n$ of isometries of the plane which map a regular $n$-gon onto itself can be considered as a subgroup of $\mathbf{S}_n$. To see this, first let us represent the elements of $\mathbf{D}_n$ as permutations. A $(360/n)^{\text{o}}$ clockwise rotation (about the center of the $n$-gon) is represented by the permutation \[ \rho = \left( \begin{array}{ccccc} 1 & 2 & \cdots & n-1 & n\\ 2 & 3 & \cdots & n & 1\end{array}\right). \] Thus, for each $1 \leq k < n$, a $(360k/n)^{\text{o}}$ clockwise rotation can be represented as the permutation $\rho^{k}$ given by \begin{equation} \rho^{k} = \left( \begin{array}{ccccccc} 1 & 2 & \cdots & n-k & n-k+1 & \cdots & n\\ k+1 & k+2 & \cdots & n & 1 & \cdots & k\end{array}\right), \label{eq18} \end{equation} and $\rho^n = \iota$. Note that $\left\langle \rho \right\rangle$ is the subgroup of $\mathbf{D}_n$ consisting of all rotations. Further, for each $k = 1,\ldots, n$, one can see from Eq.~(\ref{eq18}) that $N(\rho^k) = k(n-k)$ and so \[ \sum_{\sigma \in \left\langle \rho \right\rangle} N(\sigma) = \sum_{k=1}^n N(\rho^k) = \sum_{k=1}^n k(n-k) = \frac{n+1}{3}\binom{n}{2}. \] If $n$ is odd, for each $1\leq k \leq n$, let $\mu_k$ be the mirror reflection whose axis bisects the angle corresponding to the vertex $k$ of the $n$-gon. \noindent \textbf{Case 1.} If $2k-1\leq n$ then \begin{equation*} \mu_{k}= \left( \begin{array}{cccccccccc} 1 & 2 & \cdots & k & \cdots & 2k-2 & 2k-1 & 2k & \cdots & n \\ 2k-1 & 2k-2 & \cdots & k & \cdots & 2 & 1 & n & \cdots & 2k \end{array}\right). \end{equation*} It follows that \[ \overline{\mu_{k}} = \left( \begin{array}{cccccccccc} 1 & 2 & \cdots & n-2k+1 & n-2k+2 & n-2k+3 & \cdots & n \\ 2k & 2k+1 & \cdots & n & 1 & 2 & \cdots & 2k-1 \end{array}\right), \] and so $\overline{\mu_{k}}=\rho^{2k-1}$.\\ \textbf{Case 2.} If $2k-1 > n$ then \begin{equation*} \mu_k = \left( \begin{array}{ccccccccccc} 1 & \cdots & 2k-n-1 & 2k-n & \cdots & k & k+1 & \cdots & n \\ 2k-n-1 & \cdots & 1 & n & \cdots & k & k-1 & \cdots & 2k-n \end{array}\right) \end{equation*} and \[ \overline{\mu_{k}} = \left( \begin{array}{cccccccccc} 1 & 2 & \cdots & 2n-2k+1 & 2n-2k+2 & \cdots & n \\ 2k-n & 2k-n+1 & \cdots & n & 1 & \cdots & 2k-n-1 \end{array}\right). \] and thus, $\overline{\mu_{k}}=\rho^{2k-n-1}$. Suppose now that $n$ is even. For $1 \leq k \leq n$, we have $\mu_{k}=\mu_{k+n/2}$ and thus we only need to consider those reflections $\mu_{k}$ for $1 \leq k \leq n/2$. Similarly, it can be shown that $\overline{\mu_{k}}=\rho^{2k-1}$ for all $1\leq k \leq n/2$. Aside from the mirror reflection $\mu_{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, \ldots, n/2$, denote $\mu_{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 \[ \mu_{k,k+1} = \left( \begin{array}{cccccc} 1 & \cdots & 2k & 2k+1 & \cdots & n \\ 2k & \cdots & 1 & n & \cdots & 2k+1 \end{array}\right). \] Taking the backward permutation yields \[ \overline{\mu_{k,k+1}} = \left( \begin{array}{cccccc} 1 & \cdots & n-2k & n-2k+1 & \cdots & n \\ 2k+1 & \cdots & n & 1 & \cdots & 2k \end{array}\right). \] and thus $\overline{\mu_{k,k+1}}=\rho^{2k}$. Hence, the backward permutation of any mirror reflection is a rotation. If $M$ be the set of all mirror reflections in $\mathbf{D}_{n}$, it follows that $B[M]$ is the set of all rotations in $\mathbf{D}_{n}$. We state these results as a theorem. \begin{theorem} If $n \geq 3$ and $M$ is the set of all mirror reflections in $\mathbf{D}_{n}$, then $\left\{M,B[M]\right\}$ partitions $\mathbf{D}_{n}.$ \label{thm4} \end{theorem} Similarly, we define \[ D_n = \sum_{\sigma\in\mathbf{D}_n} N(\sigma) \] and the following theorem gives an explicit formula for $D_n$. \begin{theorem} For all $n \geq 3$ we have \[ D_n = \frac{|\textbf{D}_n|}{2}\binom{n}{2} = n\binom{n}{2}. \] \label{thm5} \end{theorem} \begin{proof} Using the previous theorem, we get \begin{eqnarray*} D_{n} = \sum_{\sigma \in \mathbf{D}_{n}}N(\sigma) &=& \sum_{\sigma \in M}N(\sigma)+\sum_{\sigma \in B[M]}N(\sigma)\\ &=& \sum_{\sigma \in M}N(\sigma) + \sum_{\sigma \in M}N(\overline{\sigma})\\ &=& \sum_{\sigma \in M}\left[N(\sigma)+ N(\overline{\sigma})\right]\\ &=& |M|\binom{n}{2}\ \, = \ \, n\binom{n}{2}. \end{eqnarray*} \end{proof} \begin{corollary} If $t_n$ denotes the $n$th triangular number, then for all $n\geq 3$ we have \[ D_n = \sum_{t_{n-1} < i < t_n} i. \] \label{cor2} \end{corollary} Using Theorems \ref{thm1}, \ref{thm2} and \ref{thm5}, we can generate the following table : { \small \[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & \ \ \ \ 1 \ \ \ \ & \ \ \ \ 2 \ \ \ \ & \ \ \ \ 3 \ \ \ \ & \ \ \ \ 4 \ \ \ \ & \ \ \ \ 5 \ \ \ \ & \ \ \ \ 6 \ \ \ \ & \ \ \ \ 7 \ \ \ \ & 8 & 9 \\ \hline S_{n} & 0 & 1 & 9 & 72 & 600 & 5400 & 52920 & 564480 & 6531840 \\ \hline A_{n} & 0 & 0 & 4 & 36 & 300 & 2700 & 26460 & 282240 & 3265920 \\ \hline D_{n} & & & 9 & 24 & 50 & 90 & 147 & 224 & 324 \\ \hline \hline \end{array} \] } \section{Number of permutations with \textit{k} inversions} Let $I_n(k)$ denotes the number of permutations in $\mathbf{S}_n$ having $k$ inversions. It was shown that the sequence $\{ I_n(k) : 0 \leq k \leq \binom{n}{2}\}$ has the generating function \[ \sum_{k=0}^{\binom{n}{2}} I_n(k)x^k = \prod_{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,\ldots,\binom{n}{2}$, (see \cite{label3}). Also, asymptotic formulas of the sequence $\{I_{n+k}(n) : n\in\mathbb{N}\}$ for a fixed integer $k\geq 0$ were discussed in \cite{label2} and \cite{label3}. In this paper, we employ the partitioning method to provide a recursive formula in finding these inversion numbers. \begin{lemma} For each $0 \leq k \leq \binom{n}{2}$, there exists $\sigma\in\mathbf{S}_n$ such that $N(\sigma) = k$. \label{lem2} \end{lemma} \begin{proof} If $n=1,2$, the statement clearly holds. Assume that the lemma is true for $n-1$. Let $0 \leq k \leq \binom{n}{2}$. For all $1\leq j\leq n$ and $0 \leq l \leq \binom{n-1}{2}$ there exists $\tau \in \mathbf{S}(A-\{j\})$ such that $N(\sigma_{\tau,j}) = (j-1) + N(\tau)$ and $N(\tau) = l$. Observe that the possible values of $(j-1) + N(\tau)$ are $0,1,\ldots, \binom{n}{2}$. Therefore, one can find a $j$ and a $\tau$ such that $\sigma_{\tau,j} \in \mathbf{S}_n$ and $N(\sigma_{\tau,j}) = (j-1) + N(\tau) = k$. \end{proof} We note that $S_n$ and $A_n$ can be represented by the inversion numbers. Indeed, we have \begin{eqnarray*} S_{n} = \sum_{k=0}^{\binom{n}{2}}kI_{n}(k) & \begin{rm}and\end{rm} & A_{n} = \sum_{k = 0}^{\lfloor\frac{1}{2}\binom{n}{2}\rfloor} 2kI_{n}(2k). \end{eqnarray*} \begin{theorem} For $0\leq k \leq \binom{n}{2}$ where $n\geq 2$, we have the following recurrence relation \begin{equation} I_1(0) = I_{2}(0) = I_{2}(1) = 1 \label{eq19} \end{equation} and \begin{equation} I_{n}(k) = \sum_{i=\max\{0,k-n+1\}}^{\min\left\{k,\binom{n-1}{2}\right\}} I_{n-1}(i), \ \ \ n\geq 3. \label{eq20} \end{equation} \label{thm6} \end{theorem} \begin{proof} Eq.~(\ref{eq19}) is clear. Now suppose $n\geq 3$. Recall that $N(\sigma_{\tau, j})=(j-1)+N(\tau)$. Let $N(\sigma_{\tau, j})=k$ and $N(\tau)=i$ then $0\leq i \leq \binom{n-1}{2}$ and $0\leq j-1 \leq n-1$. We find those $i$ such that given $j$, $N(\sigma_{\tau,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\leq k$. Because $i\leq \binom{n-1}{2}$, then $i\leq \min\left\{ k,\binom{n-1}{2} \right\}$. Now $i=k-j+1\geq k-n+1$. But $i$ must be nonnegative and thus $i\geq \max\left\{ 0,k-n+1 \right\}$. Hence, we have Eq.~(\ref{eq20}). \end{proof} With the aid of the previous theorem, we can generate the following table: { \small \[ \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \multicolumn{17}{|c|}{$I_{n}(k)$}\\ \hline $n\backslash k$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ \hline 1 & 1 & & & & & & & & & & & & & & & \\ \hline 2 & 1 & 1 & & & & & & & & & & & & & & \\ \hline 3 & 1 & 2 & 2 & 1 & & & & & & & & & & & & \\ \hline 4 & 1 & 3 & 5 & 6 & 5 & 3 & 1 & & & & & & & & & \\ \hline 5 & 1 & 4 & 9 & 15 & 20 & 22 & 20 & 15 & 9 & 4 & 1 & & & & & \\ \hline 6 & 1 & 5 & 14 & 29 & 49 & 71 & 90 & 101 & 101 & 90 & 71 & 49 & 29 & 14 & 5 & 1\\ \hline \hline \end{tabular} \]} Let $n > 1$. Using Theorem \ref{thm6}, if the value of $I_{n-1}(k)$ for $0\leq k \leq \binom{n-1}{2}$ is known, then the values of $I_n(k)$ for $0\leq k \leq \binom{n}{2}$ can be determined by the following formula \begin{equation} I_n(k) = \begin{cases} \begin{array}{ll} 1, & \quad \text{if } k = 0; \\ I_n(k-1) + I_{n-1}(k), & \quad \text{if } 1\leq k \leq n-1; \\ I_n(k-1) + I_{n-1}(k) - I_{n-1}(k-n), & \quad \text{if } n \leq k \leq \binom{n-1}{2};\\ I_n(k-1) - I_{n-1}(k-n), & \quad \text{if } \binom{n-1}{2} < k \leq \binom{n}{2}. \end{array} \end{cases} \label{eq21} \end{equation} \begin{theorem} For all $0\leq k \leq \binom{n}{2}$ we have $I_{n}\left( \binom{n}{2}-k \right) = I_{n}(k).$ \label{thm7} \end{theorem} \begin{proof} Let $K_{1} = \left\{ \sigma \in \mathbf{S}_{n} : N(\sigma) = k \right\}$ and $K_{2} = \left\{ \sigma \in \mathbf{S}_{n} : N(\sigma) = \binom{n}{2} - k \right\}$, and by Lemma 5.1, $K_1$ and $K_2$ are both nonempty. The mapping $B_1 : K_{1}\rightarrow K_{2}$ defined by $B_1(\sigma) = \overline{\sigma}$ is clearly bijective. Therefore $|K_{1}| = |K_{2}|$ and so $I_{n}\left( \binom{n}{2}-k \right) = I_{n}(k)$. \end{proof} \begin{corollary} If $n\equiv 2,3 \pmod 4$ and $C = \frac{1}{2}\left[\binom{n}{2}-1 \right]$ then $\displaystyle\sum_{k=0}^{C}I_{n}(k) = \frac{n!}{2}.$ \label{cor3} \end{corollary} As an application of Eq.~(\ref{eq21}), we will consider the sequence $\{I_{n+k}(k) : n \geq 0\}$, where $k \geq 1$ is fixed. One can verify, using the second case in Eq.~(\ref{eq21}), 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 \geq 0$. Suppose $I_{n+k}(k) = \sum_{i=0}^k a_{ki}n^i$, where $a_{kk} \neq 0$ so that $deg\ I_{n+k}(k) = k$. Thus \begin{eqnarray*} I_{n+k+1}(k+1) &=& I_{k+1}(k+1) + \sum_{j=1}^n I_{j+1+k}(k)\\ &=& C_{k+1} + \sum_{j=1}^n \sum_{i=0}^k a_{ki}(j+1)^i\\ &=& C_{k+1} + \sum_{j=1}^n \sum_{i=0}^k \sum_{h=0}^i \binom{i}{h}a_{ki}j^h\\ &=& C_{k+1} + \sum_{i=0}^k \sum_{h=0}^i \binom{i}{h}a_{ki}P_{h+1}(n), \end{eqnarray*} for all $n \geq 0$, where $C_{k+1} = I_{k+1}(k+1)$ and $P_{h+1}(n) = \sum_{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 \geq 1$. This result implies that $I_{n}(k) = O(n^k)$ for all $k \geq 1$. \begin{thebibliography}{3} \bibitem{label1} N. Eriksen, (1+$\epsilon$)-approximation of sorting by reversals and transpositions, \textit{Theor. Comput. Sci.} \textbf{289} (2002), 517--529. \bibitem{label2} G. Louchard and H. Prodinger, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Louchard/louchard.html}{The number of inversions in permutations: a saddle point} approach, \textit{J. Integer Sequences} \textbf{6} (2003), Article 03.2.8. \bibitem{label3} B. H. Margolius, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/MARGOLIUS/inversions.html}{Permutations with inversions}, \textit{J. Integer Sequences} \textbf{4} (2001), Article 01.2.4. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A10; Secondary 20B35. \noindent \emph{Keywords:} inversions, permutations, symmetric groups, alternating groups, dihedral groups. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001809} and \seqnum{A006002}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received May 11 2008; revised version received September 29 2008. Published in {\it Journal of Integer Sequences}, October 4 2008. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}