Find the number of ways there are to permute the elements of the set {1,2,3,4,5,6,7,8,9} such that no two adjacent numbers are both even or both odd.

There are 6054 permutations.