
How Did We Get Here? Permutations as Genome Rearrangements. 381
12. Let us say that the permutation p = p
1
p
2
···p
n
has a bond in i ∈ [0,n]if
p
i+1
= p
i
+1, where p
0
=0andp
n+1
= n+ 1. State and prove a slightly
stronger version of Theorem 9.6 in terms of the number of bonds of p.
13. Sort the permutation 963852741 with five block transpositions.
14. Let p be an n-permutation, and let us sort p by block interchanges in
which each block consists of one entry. Find a formula for the number
of such operations needed to sort p.
15. (–) Let p be an n-permutation, and let is(p) be the length of the longest
increasing subsequence of p.Provethatbtd(n) ≤ n − is(p), a