cp's OEIS Frontend

See also the comments in A058986 for background information.

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 composed 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 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)

Or, number of 2-sided polyedges with n cells. - Ed Pegg Jr, May 13 2009

A walk and its reflection (i.e., exchange start and end of walk, what Hayes calls a "retroreflection") are considered one and the same here. - Joerg Arndt, Jan 26 2018

With A001411 as main input and counting the symmetrical shapes separately, higher terms can be computed efficiently (see formula). - Bert Dobbelaere, Jan 07 2019