In October 2010, I published a [Monthly problem](http://alum.mit.edu/www/tchow/monthlyprob11523.png) that introduced the concept of a *fair permutation*, which is a permutation $\pi$ such that for every $i$, either $\pi(i) > i$ and $\pi^{-1}(i) > i$, or $\pi(i) \le i$ and $\pi^{-1}(i) \le i$. Equivalently, every cycle of $\pi$ is either a fixed point or an alternating cycle of even length, meaning that if $z$ is the largest element of the cycle, then
$$z > \pi(z) < \pi(\pi(z)) > \pi(\pi(\pi(z))) < \cdots < z.$$


I don't think anyone has studied fair permutations explicitly before.
However, 
a permutation $\sigma$ on $\lbrace1, 2, \ldots, 2m\rbrace$ is said to be a *Salié permutation* if for some $r\le m$, $$\sigma(1) < \sigma(2) > \sigma(3) < \cdots < \sigma(2r)$$ and
$$\sigma(2r) < \sigma(2r+1) < \sigma(2r+2) < \cdots < \sigma(2m).$$
These *have* been studied before, and one can show by generatingfunctionology that the number of fair permutations is twice the number of Salié permutations. This is very suggestive and hints at a close connection.



> 
> **Question**: Can one construct an explicit 2-to-1 map from fair permutations to Salié permutations?
> 
> 
> 



Salié permutations and fair permutations
Write a fair permutation in cycle form, as follows. First write all
cycles of length $>1$ in decreasing order of their smallest element,
with the smallest element of each cycle written as the leftmost
element of the cycle. Then append all the fixed points in increasing
order. An example is
 $$ (3,9,4,6)(1,7,2,10)(5)(8). $$
Now erase the parentheses. We obtain a Salié permutation. Each Salié
permutation arises in exactly two ways. If the first fixed point is
less than the element preceding it in the representation just
described (as is the case for the example above), then we can absorb
the first two fixed points into the cycle preceding them (that is, the
rightmost cycle). Otherwise, we can turn the last two elements of the
rightmost cycle into fixed points. For the example above we get the
additional fair permutation
 $$ (3,9,4,6)(1,7,2,10,5,8) $$
yielding the same Sailé permutation.


**Addendum.** There is a small inaccuracy above. If 1 is a fixed point, 
then rather than absorbing 1 and the fixed point $j$ following it into 
the previous cycle, we should create a new cycle $(1,j)$.


