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, which also follows from a general inequality given by Eriksson et al. (2001).
LINKS
Vineet Bafna and Pavel A. Pevzner, Sorting by transpositions, SIAM Journal on Discrete Mathematics, 11 (1998), 224-240. (alternative link)
A. Chervov et al., CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version), arXiv:2509.19162 [math.CO], 2025. See p. 36.
Henrik Eriksson, Kimmo Eriksson, Johan Karlander, Lars Svensson, and Johan Wästlund, Sorting a bridge hand, Discrete Math. 241 (2001), 289-300. (alternative link)
Rodrigo de A. Hausen, Luerbio Faria, Celina M. H. de Figueiredo, and Luis Antonio B. Kowada, On the toric graph as a tool to handle the problem of sorting by transpositions, LNCS 5167 (2008), 79-91.
Jamile Gonçalves, L. R. Bueno, and Rodrigo de A. Hausen, Assembling a New and Improved Transposition Distance Database, in Simpósio Brasileiro de Pesquisa Operacional, Sept. 2013.
FORMULA
Eriksson et al. (2001) 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
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, Sep 18 2025
STATUS
approved