Proof of conjectured formula for A275527 (for n>1)

[Martin Fuller]

I am fairly sure the proof below is right. Is there anything I should do to make it clearer?

Let p be a permutation of 1..n. A275527 gives two operations, cyclic rotation and n+1-complement, and we are told these operations commute with each other.

Define equivalence classes [p] = set of cyclic rotations of p.
These classes are all the same size, #[p] = n, because cyclic rotation of a permutation is order n.

Define another collection of equivalence classes [p]' = set obtained by cyclic rotations and/or n+1-complement.
We have [p]' = [p] union [p'], where p' is the n+1-complement of p, because n+1-complement is order 2 and it commutes with cyclic rotation.
Therefore:
  #[p]' = n if [p] = [p'].
  #[p]' = 2n if [p] != [p'].


Define d(p,i,j) = number of rightward cyclic steps from i to j in permutation p.
Example: d(54312, 1, 5) = 2 because 1 is the 4th entry and 5 is the 1st entry, which is 2 cyclic steps to the right.
Properties of d():
D1: d() is preserved by [p], that is d(p,i,j) = d(q,i,j) for any q in [p].
D2: d(p,i,j) + d(p,j,i) = n if i != j.

Lemma: Suppose n != 1. Then [p] = [p'] => d(p,1,n) = n/2.
Proof:
d(p,1,n) = d(p',n,1)     by the definition of p'.
         = n - d(p',1,n) by property D2.
         = n - d(p,1,n)  by assumption [p] = [p'] and property D1.
         = n/2           by combining like terms.

Theorem: Suppose n != 1 and n is odd. Then a(n) = (n-1)!/2.
Proof: The previous lemma cannot apply, because n/2 is a fraction. Therefore [p] != [p'], and hence #[p]' = 2n for all permutations. Therefore a(n) = n!/(2n) = (n-1)!/2.

Theorem: Suppose n is even. Then a(n) = ((n-1)! + (n-2)!!) / 2 = ((n-1)!! + 1) * (n-2)!! / 2.
Proof: Suppose [p] = [p']. Take a representative p which starts with 1.
Then p = (1, p2, ..., n, n+1-p2, ...).
There are n-2 choices for p2. The complement of this number must follow after n, so there n-4 choices for p3, and so on. This gives (n-2)!! classes altogether with [p] = [p'].
There are (n-1)! - (n-2)!! remaining classes with [p] != [p'], and these count only half towards a(n).

Martin Fuller

[Christian Sievers]

The name of that sequence describes neither of the two methods described in the comments to obtain it.

The sequence can be computed using the [Not] Burnside's / Cauchy-Frobenius lemma by letting the group

C_n X C_2 act on the permutations of [n], where (i,j) rotates by i and also complements iff j=1.

As always, the identity fixes all elements (here: n!).

Arguments similar to yours show that the only other group element that fixes any permutations is (n/2,1) if n is even,

and it fixes n!! permutations.

So we get n!/(2n)=(n-1)!/2 for odd n, and (n!+n!!)/(2n)=((n-1)!+(n-2)!!)/2=...(yes, it's less multiplications, but I dont like it)... for even n.

I liked the sequence a lot more when I saw the nice formula (n!+n!!)/(2n).

Christian