Define an ascent of a permutation, $w$, to be an index, $1\le i\le n$, such that $w_i<w_{i+1}$. Furthermore, we adopt the convention that $n$ is always an ascent. This convention is not typical, but it makes this particular problem work out.
Let $\mathcal{D}(n)$ and $\mathcal{E}(n)$ be respectively the set of derangements of $n$ elements and the set of permutations of $n$ element whom first ascent is in even position. It's not so hard to see through a recursive reasoning that the cardinalities of this two sets are equal. But Stanley's Combinatorics volume 1 asks also for a combinatorial proof. I tried for hours but I couldn't figure it out so I checked the solution. He proposes the following bijection:
- Let $w$ be a derangements.
- Write it as a product of cycles in the standard way (the standard convention of Stanley is: "the cycles start with their biggest element").
- Arrange the cycles in such a way that the elements of the smallest elements of the cycles are in decreasing order.
- Move the smallest element of each cycle to the second position of its cycle.
- Erase the parenthesis and you have your $w'\in \mathcal{E}(n)$.
Then he states that it's fairly easy to see that this is a bijection. The main question is:
-How do I construct an inverse to effectively see that this is a bijection?
Then there is a secondary question that is partially a "rant". How should you come up with these convoluted ideas? For sure I'm not an expert in combinatorics, but I studied the material covered in this course and I'm really trying hard to do the exercises in this book. This exercise is $[2+]$ that the author defines to be "somewhat difficult", but then the author states that it's published in a paper... Maybe I'm simply mathematically immature but I simply can't understand if I'm studying wrong or it's simply the difficulty levels of this book that are skewed. This course feels so much different from any other course I've taken.
This answer is roughly speaking a long-winded version of Mike's answer above, but I've tried to at least make a stab at saying where the bijection comes from in answer the rant part of the question :)
To fix notation, recall that $S_n$ is the group of bijections of an $n$-element set $[1,n] = \{1,\ldots,n\}$, and any permutation can be written as the composition of disjoint cycles, where a cycle $\mathbf e = (e^1,\ldots,e^l)$ denotes the permutation which maps $e^i$ to $e^{i+1}$ if $i<l$, $e^l$ to $e^1$, and fixes all $k \in [1,n]\backslash \{e^i: 1\leq i \leq l\}$. We write $|\mathbf e|=l = n -|\{k \in [1,n]: \sigma(k)=k\}|$.
Stanley's bijection $b\colon \mathcal D(n) \to \mathcal E(n)$ takes a derrangement $\sigma$, views it as the composition of its disjoint cycles, writes these down according to an ordering convention, and then reads the resulting list $t_1t_2\ldots t_n$ as the permutation $i\mapsto t_i$. This map, given by writing a permutation according to one labelling convention and then reading it off using a differnet convention, may feel bizarre to start with, but in this context it is actually natural enough: it is straight-forward to recursively build a derrangement by specifying its cycles one at a time, while to recursively build a permutation $\tau$ with even first ascent, it is simpler to iteratively build up the list $t_1\ldots t_n$ (where $\tau(i)=t_i$).
The subtlety is thus what order to choose to write the cycles in, and what convention to use to "cut" a cycle into a segment. The latter is in a sense more evident: if we place the smallest element of the cycle in the second slot (and for a derangement there are always at least two slots in each cycle) the this obviously creates an ascent at $2$ unless the first cycle has only two elements. In addition to this, Stanley's map then also places the cycles so that their minimal elements form a decreasing sequence, that is, if $\sigma = \mathbf c^1\ldots \mathbf c^r$ where $\mathbf c^i = (c^i_1,\ldots, c_i^{k_i})$, then $c_i^2 = \min\{c_i^j: 1\leq j\leq k_i\}$ and $c_1^2>c_2^2>\ldots >c_r^2$.
It follows that $b(\sigma)$ has $b(\sigma)(1)>b(\sigma)(2)<b(\sigma)(3)$, so that $2$ is the first ascent, unless we have $k_1=2$ and $b(\sigma)(2)>b(\sigma)(3)$. But since $k_1=2$, $b(\sigma)(3)>b(\sigma)(4)$ since they are the first two terms in a cycle, so the first ascent is at least $4$. Iterating in this way we see that we obtain an even first ascent unless all the cycles have length $2$ and $c_2^i>c_1^{i+1}$, and since our conventions insist that $c_1^i>c_2^i$, we see that the list $t_1\ldots t_n$ is strictly decreasing and hence $$ \sigma=(n, n-1)(n-2, n-3)\ldots (2,1) $$ so that $n=2r$ and $n$ is an ascent by convention. It follows that $b\colon \mathcal D(n) \to \mathcal E(n)$.
To see that it is a bijection, consider first how our ordering convention can be used to recover the cycles from the list obtained by removing the bracketing they give: each cycle $\mathbf c^i$ is a segment of the list with its minimal element $c^i_2$ appearing second, and these minimal elements must decrease. We describe the inverse map $c\colon \mathcal E(n) \to \mathcal D(n)$ by recursively removing an initial segment of the remaining list.
Now suppose that $\tau \in \mathcal E(n)$. We describe $c\colon \mathcal E(n)\to \mathcal D(n)$ recursively, where at stage $k$ we produce the $k$-th cycle of $c(\tau)$. Let $i_1=1$ and consider the list $t_{i_1}\ldots t_n$. Since $\tau$ has even first ascent, $t_1>t_2$, and we let $j_1 = \min\{k>2: t_k<t_2\}$. If $j_1=3$ then let $\mathbf c^1= (t_1t_2)$ and let $i_2 = 3$. If $j_1\geq 4$, then let $\mathbf c^1 = (t_1\ldots t_{j_1-2})$ and $i_2=j_1-1$. In the latter case, the remainder of the list begins with a descent because $t_{j_1-1}>t_2>t_{j_1}$, while in the former, places $1$ and $2$ were not ascents, and the first ascent is even, hence $3$ is a descent. Iterating this process on $t_{i_2}\ldots t_n$ and so on yields $c(\tau) = (\mathbf c^1\ldots\mathbf c^r)$, where each cycle $\mathbf c^i$ has length a least $2$, and $c^i_2$ is its minimal element.