Here is an argument completely different from joriki’s; it is also a complete solution.
A cycle is an odd permutation iff its length is even, so a permutation written as a product of disjoint cycles is even iff an even number of the factors are even cycles. Let $\pi=\sigma_1\dots\sigma_k$ be a permutation of $[n]$ written as a product of $k$ disjoint cycles. Then $n=|\,\sigma_1|+\dots+|\,\sigma_k|$, so the parity of $n$ is the same as the parity of the number of cycles of odd length. Thus, $\pi$ has an even number of cycles of even length iff $n$ and $k$ have the same parity, i.e., iff $(-1)^{n+k}=1$.
Let $e_n$ be the total number of cycles in even permutations of $[n]$, let $o_n$ be the total number of cycles in odd permutations of $[n]$, and let $d_n=e_n-o_n$. The total number of permutations of $[n]$ with $k$ cycles is given by $\left[n\atop k\right]$, the unsigned Stirling number of the first kind. Each of these $\left[n\atop k\right]$ permutations contributes $k$ cycles to $e_n$ if $(-1)^{n+k}=1$, and to $o_n$ if $(-1)^{n+k}=(-1)$. Thus, each contributes $(-1)^{n-k}k$ to $d_n$, and it follows that
$$d_n=\sum_k(-1)^{n+k}k\left[n\atop k\right]\;.$$
Now $(-1)^{n+k}\left[n\atop k\right]=(-1)^{n-k}\left[n\atop k\right]$ is the signed Stirling number of the first kind, for which we have the generating function $$\sum_k(-1)^{n+k}\left[n\atop k\right]x^k=x^{\underline{n}}\;.\tag{1}$$
(Here $x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)$ is the falling factorial, sometimes written $(x)_n$.)
Differentiate $(1)$ with respect to $x$ to obtain
$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=Dx^{\underline{n}}=(x-n+1)Dx^{\underline{n-1}}+x^{\underline{n-1}}\;,$$
where the last step is simply the product rule, since $x^{\underline{n}}=x^{\underline{n-1}}(x-n+1)$. But $$Dx^{\underline{n-1}}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}\;,$$ so
$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}+x^{\underline{n-1}}\;.\tag{2}$$
Now evaluate $(2)$ at $x=1$ to get $$d_n=(2-n)d_{n-1}+[n=1]\;,\tag{3}$$ where the last term is an Iverson bracket. If we set $d_0=0$, $(3)$ yields $d_1=[1=1]=1$, which by direct calculation is the correct value: the only permutation of $[1]$ is the identity, which is even and has one cycle. It’s now a trivial induction to check that $d_n=(-1)^n(n-2)!$ for all $n\ge 1$: the induction step is
$$\begin{align*}d_{n+1}&=\Big(2-(n+1)\Big)d_n\\
&=(1-n)(-1)^n(n-2)!\\
&=(-1)^{n+1}(n-1)!\;.
\end{align*}$$
Added: It occurs to me that there’s a rather easy argument that does not use generating functions. Let $\sigma$ be any $k$-cycle formed from elements of $[n]$; then $\sigma$ is a factor in $(n-k)!$ permutations of $[n]$. Moreover, exactly half of these permutations are even unless $n-k$ is $0$ or $1$. Thus, $\sigma$ contributes to $d_n$ iff $k=n$ or $k=n-1$.
There are $(n-1)!$ $n$-cycles; they are even permutations iff $n$ is odd, so they contribute $(-1)^{n-1}(n-1)!$ to $d_n$.
There are $n(n-2)!$ $(n-1)$-cycles: there are $n$ ways to choose the element of $n$ that is not part of the $(n-1)$-cycle, and the other $n-1$ elements can be arranged in $(n-2)!$ distinct $(n-1)$-cycles. The resulting permutation of $[n]$ is even iff $n-1$ is odd, i.e., iff $n$ is even, so they contribute $(-1)^nn(n-2)!$ to $d_n$.
It follows that $$\begin{align*}d_n&=(-1)^nn(n-2)!+(-1)^{n-1}(n-1)!\\
&=(-1)^n\Big(n(n-2)!-(n-1)!\Big)\\
&=(-1)^n(n-2)!\Big(n-(n-1)\Big)\\
&=(-1)^n(n-2)!\;.
\end{align*}$$
Here is the proof, from Bolker and Gleason, Counting Permuations.
It is well known that any permutation of A can be written as a product
of disjoint cycles. This representation is not strictly unique because
of ambiguities of order (e.g., (ab)(cd) and (dc)(ab) represent the
same permutation). However, if a linear order relation is imposed on
A, then we can pick out a canonical way to write a permutation of A as
a product of cycles by observing the following rules :
(a) Even trivial cycles of length one are written.
(b) Each cycle is written so that its least member occurs at the end.
(c) The cycles are written so that their least members increase.
Hence, if A = {a, b, c, d, e, f g} with alphabetical order, the
permutation (a c e) (g d f) has the canonical form (c e a) (b) (f g
d). Now in this canonical form the parentheses marking the cycle
boundaries can be dispensed with; there is no loss of information if
we write the above permutation simply as the arrangement c e a b f g
d, because a cycle closes whenever we come to an element which
precedes in the ordering of A all the elements that follow it in the
arrangement. We obtain in this way a one-to-one correspondence between
the arrangements of A and the permutations of A.
Best Answer
Example
Consider the permutation $\sigma = [1 3 2]\in S_3$ (which is $1\mapsto 1$, $2\mapsto 3$, $3\mapsto 2$). In the standard representation introduced in the exercise, $\sigma = (1)(3,2)$. Now $\hat{\sigma} = [1 3 2] = \sigma$, so $\sigma$ is fixed under $\hat{{}}$.
Solution
Let $A(n)$ be the number of fixed permutations in $S_n$. We see that $A_1 = 1$ and $A_2 = 2$, i.e. in $S_1$ and $S_2$, all permutationes are fixed.
Now let $n \geq 3$. Let $\pi\in S_n$ be fixed under the transformation. Consider the largest number $n$. In the standard representation, $n$ is the first element of the last cycle. If the last cycle has length $1$ (i.e. it has the form (n), which is a fixed point), then $\pi$ is fixed if and only if after removing the cycle $(n)$, the resulting permutation is fixed in $S_{n-1}$.
Now assume the last cycle of $\pi$ is $(n,\ldots,a)$ of length $\geq 2$. Then $\hat{\pi}(n) = a$. So also $\pi(n) = a$, which implies that the last cycle is $(n,a)$. Now $\pi(a) = n$ and $\hat{\pi}(n-1) = n$, which implies $a = n-1$. So the last cycle has the form $(n-1, n)$. We see that $\pi = \hat{\pi}$ if and only if after removing the last cycle, the resulting permutation is fixed in $S_{n-2}$.
So $A(n) = A(n-1) + A(n-2)$. Thus $A(n)$ adheres to the same recursion formula as the Fibonacci numbers F(n). Because of $A(1) = 1$, $A(2) = 2$ and $F(2) = 1$, $F(3) = 2$, we get $A(n) = F(n+1)$.