|
%I #39 Dec 17 2019 07:42:13
%S 0,1,2,3,3,4,4,5,5,6,6,7,8,8,9
%N Transposition diameter: maximal number of moves in an optimal sorting of n objects by moving blocks.
%C Arises in sorting cards in a bridge hand; also in computational biology because block move is a fundamental type of mutation, called transposition.
%C de A. Hausen et al. (2008) showed that 9 <= a(16) <= 10.
%H V. Bafna and P. A. Pevzner, <a href="https://doi.org/10.1137/S089548019528280X">Sorting by transpositions</a>, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
%H V. Bafna and P. A. Pevzner, <a href="http://www.ic.unicamp.br/~meidanis/courses/mo640/2007s1/textos/Bafna-Pevzner-1998.pdf">Sorting by transpositions</a>, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240.
%H H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wästlund, <a href="http://www.math.chalmers.se/~wastlund/Sorting.pdf">Sorting a bridge hand</a>, Discrete Math. 241 (2001), 289-300.
%H H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wästlund, <a href="https://doi.org/10.1016/S0012-365X(01)00150-9">Sorting a bridge hand</a>, Discrete Math. 241 (2001), 289-300.
%H R. de A. Hausen, L. Faria, C. M. H. de Figueiredo, and L. A. B. Kowada, <a href="http://dx.doi.org/10.1007/978-3-540-85557-6_8">On the toric graph as a tool to handle the problem of sorting by transpositions</a>, LNCS 5167 (2008), 79-91.
%H J. Gonçalves, L. R. Bueno, and R. A. Hausen, <a href="https://pdfs.semanticscholar.org/b9df/0c38ed7fca7d5046513de19895412c9ff2c0.pdf">Assembling a New and Improved Transposition Distance Database</a>, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.
%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%F It is conjectured that a(n) = ceiling((n+1)/2) for n >= 3 except for n = 13 and 15.
%F From _Petros Hadjicostas_, Dec 16 2019: (Start)
%F 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)).
%F ceiling((n+1)/2) <= a(n) <= floor((2*n-2)/3) for n >= 3 (see p. 293 in Eriksson et al. (2001)). (End)
%Y Cf. A164366, A219243
%K nonn,nice,more,hard
%O 1,3
%A _N. J. A. Sloane_, Dec 02 2001
%E Definition corrected by Peter Lipp, Dec 16 2008
%E Edited by _Max Alekseyev_, Nov 07 2011
|
