\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{amsfonts} % \mathbb (set N) \usepackage{amsmath} % \eqref \usepackage{amsthm} % theorem, proof environments \usepackage{fullpage} % increase printing area \usepackage{graphicx} % \includegraphics, \rotatebox \usepackage[all]{xy} % Package used for drawings (\xymatrix) \CompileMatrices % to avoid reconstruction of matrices at each compilation \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 On Hultman Numbers } \vskip 1cm \large Jean-Paul Doignon and Anthony Labarre \\ Universit\'e Libre de Bruxelles\\ D\'epartement de Math\'ematique, c.p.~216\\ Bd du Triomphe\\ B-1050 Bruxelles\\ Belgium\\ \href{mailto:doignon@ulb.ac.be}{\tt doignon@ulb.ac.be} \\ \href{mailto:alabarre@ulb.ac.be}{\tt alabarre@ulb.ac.be} \\ \end{center} \vskip .2 in \begin{abstract} Finding a sequence of transpositions that transforms a given permutation into the identity permutation and is of the shortest possible length is an important problem in bioinformatics. Here, a transposition consists in exchanging two contiguous intervals of the permutation. Bafna and Pevzner introduced the cycle graph as a tool for working on this problem. In particular, they took advantage of the decomposition of the cycle graph into so-called alternating cycles. Later, Hultman raised the question of determining the number of permutations with a cycle graph containing a given quantity of alternating cycles. The resulting number is therefore similar to the Stirling number of the first kind. We provide an explicit formula for computing what we call the Hultman numbers, and give a few numerical values. We also derive formulae for related cases, as well as for a much more general problem. Finally, we indicate a counting result related to another operation on permutations called the ``block-interchange''. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \section{Introduction} Bafna and Pevzner~\cite{bafna-transpositions} introduced the biologically related problem of finding a sequence of ``transpositions'' that transforms a given permutation into the identity permutation and is of the shortest possible length. Here, a \emph{transposition} consists in exchanging two contiguous intervals of the permutation. The length of such a sequence is called the \emph{distance} of the permutation. The computational complexity of this problem is open, and the best polynomial-time approximation algorithm, by Elias and Hartman~\cite{elias-better-journal}, has a ratio of $\frac{11}{8}$. In order to study this problem, Bafna and Pevzner introduced an equivalent representation of a permutation using a bicoloured directed graph, called the \emph{cycle graph} and hereafter denoted by $G$. Later, Eriksson et al.~\cite{eriksson-bridge} introduced an equivalence relation on the symmetric group, which is of great interest to the sorting problem described above, because two permutations that are equivalent with respect to this relation have the same distance. Hultman~\cite{hultman-toric} enumerated the corresponding equivalence classes (Sequence~\seqnum{A002619} of The On-line Encyclopedia of Integer Sequences~\cite{sloane-oeis} -- OEIS for short). He also noticed that the structure of $G$ is preserved under this equivalence relation, whereas the classical disjoint cycle decomposition of the permutation is in general not preserved. This led him to propose an analogue of the Stirling number of the first kind based on $G$, and to ask for a determination of the resulting number. We present a bijection between the set of permutations of $n$ elements whose cycle graph $G$ contains $k$ alternating cycles, on the one hand, and, on the other hand, the set of factorisations of a given $(n+1)$-cycle into the product of an $(n+1)$-cycle and a permutation whose disjoint cycle decomposition contains $k$ cycles. As a corollary, the cardinalities of the two sets are equal, and an explicit formula for the Hultman numbers follows for instance from Goupil and Schaeffer~\cite{goupil-factoring}. In fact, our approach leads to more general counting results for permutations whose cycle graph $G$ has a given cycle type. Our paper is organised as follows. In Section~\ref{sec:notations}, we introduce the notions and notation we will use, and state the counting problem raised by Hultman. Section~\ref{sec:bijection} presents a bijection that leads to an explicit formula for the Hultman numbers, which we derive in Section~\ref{sec:explicit-formula-hultman-numbers} together with the solution of a more general problem. We provide a few explicit values of the Hultman numbers in Section~\ref{sec:consequences}, as well as simple expressions for a few particular cases. Finally, we briefly consider another distance on permutations, called the ``block-interchange distance'', and indicate how to count permutations at any given distance. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Notation and Definitions}\label{sec:notations} The notation $S_n$ stands for $\mathrm{Sym}(\{1,2,\ldots,n\})$. A permutation $\pi$ in $S_n$ can be described in the two row notation $ \left(\begin{array}{cccc}1 & 2 & \cdots & n\\ \pi_1 & \pi_2 & \cdots & \pi_n\end{array}\right), $ where $\pi_i=\pi(i)$. We shorten the writing by keeping only the second row within angle brackets, i.e., $\pi=\langle\pi_1\ \pi_2\ \cdots\ \pi_n\rangle$. The usual {\sl graph} $\Gamma(\pi)$ of the permutation $\pi$ contains an edge $(i,j)$ whenever $\pi_i=j$. The graph $\Gamma(\pi)$ decomposes in a unique way into disjoint cycles, leading to another notation for $\pi$ based on its {\sl disjoint cycle decomposition}. For instance, when $\pi=\langle 4\ 1\ 6\ 2\ 5\ 7\ 3\rangle$, the disjoint cycle notation is $\pi=(1,4,2)(3,6,7)(5)$ (notice the parentheses and commas). The number of cycles in $\Gamma(\pi)$ is denoted by $c(\Gamma(\pi))$. We also work with $\mathrm{Sym}(\{0,1,2,\ldots,n\})$, abbreviated to $S(1+n)$, whose elements will be described by their disjoint cycle decomposition. Product of permutations (both in $S_n$ or in $S(1+n$)) is denoted by $\circ$ and applied from right to left: when writing $\pi\circ\sigma$, we first apply $\sigma$, then $\pi$. \begin{definition} The {\sl Stirling number of the first kind} $\mathcal{S}(n,k)$ counts the number of permutations $\pi$ in $S_n$ whose disjoint cycle decomposition contains $k$ cycles (i.e., $c(\Gamma(\pi))=k$). \end{definition} A more general counting situation occurs when the ``(conjugacy) class'' of the relevant permutations is completely specified. \begin{definition}\label{def:partition} A {\sl partition} $\lambda=(\lambda_1, \lambda_2, \ldots, \lambda_l)$ is a finite sequence of integers called {\sl parts} such that $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_l>0$. Its {\sl length} is $l$, and we write $\lambda\vdash n$ if $\sum_{i=1}^{l}\lambda_i=n$; then $\lambda$ is a {\sl partition of} $n$. A permutation $\pi$ in $S_n$ is of {\sl class} $\lambda$ if $\lambda$ is obtained by writing in non-increasing order the various lengths of the disjoint cycles in $G(\pi)$; we then set $\lambda=C(\pi)$. \end{definition} The number of permutations $\pi$ in $S_n$ of a given class $\lambda$ is easily derived (see for instance Proposition~4.1 in~\cite{stanley-enumerative}): let $\alpha_i$ denote the number of $\lambda_j$'s that are equal to $i$ (for $1\leq i\leq n$), and set $z_{\lambda}=\prod_i\alpha_i!\,i^{\alpha_i}$; then the number of permutations of class $\lambda$ equals $n! \,/\, z_\lambda$. The reader may be less familiar with the following structure, introduced by Bafna and Pevzner~\cite{bafna-transpositions}. Our definition slightly differs from theirs, but the minor modification we make does not affect the features of interest here. \begin{definition}\label{def:cycle-graph} The {\sl cycle graph} of a permutation $\pi$ in $S_n$ is the bicoloured directed graph $G(\pi)$ with vertex set $\{\pi_0=0,\pi_1, \ldots, \pi_n\}$ and whose edge set consists of \begin{itemize} \item black edges $(\pi_i, \pi_{(i-1)\bmod(n+1)})$ for $0\leq i\leq n$, and \item grey edges $(i, (i+1)\bmod(n+1))$ for $0\leq i\leq n$. \end{itemize} \end{definition} \noindent Quite often we list the vertices of $G(\pi)$ in the order $\pi_0$, $\pi_1$, \dots, $\pi_n$. The set of black and grey edges decomposes in a unique way into edge-disjoint {\sl alternating cycles}, i.e., cycles in $G(\pi)$ which alternate black and grey edges. The number of alternating cycles in $G(\pi)$ is denoted by $c(G(\pi))$. Figure~\ref{fig:cycle-graph-example} shows an example of a cycle graph, together with its decomposition, where black edges are drawn using continuous arrows and grey edges are drawn using dashed arrows. \begin{figure}[htbp] \centering\ \centering \xymatrix@1@=0pt@C=36pt{ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ (a)&{\bullet}\ar@{-->}@/^1.2pc/[rr]\ar@/^12pc/[rrrrrrr] & {\bullet}\ar[l]\ar@{-->}@/^3pc/[rrrr] & {\bullet}\ar@{-->}@/^2pc/[rr]\ar[l] & {\bullet}\ar@{-->}@/^2.5pc/[rrr]\ar[l] & {\bullet}\ar@{-->}@/^1.5pc/[rrr]\ar[l] & {\bullet}\ar@{-->}@/_1pc/[ll]\ar[l] & {\bullet}\ar@{-->}@/_6pc/[llllll]\ar[l] & {\bullet}\ar[l]\ar@{-->}@/_7pc/[llllll] \\ & 0 & 4 & 1 & 6 & 2 & 5 & 7 & 3 \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ (b)&{\bullet}\ar@{-->}@/^1.2pc/[rr]\ar@/^12pc/[rrrrrrr] & {\bullet}\ar[l]\ar@{-->}@/^3pc/[rrrr] & {\bullet}\ar[l] & {\bullet} & {\bullet}\ar@{-->}@/^1.5pc/[rrr] & {\bullet}\ar[l] & {\bullet}\ar@{-->}@/_6pc/[llllll] & {\bullet}\ar[l]\ar@{-->}@/_7pc/[llllll] \\ & 0 & 4 & 1 & 6 & 2 & 5 & 7 & 3 \\ & & & & & & & & \\ & & & & & & & & \\ & & & & & & & & \\ (c)&{\bullet} & {\bullet} & {\bullet}\ar@{-->}@/^2pc/[rr] & {\bullet}\ar[l]\ar@{-->}@/^3pc/[rrr] & {\bullet}\ar[l] & {\bullet}\ar@{-->}@/_1pc/[ll] & {\bullet}\ar[l] & {\bullet} \\ & 0 & 4 & 1 & 6 & 2 & 5 & 7 & 3 } \caption{$(a)$ The cycle graph of $\langle 4\ 1\ 6\ 2\ 5\ 7\ 3\rangle$; $(b),(c)$ its decomposition into two alternating cycles} \label{fig:cycle-graph-example} \end{figure} Hultman~\cite{hultman-toric} proposed an analogue of the Stirling number of the first kind based on the cycle graph. \begin{definition} The {\sl Hultman number} $\mathcal{S}_H(n,k)$ counts the number of permutations in $S_n$ whose cycle graph decomposes into $k$ alternating cycles. Thus: $$ \mathcal{S}_H(n,k)=|\{\pi\in S_n\ |\ c(G(\pi))=k\}|. $$ \end{definition} Hultman does not obtain a full characterisation of these numbers, but notes that $\mathcal{S}_H(n,n+1)=1$ and $\mathcal{S}_H(n,n-1)=\binom{n+2}{4}$. It is also obvious that $\mathcal{S}_H(n,k)=0$ for all $k\not\in[1, n+1]$, since $G(\pi)$ always contains at least one alternating cycle and at most $n+1$ alternating cycles. \begin{lemma}\label{lemma:parity-c-G} \cite{hultman-toric} For all $\pi$ in $S_n$, we have $c(G(\pi)) \equiv n+1 \pmod 2.$ \end{lemma} Lemma~\ref{lemma:parity-c-G} immediately yields the following corollary. \begin{corollary}\label{corollary:hultman-numbers-same-parity} For all $k\equiv n \pmod 2$, we have $\mathcal{S}_H(n,k)=0.$ \end{corollary} We will provide a solution to the more general problem of counting permutations in $S_n$ whose cycle graph has a given structure. The {\sl length} of an alternating cycle is the number of its black edges (or equivalently, grey edges). \begin{definition} A permutation $\pi$ in $S_n$ has {\sl Hultman class} $\lambda$ if $\lambda$ is obtained by writing in non-increasing order the various lengths of the edge-disjoint alternating cycles in $G(\pi)$. We then set $C_H(\pi)=\lambda$. \end{definition} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Bijection}\label{sec:bijection} We now construct a bijection from the set of permutations $\pi$ in $S_n$ with $c(G(\pi))=k$ and the set of factorisations in $S(1+n)$ of a given $(n+1)$-cycle into some $(n+1)$-cycle and some permutation $\sigma$ with $c(\Gamma(\sigma))=k$. Let first $\pi$ be any permutation in $S_n$, and consider the edges of the cycle graph $G(\pi)$. The grey edges are the pairs $(i, (i+1)\bmod(n+1))$, for $0\leq i\leq n$, which form the following $(n+1)$-cycle (independent of $\pi$) in $S(1+n)$: $$ \alpha = (0,\, 1,\, \dots,\, n). $$ Similarly, the black edges $(\pi_i, \pi_{(i-1) \bmod (n+1)})$, for $0\leq i\leq n$, form the following $(n+1)$-cycle in $S(1+n)$: $$ \dot \pi = (0, \pi_n,\, \pi_{n-1},\, \dots, \pi_1). $$ Notice that the mapping $S_n \to S(1+n): \pi \mapsto \dot \pi$ is injective. Moreover, its co-domain is the set of all $(n+1)$-cycles in $S(1+n)$. By Definition~\ref{def:cycle-graph}, the alternating cycles in the graph $G(\pi)$ build up a permutation $\mathring{\pi}$ in $S(1+n)$ that maps $i$ onto $j$ when there is a black edge from $(i+1) \bmod (n+1)$ to $j$ (remember that $(i,(i+1) \bmod (n+1))$ is always a grey edge). Thus we have $\mathring{\pi}=\dot{\pi} \circ \alpha$, that is \begin{equation}\label{eq-alpha} \alpha = \dot{\pi}^{-1} \circ \mathring{\pi}. \end{equation} As an example, the alternating cycle decomposition of the cycle graph of Figure~\ref{fig:cycle-graph-example} yields the permutation \begin{eqnarray*} \mathring{\pi}&=&(0,\, 4,\, 2,\, 7,\, 3) \, (1,\, 6,\, 5)\\ &=&(0,\, 3,\, 7,\, 5,\, 2,\, 6,\, 1,\, 4) \circ (0,\, 1,\, 2,\, 3,\, 4,\, 5,\, 6,\, 7). \end{eqnarray*} \begin{theorem}\label{thm:bijection-hultman-factorisations} Let $\alpha=(0,\, 1,\, \dots,\, n)$. The mapping \begin{eqnarray*} F&:&\{\pi\in S_n\ |\ c(G(\pi))=k\}\rightarrow\\ &&\{\sigma\in S(1+n)\ |\ c(\Gamma(\sigma))=k \mbox{ and }\exists\ \rho\in S(1+n): c(\Gamma(\rho))=1\mbox{ and } \alpha=\rho\circ\sigma\}\\ &:&\pi\mapsto\mathring{\pi} \end{eqnarray*} is bijective. \end{theorem} \begin{proof} First note that $F$ is well defined. If $\pi\in S_n$, then $\mathring\pi$ satisfies $\alpha=\rho \circ \mathring\pi$, where $\rho=\dot\pi^{-1}$ is an $(n+1)$-cycle (cf.~Equation~\eqref{eq-alpha}). Moreover, we have $c(G(\pi))=c(\Gamma(\mathring\pi))$. Since the mapping $S_n \to S(1+n): \pi \mapsto \dot{\pi}$ is injective, the injectivity of $F$ follows from Equation~\eqref{eq-alpha}. On the other hand, every $(n+1)$-cycle $\rho$ in $S(1+n)$ is of the form $\dot\pi^{-1}$ for some $\pi$ in $S_n$; because $\alpha=\rho \circ \sigma$, Equation~\eqref{eq-alpha} implies $\sigma=\mathring\pi$. Therefore $F$ is also surjective (remember $c(G(\pi))=c(\Gamma(\mathring\pi))$). \end{proof} Given any $(n+1)$-cycle $\beta$ in $S(1+n)$, define $D(n+1,k)$ as the number of factorisations of $\beta$ into the product $\rho\circ\sigma$, where $\rho$ is some $(n+1)$-cycle and $\sigma$ some permutation in $S(1+n)$ having $c(\Gamma(\sigma))=k$. We get the following result. \begin{corollary}\label{cor:bijection-hultman-factorisations} For all $n$, $k$ in $\mathbb{N}$, we have $\mathcal{S}_H(n,k)=D(n+1,k)$. \end{corollary} The bijection $F$ in Theorem~\ref{thm:bijection-hultman-factorisations} is induced by a much more general bijection, which is established along the same arguments. \begin{theorem}\label{thm:bijection-hultman-classs} Let $\lambda$ be a partition of $n+1$. The mapping \begin{eqnarray*} F&:&\{\pi\in S_n\ |\ C_H(\pi)=\lambda \}\rightarrow\\ &&\{\sigma\in S(1+n)\ |\ C(\sigma)=\lambda \mbox{ and }\exists\ \rho\in S(1+n): c(\Gamma(\rho))=1\mbox{ and } \alpha=\rho\circ\sigma\}\\ &:&\pi\mapsto\mathring{\pi} \end{eqnarray*} is bijective. \end{theorem} We finish this section by noting that using a very similar approach, although working with another conjugacy class of $S(1+n)$, Hultman~\cite{hultman-toric} characterises what he calls ``valid decompositions'' of the cycle graph. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{An Explicit Formula for the Hultman Numbers}\label{sec:explicit-formula-hultman-numbers} Several authors give formulae for the number $D(n,k)$ of factorisations of an $n$-cycle into the product $\rho\circ\sigma$, where $\rho,\sigma\in S_n$, $\rho$ is an $n$-cycle, and $c(\Gamma(\sigma))=k$ (see, e.g., Goupil~\cite{goupil-products} or Stanley~\cite{stanley-factorization}). Goupil and Schaeffer~\cite{goupil-factoring} give a general formula for the number of factorisations of an $n$-cycle into two permutations of given classes, expressed as a summation of only non-negative terms. We will use their result and Theorem~\ref{thm:bijection-hultman-factorisations} to derive a formula for computing $\mathcal{S}_H(n,k)$. \begin{definition}\label{def:composition} A {\sl composition} $\lambda=(\lambda_1, \lambda_2, \ldots, \lambda_l)$ is a finite sequence of non-negative integers. Its {\sl length} is $l$. If $\sum_{i=1}^{l}\lambda_i=n$, we say that $\lambda$ is a {\sl composition of} $n$ and we write $\lambda \models n$. \end{definition} Denote $c^{(n)}_{\lambda\mu}$ the number of ways to express a given $n$-cycle as the product of two permutations whose classes are given respectively by partitions $\lambda$ and $\mu$. \begin{theorem}\label{thm:goupil-schaeffer}\cite{goupil-factoring} Let $\lambda=(\lambda_1, \ldots, \lambda_l)$ and $\mu=(\mu_1, \ldots, \mu_k)$ be any two partitions of $n$, and set $g=\frac{n+1-l(\lambda)-l(\mu)}{2}$. Then $$ c^{(n)}_{\lambda\mu} = \frac{n}{z_{\lambda}z_{\mu}2^{2g}} \sum_{ \begin{array}{c} \scriptstyle (g_1,g_2)\models g \end{array} } (l+2g_1-1)!\,(k+2g_2-1)! \sum_{ \begin{array}{c} \scriptstyle (i_1, \ldots, i_l)\models g_1 \\ \scriptstyle (j_1, \ldots, j_k)\models g_2 \end{array} } \prod_{h_1=1}^l \binom{\lambda_{h_1}}{2i_{h_1}+1}\prod_{h_2=1}^k \binom{\mu_{h_2}}{2j_{h_2}+1}. $$ \end{theorem} From the previous section, we need to count the number of factorisations of a given $n$-cycle into an $n$-cycle and a permutation with $k$ disjoint cycles. In the present notation, this number is the sum of $c^{(n)}_{(n)\mu}$ over all partitions $\mu$ of $n$ with $l(\mu)=k$. \begin{lemma}\label{lemma:goupil-schaeffer-n-k} The number of ways to express a given $n$-cycle as the product of an $n$-cycle and a permutation of class given by $\mu=(\mu_1,\ldots,\mu_k)$ is $$ c^{(n)}_{(n)\mu} \;=\; \frac{n!}{z_{\mu}2^{n-k}} \sum_{i=0}^{\frac{n-k}{2}}\frac{1}{2i+1} \sum_{(j_1, \ldots, j_k)\models\frac{n-k}{2}-i}\; \prod_{h=1}^k \binom{\mu_h}{2j_h+1}. $$ \end{lemma} \begin{proof} Simplification of the formula of Theorem~\ref{thm:goupil-schaeffer} in the case where $\lambda=(n)$. As we have $l=1$, there is a unique composition $(g_1)\models g_1$. Therefore \begin{equation*} \sum_{\begin{array}{c} \scriptstyle (i_1, \ldots, i_l)\models g_1 \\ \scriptstyle (j_1, \ldots, j_k)\models g_2 \end{array}} \prod_{h_1=1}^l \binom{\lambda_{h_1}}{2i_{h_1}+1} \prod_{h_2=1}^k \binom{\mu_{h_2}}{2j_{h_2}+1} \;=\; \binom{n}{2g_1+1}\sum_{(j_1, \ldots, j_k)\models g_2} \prod_{h_2=1}^k \binom{\mu_{h_2}}{2j_{h_2}+1}.\\ \end{equation*} \noindent On the other hand, $l(\mu)=k$, so $g=\frac{n-k}{2}$, also $g_2=g-g_1$, and we have \begin{equation*} (l+2g_1-1)!\,(k+2g_2-1)! = (2g_1)!\,(n-2g_1-1)!, \end{equation*} which simplifies further when both sides are multiplied by $\binom{n}{2g_1+1}$: \begin{eqnarray*} (l+2g_1-1)!\,(k+2g_2-1)!\,\binom{n}{2g_1+1}=\frac{(2g_1)!\,(n-2g_1-1)!\,n!}{(2g_1+1)!\,(n-2g_1-1)!}=\frac{n!}{2g_1+1}.\\ \end{eqnarray*} Finally, note that $z_{\lambda}=\prod_i\alpha_i!\,i^{\alpha_i}=1!\,n^1=n$. Hence $$ \frac{n}{z_{\lambda}z_{\mu}2^{2g}}=\frac{n}{nz_{\mu}2^{n-k}}=\frac{1}{z_{\mu}2^{n-k}}. $$ All these operations lead to the following simplification of the formula in Theorem~\ref{thm:goupil-schaeffer}: $$ c^{(n)}_{(n)\mu}= \frac{n!}{z_{\mu}2^{n-k}} \sum_{\begin{array}{c} \scriptstyle (g_1,g_2)\models g \end{array}} \frac{1}{2g_1+1} \sum_{(j_1, \ldots, j_k)\models g_2}\; \prod_{h_2=1}^k \binom{\mu_{h_2}}{2j_{h_2}+1}. $$ Setting $g_1=i$, we obtain $g_2=\frac{n-k}{2}-i$ and then the required equality. \end{proof} We can now give an explicit formula for computing the Hultman number $\mathcal{S}_H(n,k)$. \begin{theorem}\label{thm:explicit-formula-for-hultman-numbers} For all $n$, $k$ in $\mathbb{N}$: \begin{eqnarray}\label{formula:hultman-numbers} \mathcal{S}_H(n,k)= \frac{(n+1)!}{2^{n+1-k}} \sum_{(\mu_1,\ldots,\mu_k)\vdash(n+1)}\frac{1}{z_{\mu}} \sum_{i=0}^{\frac{n+1-k}{2}}\frac{1}{2i+1} \sum_{(j_1, \ldots, j_k)\models\frac{n+1-k}{2}-i} \; \prod_{h=1}^k \binom{\mu_h}{2j_h+1}\ . \end{eqnarray} \end{theorem} \begin{proof} Clearly, $D(n+1,k)=\sum_{(\mu_1,\ldots,\mu_k)\vdash(n+1)}c^{(n+1)}_{(n+1)\mu}$. Equation~\eqref{formula:hultman-numbers} follows from Corollary~\ref{cor:bijection-hultman-factorisations} and Lemma~\ref{lemma:goupil-schaeffer-n-k}. \end{proof} Using this time Theorem~\ref{thm:bijection-hultman-classs} together with Lemma~\ref{lemma:goupil-schaeffer-n-k}, we similarly derive \begin{theorem}\label{thm:explicit-formula-for-class} The number of permutations $\pi$ in $S_n$ having Hultman class $\mu=(\mu_1,\ldots,\mu_k)$ equals $$ c^{(n+1)}_{(n+1)\mu}= \frac{(n+1)!}{z_{\mu}2^{n+1-k}} \sum_{i=0}^{\frac{n+1-k}{2}}\frac{1}{2i+1} \sum_{(j_1, \ldots, j_k)\models\frac{n+1-k}{2}-i}\; \prod_{h=1}^k \binom{\mu_h}{2j_h+1}. $$ \end{theorem} We now turn to particular cases, where simpler formulae can be obtained. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Consequences}\label{sec:consequences} A first consequence of Theorem~\ref{thm:bijection-hultman-factorisations} is the derivation of two simple formulae for particular values of $\mathcal{S}_H(n,k)$ and $D(n+1,k)$: \begin{enumerate} \item for all even $n$, we have $\mathcal{S}_H(n,1)=2\frac{n!}{n+2}$; \item for all $n$ in $\mathbb{N}$, we have $D(n+1,n-1)=\binom{n+2}{4}$. \end{enumerate} On the other hand, Theorem~\ref{thm:explicit-formula-for-class} paves the way for some other counting formulae. ``Simple'' permutations, ``$2$-permuta\-tions'' and ``$3$-permutations'' in $S_n$ play an important role in genome rearrangement (see for instance Hannenhalli and Pevzner~\cite{hannenhalli-transforming}, or Elias and Hartman~\cite{elias-better-journal}). As in the work of Labarre~\cite{labarre-new}, these permutations can be defined as follows. \begin{definition} A permutation $\pi$ in $S_n$ is {\sl simple} if $G(\pi)$ has no alternating cycle of length greater than three. \end{definition} \begin{definition} A permutation $\pi$ in $S_n$ is a {\sl $2$-permutation} (resp.\ {\sl $3$-permutation}) if all alternating cycles in $G(\pi)$ have length $2$ (resp.\ $3$). \end{definition} Note that $2$-permutations (resp. $3$-permutations) only exist when $4$ (resp.\ $3$) divides $n+1$. The number of simple permutations can be obtained by restricting partitions $(\mu_1,\ldots,\mu_k)$ of $n+1$ in Theorem~\ref{thm:explicit-formula-for-class} to those made up only of 1's, 2's and 3's. More compact formulae for counting elements of the two other classes are derived as follows. \begin{enumerate} \item The number of $2$-permutations in $S_n$ is $$\frac{(n+1)!}{\left(\frac{n+1}{2}+1\right)!\,2^\frac{n+1}{2}}.$$ \begin{proof} In Theorem~\ref{thm:explicit-formula-for-class}, let $\mu=(\underbrace{2,2,\ldots,2}_{\frac{n+1}{2}})$. Thus $k=\frac{n+1}{2}$ and the number of $2$-permutations in $S_n$ is therefore \begin{eqnarray*} \lefteqn{ \frac{(n+1)!}{\left(\frac{n+1}{2}\right)!\,2^{\frac{n+1}{2}}2^{n+1-\frac{n+1}{2}}} \sum_{i=0}^{\frac{n+1-\frac{n+1}{2}}{2}}\frac{1}{2i+1} \sum_{(j_1, \ldots, j_\frac{n+1}{2})\models\left(\frac{n+1-\frac{n+1}{2}}{2}-i\right)} \prod_{h=1}^\frac{n+1}{2} \binom{2}{2j_h+1} }\hspace{30mm}\\ &=&\frac{(n+1)!}{\left(\frac{n+1}{2}\right)!\,\,2^{n+1}} \sum_{i=0}^{\frac{n+1}{4}}\frac{1}{2i+1} \sum_{(j_1, \ldots, j_\frac{n+1}{2})\models\left(\frac{n+1}{4}-i\right)} \prod_{h=1}^\frac{n+1}{2} \binom{2}{2j_h+1}. \end{eqnarray*} Since $\frac{n+1}{4}\geq i$, we have two cases: \begin{enumerate} \item if $\frac{n+1}{4}>i$, then there exists $1\leq h_0\leq h$ such that $j_{h_0}\geq 1$, which implies $\binom{2}{2j_{h_0}+1}=0=\prod_{h=1}^\frac{n+1}{2} \binom{2}{2j_h+1}$. \item if $\frac{n+1}{4}=i$, then the only composition of $0$ being obviously $(0,\ldots,0)$ we derive $\prod_{h=1}^\frac{n+1}{2} \binom{2}{2j_h+1}=2^\frac{n+1}{2}$. \end{enumerate} Consequently, the number of $2$-permutations in $S_n$ equals \begin{equation*} \frac{(n+1)!}{\left(\frac{n+1}{2}\right)!\,2^{n+1}}\; \frac{1}{2\frac{n+1}{4}+1}\; 2^\frac{n+1}{2}, \end{equation*} which gives the wanted expression. \end{proof} Removing all $0$'s from the resulting sequence yields Sequence~\seqnum{A035319} in OEIS, which counts certain maps on orientable surfaces. A bijection relating those maps to special factorisations of cycles is derived from Proposition 4.1 in~\cite{goupil-factoring}. In turn, our Theorem~\ref{thm:explicit-formula-for-class} explains why Sequence~\seqnum{A035319} also counts $2$-permutations. \item The number of $3$-permutations in $S_n$ is \begin{eqnarray*} &&\frac{(n+1)!}{\left(\frac{n+1}{3}\right)!\,12^{\frac{n+1}{3}}}\sum_{i=0}^{\frac{n+1}{3}} \binom{\frac{n+1}{3}}{i}\frac{3^{i}}{2i+1}. \end{eqnarray*} \begin{proof} In Theorem~\ref{thm:explicit-formula-for-class}, let this time $\mu=(\underbrace{3,3,\ldots,3}_{\frac{n+1}{3}})$. Thus $k=\frac{n+1}{3}$ and the number of $3$-permutations in $S_n$ is therefore \begin{eqnarray*} &&\frac{(n+1)!}{\left(\frac{n+1}{3}\right)!\,3^{\frac{n+1}{3}}\,2^{n+1-\frac{n+1}{3}}} \sum_{i=0}^{\frac{n+1-\frac{n+1}{3}}{2}}\frac{1}{2i+1} \sum_{(j_1, \ldots, j_\frac{n+1}{3})\models\frac{n+1-\frac{n+1}{3}}{2}-i} \prod_{h=1}^\frac{n+1}{3} \binom{3}{2j_h+1}\\ &=&\frac{(n+1)!}{\left(\frac{n+1}{3}\right)!\,12^{\frac{n+1}{3}}} \sum_{i=0}^{\frac{n+1}{3}}\frac{1}{2i+1} \sum_{(j_1, \ldots, j_\frac{n+1}{3})\models\frac{n+1}{3}-i} \prod_{h=1}^\frac{n+1}{3} \binom{3}{2j_h+1}. \end{eqnarray*} The binomial coefficient at the end of the last expression takes value $1$ when $j_h=1$, value $3$ when $j_h=0$, and value $0$ otherwise. In the last summation, we may thus assume $j_h\in\{0,1\}$ for all $h$. Then the number of $j_h$ equal to $1$ in every composition of $\frac{n+1}{3}-i$ is $\frac{n+1}{3}-i$, the number of $j_h$ equal to $0$ is $i$, and there are exactly $\binom{\frac{n+1}{3}}{i}$ such compositions. Therefore the number of $3$-permutations in $S_n$ is $$\frac{(n+1)!}{\left(\frac{n+1}{3}\right)!\,12^{\frac{n+1}{3}}}\sum_{i=0}^{\frac{n+1}{3}} \binom{\frac{n+1}{3}}{i}\frac{3^{i}}{2i+1}.$$ \end{proof} \end{enumerate} Table~\ref{tab:number-of-simple-permutations} gives a few values of the number of simple permutations, $2$-permutations, and $3$-permutations. The sequences for simple or $3$-permutations do not appear in the OEIS. \begin{table}[H] \centering { \begin{tabular}{r|r|r|r|r|r|r|r|r|r|r|r} $n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline simple & 1 & 2 & 6 & 16 & 48 & 204 & 876 & 3\,636 & 18\,756 & 105\,480 & 561\,672 \\ $2$- & 0 & 0 & 1 & 0 & 0 & 0 & 21 & 0 & 0 & 0 & 1\,485 \\ $3$- & 0 & 1 & 0 & 0 & 12 & 0 & 0 & 464 & 0 & 0 & 38\,720 \end{tabular} } \caption{Number of simple permutations, $2$-permutations, and $3$-permutations in $S_n$} \label{tab:number-of-simple-permutations} \end{table} Finally, our counting results may also be used to infer the distribution of those rearrangement distances based on the cycle graph. For instance, Christie~\cite{christie-block} generalised transpositions, which exchange contiguous intervals in a permutation, to the case where the exchanged intervals need not be contiguous, resulting in an operation called a {\sl block-interchange}. By contrast with transpositions, finding an optimal sorting sequence of block-interchanges can be done in polynomial time, and the induced distance of a permutation $\pi$ in $S_n$ is given by $(n+1-c(G(\pi)))/2$ (see Christie~\cite{christie-block}). Therefore the number of permutations in $S_n$ whose block-interchange distance is $k$ is exactly $\mathcal{S}_H(n,n+1-2k)$, which can be computed as in Theorem~\ref{thm:explicit-formula-for-hultman-numbers}. We conclude with a few numerical values of $\mathcal{S}_H(n,k)$, shown in Table~\ref{tab:hultman-numbers}. Note that the successive values of $\mathcal{S}_H(n,1)$ ($n=2, 4, \ldots$) form Sequence~\seqnum{A060593} in OEIS~\cite{sloane-oeis} (in the context of cycle factorisations), whereas the other values do not appear in OEIS (except of course for $\binom{n+2}{4}$). \begin{table}[H] \centering \rotatebox{90} { \begin{tabular}{r|rrrrrrrrrrrrrr} $n \backslash^{\displaystyle k}$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ & $12$ \\ & & & & & & & & & & & & \\ \hline 1 & 0 & 1 & & & & & & & & & &\\ 2 & 1 & 0 & 1 & & & & & & & & &\\ 3 & 0 & 5 & 0 & 1 & & & & & & & &\\ 4 & 8 & 0 & 15 & 0 & 1 & & & & & & &\\ 5 & 0 & 84 & 0 & 35 & 0 & 1 & & & & & &\\ 6 & 180 & 0 & 469 & 0 & 70 & 0 & 1 & & & & &\\ 7 & 0 & 3\,044 & 0 & 1\,869 & 0 & 126 & 0 & 1 & & && \\ 8 & 8\,064 & 0 & 26\,060 & 0 & 5\,985 & 0 & 210 & 0 & 1 & && \\ 9 & 0 & 193\,248 & 0 & 152\,900 & 0 & 16\,401 & 0 & 330 & 0 & 1 & & \\ 10 & 604\,800 & 0 & 2\,286\,636 & 0 & 696\,905 & 0 & 39\,963 & 0 & 495 & 0 & 1 &\\ 11 & 0 & 19\,056\,960 & 0 & 18\,128\,396 & 0 & 2\,641\,925 & 0 & 88\,803 & 0 & 715 & 0 & 1 \end{tabular} } \caption{A few values of $\mathcal{S}_H(n, k)$} \label{tab:hultman-numbers} \end{table} \section{Acknowledgments} We thank the referees for helpful comments, which resulted in an improved exposition. This research is supported by ``Communaut\'e fran\c caise de Belgique - Actions de Recherche Concert\'ees". The second author is funded by the ``Fonds pour la Formation \`a la Recherche dans l'Industrie et dans l'Agriculture'' (F.R.I.A.). % \newpage \begin{thebibliography}{10} \bibitem{bafna-transpositions} {V.~Bafna and P.~A. Pevzner}, {Sorting by transpositions}, {\em SIAM J. Discrete Math.}, \textbf{11} (1998), 224--240. \bibitem{christie-block} {D.~A. Christie}, {Sorting permutations by block-interchanges}, {\em Inform. Process. Lett.}, \textbf{60} (1996), 165--169. \bibitem{elias-better-journal} {I.~Elias and T.~Hartman}, {A $1.375$-approximation algorithm for sorting by transpositions}, {\em IEEE/ACM Transactions on Computational Biology and Bioinformatics}, \textbf{3} (2006), 369--379. \bibitem{eriksson-bridge} {H.~Eriksson, K.~Eriksson, J.~Karlander, L.~Svensson, and J.~W{\"a}stlund}, {Sorting a bridge hand}, {\em Discrete Math.}, \textbf{241} (2001), 289--300. \bibitem{goupil-products} {A.~Goupil}, {On products of conjugacy classes of the symmetric group}, {\em Discrete Math.}, \textbf{79} (1989/90), 49--57. \bibitem{goupil-factoring} {A.~Goupil and G.~Schaeffer}, {Factoring {$n$}-cycles and counting maps of given genus}, {\em European J. Combin.}, \textbf{19} (1998), 819--834. \bibitem{hannenhalli-transforming} {S.~Hannenhalli and P.~A. Pevzner}, {Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals}, {\em J. ACM}, \textbf{46} (1999), 1--27. \bibitem{hultman-toric} {A.~Hultman}, {\em Toric permutations}, Master's thesis, Department of Mathematics, KTH, Stockholm, Sweden, 1999. \bibitem{labarre-new} {A.~Labarre}, {New bounds and tractable instances for the transposition distance}, {\em IEEE/ACM Transactions on Computational Biology and Bioinformatics}, \textbf{3} (2006), 380--394. \bibitem{sloane-oeis} {N.~J.~A. Sloane}, {\em The On-Line Encyclopedia of Integer Sequences}. \newblock Published electronically at \href{http://www.research.att.com/~njas/sequences/}{\url{http://www.research% .att.com/\~njas/sequences/}}. \bibitem{stanley-factorization} {R.~P. Stanley}, {Factorization of permutations into {$n$}-cycles}, {\em Discrete Math.}, \textbf{37} (1981), 255--262. \bibitem{stanley-enumerative} {R.~P. Stanley}, {\em Enumerative Combinatorics}, Vol.~1, Cambridge University Press, Cambridge, Great Britain, 1999. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15 ; Secondary 05A05. \noindent {\sl Keywords: } permutations, Stirling numbers of the first kind, Hultman numbers. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A002619}, \seqnum{A035319}, and \seqnum{A060593}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received December 23 2005; revised versions received August 21 2006; June 9 2007. Published in {\it Journal of Integer Sequences}, June 10 2007. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .