Bijection between perfect matchings permutations with even cycles

It is possible to proof that the number of perfect matching on a set of $2n$ elements is $n!!$, and on the other hand, it is also possible to proof that the number of permutations $\varphi$ of a set of $2n$ elements with the property that every cycle of $\varphi$ has even length is $(n!!)^2$. This implies that there exists a bijection between the aforementioned set and the pair of perfect matching. I wonder if someone has a nice interpretation for this bijection; meaning, how can we prove this constructing the bijection directly. Thanks!

First, this is (most of) problem 3.13.15 in Cameron's Combinatorics: Topics, Techniques, Algorithms.

This isn't quite direct, but it is possible to both sets into simple bijection with a somewhat awkward third set: let each element of the set $S$ be an ordered pair whose first element is a two-regular multigraph with vertex set $\{1,\dots,2n\}$, all of whose cycles are of even length, and whose second element is a bitstring of length equal to the number of cycles in the first element.

To map from an element of $S$ to a pair of matchings, use the bits to specify the parities of alternating red/blue coloring of edges in the respective cycles; then the blue edges give the first matching in the pair, and the red edges give the second.

To map from an element of $S$ to a permutation with all cycles of even length, instead use the bits to specify orientations of the respective cycles, and interpret the resulting directed cycles as the cycles of the permutation.

If you want to be more certain that all choices are unique, let's insist that the cycles are in order of increasing minimal element. For the edge colorings, use the bit to decide whether the edge from the minimal element of that cycle to its minimal neighbor is blue (0) or red (1). For the permutation, use the bit to decide whether the minimal element of the cycle gets sent to its minimal neightbor (0) or it maximal neighbor (1).

A simple induction on $n$ will prove the result. For $n=2$, $n! = 2$ perfect matchings. Now suppose, for $n=r \ge 2$, there are $r!$ perfect matchings in a (complete) bipartite graph on $2r$ nodes. Then find the number of perfect matchings in a bipartite graph that you construct on $2(r+1)$ nodes.

Also, by contradiction-- you can find a shorter proof.

PS: I suppose you meant the permutation of a set of $n$ elements, not $2n$.

The Bijection $f: M(G) \rightarrow S_n$:

Let $G = (V\cup W, E)$ be a bipartite graph, where $V = \{v_1, v_{2}, \cdots, v_n\}$, $W = \{w_1, w_{2}, \cdots, w_n\}$, and $E \subseteq V \times W$. Here $M(G)$ is the set of perfect matchings in $G$.

Then $\forall m \in M(G),\, \exists$ $\pi \in S_n$, such that $\forall (v_i, w_j) \in m \Longrightarrow i^\pi = j$.

PS2: The number of cycles can never be larger than $O(n\cdot n!)$.