[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
> Quadruple factorial numbers: (2n)!/n!.
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
VSA v3.6.0 licensed by XenonServer
for any support visit http://www.XenonServer.de
----------------------------------------------------
More information about the SeqFan
mailing list