cp's OEIS Frontend

A131209 Maximal distance between two signed permutations of n elements.

%I A131209 #10 Oct 22 2013 13:06:01
%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,26,
%T A131209 27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,
%U A131209 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 From Glenn Tesler: (Start)
%C A131209 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 composed 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 that 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.
%K A131209 nonn
%O A131209 0,3
%A A131209 _Brian Hayes_, Oct 26 2007, based on email from Glenn Tesler (gptesler(AT)math.ucsd.edu)