|
|
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
|
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.
|
|
FORMULA
|
It is conjectured that a(n) = ceiling((n+1)/2) for n >= 3 except for n = 13 and 15.
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
|
|
|
KEYWORD
|
nonn,nice,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Definition corrected by Peter Lipp, Dec 16 2008
|
|
STATUS
|
approved
|
|
|
|