You can search some small test data, then the solution is here:
For f[n], there're three ways to construct it.
Put 2 onto 2nd position, then it's f[n-1];
Put 3 onto 2nd position, put 2 onto 3rd position. This is
f[n-3]! (You must put 4 onto 4th position)
The last condition contains only one possible way like that (first odd, then even)
13578642
So f[n]=f[n-1]+f[n-3]+1.

Good Job!You're quite clever!

Pal, you must have pains in eggs.....

Really nice! How you get that, really smart!