|
| |
|
|
A065603
|
|
Transposition diameter: maximal number of moves in an optimal sorting of n objects by moving blocks.
|
|
1
| |
|
|
0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 8, 9
(list; graph; refs; listen; history; 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.
|
|
|
REFERENCES
| 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
|
|
|
LINKS
| H. Eriksson et al., Sorting a bridge hand, Discrete Math., 241 (2001), 289-300.
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.
|
|
|
CROSSREFS
| Cf. A164366
Sequence in context: A005410 A120835 A091374 * A084242 A194806 A156261
Adjacent sequences: A065600 A065601 A065602 * A065604 A065605 A065606
|
|
|
KEYWORD
| nonn,nice,more,hard
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Dec 02 2001
|
|
|
EXTENSIONS
| Definition corrected by Peter Lipp, Dec 16 2008
Edited by Max Alekseyev (maxale(AT)gmail.com), Nov 07 2011
|
| |
|
|
