# [seqfan] Re: Permutation inverse = inversion

jens at voss-ahrensburg.de jens at voss-ahrensburg.de
Tue Aug 31 08:40:53 CEST 2010

> A curiosity that just came up
>
> 1,0,0,2,2,0,0,12,12,0,0,120,120,0,0,1680,1680,0,0,30240,30240
> Number of permutations of 1..n p(i) with inverse permutation q(i) equal
to
> the
> inversion: q(i)=n+1-p(i)
>
> [...]
>
> the nonzero counts match
>
> http://www.research.att.com/~njas/sequences/A001813

This is actually quite easy to see:

Let p be a permutation on the numbers 1, ..., n with
the required property

(*)  p(k) + p^(-1)(k) = n + 1  for all k € {1, ..., n}

Applying this to p^(-1)(k) instead of k shows that
p^2 must be an involution with p^2(k) = n + 1 - k
for all k; in particular the only possible fixed
point of p^2 can be (n+1)/2.

This shows that p must be a product of 4-cycles
with at most one fixed point (n+1)/2, with each
pair of "opposing vertices" of the cycles adding
up to n+1.

Conversely, if q is such a product of 4-cycles with
the described properties, then (*) holds.

Therefore, in order to determine the number a(n) of
permutations satisfying (*), you need to count all
possible products of 4-cycles with the described
properties.

First, it is clear that there are no such
permutations if n is congruent 2 or 3 (mod 4) and
that for n divisible by 4, the numbers a(n) and
a(n+1) are identical.

Let n = 4k and let p be a permutation with (*).
Then every 4-cycle factor of p (e.g. (a b c d)
in cycle notation with a < c and b < d) is
determined by the smaller of the opposing
vertices, i.e. a and c, plus an "orientation",
thus a(n) equals the number of ways to split up
the "smaller half" of the numbers {1, ..., n}
(i.e. {1, ..., 2k}) into groups of 2, multiplied
by 2 to the k-th power. But this number is just
(2k)!/k!

Best regards,
Jens
--
----------------------------------------------------
message sent through VSA Webmail v0.96
(c) 2010 October Labs http://www.october-labs.de