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?
Best Answer
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:
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.