This site is supported by donations to The OEIS Foundation.

 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. R. de A. Hausen et al. showed that 9 <= a(16) <= 10. LINKS H. Eriksson et al., 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. doi:10.1007/978-3-540-85557-6_8 J. Gonçalves, L. R. Bueno, R. A. Hausen, Assembling a New and Improved Transposition Distance Database, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013. FORMULA It is conjectured that a(n) = ceiling((n+1)/2) for n >= 3 except for n = 13 and 15. 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.

Last modified July 23 00:43 EDT 2019. Contains 325228 sequences. (Running on oeis4.)