This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A131209 Maximal distance between two signed permutations of n elements. 1
 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, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS See also the comments in A058986 for background information. Comments from Glenn Tesler (Start): Let d_max = a(n) be the maximal distance. 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. The formula for reversal distance is d = n + 1 - c + h + f, 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). It turns out that c >= h+f. 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. So we may rewrite distance as d = n+1 - (c-h-f), where c-h-f>=0. Thus d_max <= n+1. Except for n=0,1,3, it turns out we can make c-h-f=0. When n=0: d(null,null) = 0, so d_max = 0 (has c=1, h=0) When n=1: d( 1, -1 ) = 1, d( 1, 1 ) = 0, so d_max = 1 (first one has c=1, h=0) When n=2: d( 2 1, 1 2 ) = 3, all other d(sigma, 1 2) < 3 (has c=h=1) When n=3: d_max = 3 (25 solutions, found by brute force; 20 with c=1, h=0; 5 with c=2, h=1) 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 n=2m: n 1 m+1 2 m+2 3 m+3 ... m-1 2m-1 m (has c=h=1) n=2m+1: n 1 m+1 2 m+2 3 m+3 ... m 2m (has c=h=2) 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. 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) REFERENCES Brian Hayes, Sorting out the genome, Amer. Scientist, 95 (2007), 386-391. LINKS FORMULA a(n) = n+1 except for n=0,1,3. CROSSREFS Cf. A058986, A078941. Sequence in context: A078796 A201929 A079789 * A116592 A152772 A089175 Adjacent sequences:  A131206 A131207 A131208 * A131210 A131211 A131212 KEYWORD nonn AUTHOR Brian Hayes (bhayes(AT)amsci.org), Oct 26 2007, based on email from Glenn Tesler (gptesler(AT)math.ucsd.edu) STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .