
356 Combinatorics of Permutations, Second Edition
where the lower bound is assured by the decreasing permutation. That, of
course, does not mean that the decreasing permutation is indeed the most
difficult to sort, but for several years, no n-permutation p was known to
satisfy btd(p) > btd(n ···21). That changed when in 2004 Isaac Elias and
Tzvika Hartman [114] presented the following result.
PROPOSITION 9.7
Let i be a non-negative integer. Then the permutation
EH(i)=432151312···614171615···14 + 4i 17+4i 16+4i 15 + 4i
has block transposition distance 10+2i.
In other words, EH(i) consists of the following parts.
1. The decreasing sequence 4321,
2. the fixed ...