# Adjacent Pairs In Permutations Both Odd...

[Leroy Quet]

Just sent this to sci.math:


Consider all of the m! permutations of {1,2,3,4,...,m}.

I THINK (I think that I think) that

the TOTAL number of occurrences of adjacent elements both being odd in 
all of the permutations is:

2 * (m-1)! * floor((m-1)/2)

If so, then the number of times (over all permutations) that adjacent 
elements are odd would approach an average of once per permutation as m 
approaches infinity.

--

Now, the total number of occurrences of any elements being adjacent in 
all permutations of {1,2,3,...,m} is:
(m-1) * m!


We can get the same set of permutations by simply subtracting every 
element of each permutation from (m+1). If m is even, then the resulting 
permutations have elements with parity reversed from the original 
permutations.
So the number of occurrences of EVEN elements being adjacent in all of 
the permutations of {1,2,3,...,m} is, for EVEN m, the same as for odd 
elements:

2 * (m-1)! * floor((m-1)/2)

= (m-1)! (m-2)

So, if I am right, the total number of occurrences of an odd element 
being next to an even element (together with the number of occurrences of 
an even element being next to an odd element) is, for even m:

(m-1) * m! - 2 * (m-1)! * (m-2) =

(m-1)! (m^2 - 3m + 4)

Half of this is for the number of occurrences of an odd being before an 
even.
And (the other...) half is for the number of occurrences of an even being 
before 
an odd.

So, the number of occurrences of two elements of identical-parity being 
adjacent over all permutations of {1,2,3,...m} is of O(m!).

While the number of occurrences of two elements of opposite-parity being 
adjacent is of O(m!m).

Therefore, IF true, the number of opposite-parity pairs grows much faster 
than the number of same-parity pairs.

But this seems counter-intuitive to me. Is there an easy way to see this 
intuitively as fact, if, in fact, it is indeed fact?

Thanks,
Leroy Quet