Permutations of [n]

Oct 2009
255
20
St. Louis Area
How many permutations of [n] are possible in which no even numbers and no odd numbers are adjacent?

Take [5] = 1 2 3 4 5. The ways to arrange the even numbers are 2 4 and 4 2 as long as stay in the even number slots. Then the way to arrange the odd numbers are 1 3 5; 1 5 3; 3 1 5; 3 5 1; 5 1 3; and 5 3 1. The number of permutations of [5] in which no even numbers and no odd numbers are adjacent is 2! * 3! or 2P2 times 3P3.

So I see the formula as two cases if n is even then it would be

\(\displaystyle _{\frac{n}{2}}P_{\frac{n}{2}}\) * \(\displaystyle _{\frac{n}{2}}P_{\frac{n}{2}}\)

If n is an odd number then

\(\displaystyle _{\frac{n+1}{2}}P_{\frac{n+1}{2}}\) * \(\displaystyle _{\frac{n-1}{2}}P_{\frac{n-1}{2}}\)

This seems too complicated.

Is there a way to calculate the total number of permutations n! and subtract the cases where the even numbers would be adjacent and the cases where the odd numbers would be adjacent?
 

Plato

MHF Helper
Aug 2006
22,458
8,632
Those are almost correct.

In the case n being even we need to double your formula.
Consider [4], ‘1432’ is a correct string. But so is ‘4123’.
You did not take that into consideration.

You are correct in the case n is odd.
 
  • Like
Reactions: oldguynewstudent
Oct 2009
255
20
St. Louis Area
Those are almost correct.

In the case n being even we need to double your formula.
Consider [4], ‘1432’ is a correct string. But so is ‘4123’.
You did not take that into consideration.

You are correct in the case n is odd.
Thank you again. You're explanations are well appreciated!