# Adjacent Pairs In Permutations Both Odd...

[Frank Ruskey]

I think this answers your question...

Throughout the set P(n) under
consideration is the the n! permutations
of 1,2,...,n.

Let EE(n), OO(n), EO(n), OE(n) have the obvious meanings,
and E(n) = floor(n/2)*(n-1)! be the number of even numbers that
occur in the first position (same as number in last position),
and O(n) = ceil(n/2)*(n-1)! be the number of odd numbers that
occur in the last position (again the same as the number in first
position).

By thinking of the element n as being inserted in all positions
in each permutation of P(n-1) we are led to the following
recurrence relations

EE(n) = (n+1)*EE(n-1) + EO(n-1) + OE(n-1) + 2*E(n-1) if n even
      = (n-1)*EE(n-1)                                if n odd

EO(n) = n*EO(n-1) + OO(n-1) + O(n-1)  if n even
      = n*EO(n-1) + EE(n-1) + E(n-1)  if n odd

The equations for OO(n) and OE(n) are symmetric (and permutation
reversal tells us that OE = EO anyways).

 From the recurrence relations you can prove by induction that

EO(n) = OE(n) = floor(n/2)*ceil(n/2)*(n-1)!
EE(n) = floor(n/2)*floor(n/2-1)*(n-1)!
OO(n) = ceil(n/2)*ceil(n/2-1)*(n-1)!

Cheers,
Frank R.

----------------------
Frank Ruskey                     e-mail: fruskey at cs.uvic.ca
Dept. of Computer Science        fax:    250-721-7292
University of Victoria           office: 250-721-7232
Victoria, B.C. V8W 3P6 CANADA    WWW: http://www.cs.uvic.ca/~fruskey

On Mon, 4 Nov 2002, Leroy Quet wrote:

> UGGG!! I just checked this numerically with Mathematica, and it didn't
> check out.
>
> >From Mathematica, I have the sequence (of the TOTAL number of occurrences
> of adjacent elements both being odd in all of the permutations) starting
> as:
>
> 0, 0, 4, 12, 144, 720, 8640, 60480, ...
>
> What I am pretty sure of is (what I originally figured out {hopefully
> correctly} & checks out numerically for the values above): If a(m) is the
> m_th term,
>
> a(2m) = (2m-1) a(2m-1).
>
> My original formula works for m <= 4, which threw me off, since I only
> checked my formula numerically by hand for m <= 4.
>
> But I know not the recursive or closed formula for the sequence of
> a(2m-1)s.
>
> I'll maybe continue to work on this or simply give up. It seems like an
> easy problem, but I keep wasting my time making errors.
>
> Thanks,
> 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
>