Geodesic
On Hultman numbers
Journal of integer sequences, Tome 10 (2007) no. 6.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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".
Keywords: permutations, Stirling numbers of the first kind, hultman numbers 
@article{JIS_2007__10_6_a7,
     author = {Doignon, Jean-Paul and Labarre, Anthony},
     title = {On {Hultman} numbers},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {10},
     number = {6},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2007__10_6_a7/}
}
TY  - JOUR
AU  - Doignon, Jean-Paul
AU  - Labarre, Anthony
TI  - On Hultman numbers
JO  - Journal of integer sequences
PY  - 2007
VL  - 10
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2007__10_6_a7/
LA  - en
ID  - JIS_2007__10_6_a7
ER  - 
%0 Journal Article
%A Doignon, Jean-Paul
%A Labarre, Anthony
%T On Hultman numbers
%J Journal of integer sequences
%D 2007
%V 10
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2007__10_6_a7/
%G en
%F JIS_2007__10_6_a7
Doignon, Jean-Paul; Labarre, Anthony. On Hultman numbers. Journal of integer sequences, Tome 10 (2007) no. 6. http://geodesic.mathdoc.fr/item/JIS_2007__10_6_a7/