##
**
On Hultman Numbers
**

###
Jean-Paul Doignon and Anthony Labarre

Université Libre de Bruxelles

Département de Mathématique, c.p. 216

Bd du Triomphe

B-1050 Bruxelles

Belgium

**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".

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequences
A002619
A035319 and
A060593
.)

Received December 23 2005;
revised versions received August 21 2006; June 9 2007.
Published in *Journal of Integer Sequences*, June 10 2007.

Return to
**Journal of Integer Sequences home page**