login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A065603 Transposition diameter: maximal number of moves in an optimal sorting of n objects by moving blocks. 2
0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 8, 9 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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

Table of n, a(n) for n=1..15.

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

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)

CROSSREFS

Cf. A164366, A219243

Sequence in context: A120835 A091374 A266977 * A225215 A214672 A268060

Adjacent sequences:  A065600 A065601 A065602 * A065604 A065605 A065606

KEYWORD

nonn,nice,more,hard

AUTHOR

N. J. A. Sloane, Dec 02 2001

EXTENSIONS

Definition corrected by Peter Lipp, Dec 16 2008

Edited by Max Alekseyev, Nov 07 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 10:14 EDT 2021. Contains 348211 sequences. (Running on oeis4.)