In how many ways can the elements of [n] be permuted so that the sum of every two consecutive elements in the permutation is odd?
[n] is the set of integers from 1 to n.
If n is even:
If n is odd, we must start with an odd element:
Is this right?