Consider all one-to-one and onto functions $f:\{1,2,3,4\} \rightarrow \{1,2,3,4\}$ which satisfy: if $f(k)$ is odd then $f(k+1)$ is even, k = 1, 2, 3 Consider all functions $f:\{1,2,3,4\} \rightarrow \{1,2,3,4\}$ which are one-one, onto and satisfy
if $f(k)$ is odd then $f(k+1)$ is even, $k = 1, 2, 3$
What is the total number of such functions?
The first thing that came to mind was to consider $f(k) = x^k$. (Clearly, if $f(k)$ is odd, $f(k+1)$ is even) This function is obviously, a particular case. Any conclusions made using this approach did not help. This answer given is 12.
One of the approaches that I was suggested was to list all possible functions $f$ and then pick the ones which satisfied the condition. This was very easy to do in hindsight but is there some systematic way of doing this. Is there an approach other than brute-force?
 A: Since $(\text{Even},\text{Even},\text{Odd},\text{Odd})$ and $(\text{Odd},\text{Odd},\text{Even},\text{Even})$ and $(\text{Even},\text{Odd},\text{Odd},\text{Even})$ each fail, there are three possibilities patterns on parity:

*

*$(1,2,3,4) \to (\text{Odd},\text{Even},\text{Odd},\text{Even})$

*$(1,2,3,4) \to (\text{Odd},\text{Even},\text{Even},\text{Odd})$

*$(1,2,3,4) \to (\text{Even},\text{Odd},\text{Even},\text{Odd})$
and each of these has $2^2$ ways of distributing the odd and even values.
Extending to $\{1,2,3,\ldots,n\}$

*

*if $n$ is odd then there is one parity pattern so $\left(\frac{n+1}{2}\right)! \left(\frac{n-1}{2}\right)!$ possibilities


*if $n$ is even then there are $\frac n2+1$ parity patterns so $\left(\frac{n+2}{2}\right)! \left(\frac{n}{2}\right)!$ possibilities
This means that there are the same number of $(k+1)!k!$ possibilities for $n=2k$ and $n=2k+1$ starting numbers.  Any pattern with $n$ odd corresponds to a shorter pattern with $n$ deleted from the pattern, and in reverse by inserting odd $n$ before a pattern with an even start, or after a pattern with an even end, or between two evens in a pattern which starts and ends odd.
A: If $f$ is a bijective function from $\{1,2,3,4\}$ to itself, then $f(1),f(2),f(3),f(4)$ are just $1,2,3,4$ in some order, so there is a one-to-one correspondence between such functions and orderings of $1,2,3,4$.
The restriction you have is that an odd number cannot be followed by another odd number, i.e. $1$ and $3$ are not consecutive in the ordering. The answer is the total number of orderings minus the number where $1,3$ are consecutive, both of which you should be able to calculate. (Hint for the second part: combine $1$ and $3$ to force them to be together, then double because they could be $1,3$ or $3,1$.)
