# Adjacent Pairs In Permutations Both Odd...

[Frank Ruskey]

I think this answers your question...

Throughout the set P(n) under
consideration is the set of 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 first position (again the same as the number in
the last 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.

==============================================================================

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
> 
> -------
> 

-- 
----------------------
Frank Ruskey                     e-mail: fruskey at cs.uvic.ca <- NEW!
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