%I A131209
%S A131209 0,1,3,3,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,
%T A131209 26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
%U A131209 48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69
%N A131209 Maximal distance between two signed permutations of n elements.
%C A131209 See also the comments in A058986 for background information.
%C A131209 Comments from Glenn Tesler (Start): Let d_max = a(n) be the maximal distance.
%C A131209 Then d_max = n for n=0,1,3; d_max = n+1 except for n=0,1,3; however, 
               there are many permutations achieving the max, not just the 2 Gollan 
               permutations as in the unsigned case.
%C A131209 The formula for reversal distance is d = n + 1 - c + h + f,
%C A131209 where c is the number of cycles in the breakpoint graph, h is the number 
               of "hurdles" and f is the number of "fortresses" (0 or 1).
%C A131209 It turns out that c >= h+f.
%C A131209 This is because each hurdle is comprised of one or more cycles, distinct 
               from those in other hurdles and fortresses can be worked into that 
               too.
%C A131209 So we may rewrite distance as d = n+1 - (c-h-f), where c-h-f>=0. Thus 
               d_max <= n+1.
%C A131209 Except for n=0,1,3, it turns out we can make c-h-f=0.
%C A131209 When n=0: d(null,null) = 0, so d_max = 0 (has c=1, h=0)
%C A131209 When n=1: d( 1, -1 ) = 1, d( 1, 1 ) = 0, so d_max = 1 (first one has 
               c=1, h=0)
%C A131209 When n=2: d( 2 1, 1 2 ) = 3, all other d(sigma, 1 2) < 3 (has c=h=1)
%C A131209 When n=3: d_max = 3 (25 solutions, found by brute force; 20 with c=1, 
               h=0; 5 with c=2, h=1)
%C A131209 When n>3: d_max = n+1 and there are many solutions, obtained by creating 
               a situation in which c=h, f=0. One of them is
%C A131209 n=2m: n 1 m+1 2 m+2 3 m+3 ... m-1 2m-1 m (has c=h=1)
%C A131209 n=2m+1: n 1 m+1 2 m+2 3 m+3 ... m 2m (has c=h=2)
%C A131209 Note that these are indeed signed permutations, in which all signs happen 
               to be positive. This is because "hurdles" require all the signs to 
               be the same.
%C A131209 Also note that these are just examples to show at least one permutation 
               has d=n+1, which proves d_max=n+1 by the bound; however, there are 
               many more signed permutations that also achieve d=n+1. (End)
%D A131209 Brian Hayes, Sorting out the genome, Amer. Scientist, 95 (2007), 386-391.
%F A131209 a(n) = n+1 except for n=0,1,3.
%Y A131209 Cf. A058986, A078941.
%Y A131209 Sequence in context: A161560 A078796 A079789 this_sequence A116592 A152772 
               A089175
%Y A131209 Adjacent sequences: A131206 A131207 A131208 this_sequence A131210 A131211 
               A131212
%K A131209 nonn
%O A131209 0,3
%A A131209 Brian Hayes (bhayes(AT)amsci.org), Oct 26 2007, based on email from Glenn 
               Tesler (gptesler(AT)math.ucsd.edu)