A065603 Transposition diameter: maximal number of moves in an optimal sorting of n objects by moving blocks.

0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 8, 9

Offset: 1

Author

N. J. A. Sloane, Dec 02 2001

Keywords

• nonn
• nice
• more
• hard

Comments

Arises in sorting cards in a bridge hand; also in computational biology because block move is a fundamental type of mutation, called transposition.

de A. Hausen et al. (2008) showed that 9 <= a(16) <= 10.

Links

• V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
• V. Bafna and P. A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
• H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wästlund, Sorting a bridge hand, Discrete Math. 241 (2001), 289-300.
• H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wästlund, Sorting a bridge hand, Discrete Math. 241 (2001), 289-300.
• R. de A. Hausen, L. Faria, C. M. H. de Figueiredo, and L. A. B. Kowada, On the toric graph as a tool to handle the problem of sorting by transpositions, LNCS 5167 (2008), 79-91.
• J. Gonçalves, L. R. Bueno, and R. A. Hausen, Assembling a New and Improved Transposition Distance Database, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.
• Index entries for sequences related to sorting

Crossrefs

Cf. A164366, A219243

Formula

It is conjectured that a(n) = ceiling((n+1)/2) for n >= 3 except for n = 13 and 15.

From Petros Hadjicostas, Dec 16 2019: (Start)

ceiling((n-1)/2) <= a(n) <= floor(3*n/4) for n >= 1 (Eriksson et al. (2001) state that these inequalities were proved in Bafna and Pevnzer (1998)).

ceiling((n+1)/2) <= a(n) <= floor((2*n-2)/3) for n >= 3 (see p. 293 in Eriksson et al. (2001)). (End)

Extensions

Definition corrected by Peter Lipp, Dec 16 2008

Edited by Max Alekseyev, Nov 07 2011