Combinatorics problems involving permutations Let $A= \{ 1,2,3,...,n\}$ a set and $f:A \to A$ a permutation of the set A. We call a number $x \in \{ 2,3,...,n-1 \}$ special if $f(x)>\max \{f(x-1),f(x+1) \}$ or $f(x)<\min \{f(x-1),f(x+1) \}.$ Determine the number of permutation with odd number of special numbers.
 A: HINT: It’s clear that there are no such permutations when $n<3$, and $n=3$ turns out to be a special case easily handled by brute force, so assume that $n\ge 4$.


*

*Show that $f$ has an odd number of special numbers if and only if either $f(1)<f(2)$ and $f(n-1)>f(n)$, or $f(1)>f(2)$ and $f(n-1)<f(n)$. (I.e., $f$ must have an ascent at $1$ and a descent at $n-1$, or a descent at $n=1$ and an ascent at $n-1$.)  

*If $f$ is any permutation of $[n]=\{1,\ldots,n\}$, let $\hat f$ be the permutation of $[n]$ defined by interchanging the values of $f(1)$ and $f(2)$: $\hat f(1)=f(2)$, $\hat f(2)=f(1)$, and $\hat f(k)=f(k)$ if $3\le k\le n$. Show that the map $f\mapsto\hat f$ is a bijection on the set of permutations of $[n]$.  

*Show that $f$ has an odd number of special numbers if and only if $\hat f$ has an even number of special numbers.  

*Use the last two points to get a simple closed form for the number of permutations of $[n]$ with an odd number of permutations.


Alternatively, you can use the following slightly clumsier approach that starts with the same basic insight.


*

*Show that $f$ has an odd number of special numbers if and only if either $f(1)<f(2)$ and $f(n-1)>f(n)$, or $f(1)>f(2)$ and $f(n-1)<f(n)$.  

*How many ways are there to choose $f(1),f(2),f(n-1)$, and $f(n)$ and order them to match the first bullet point?  

*How many ways are there to choose the rest of $f$?


Now put the pieces together and simplify.
