18
$\begingroup$

In October 2010, I published a Monthly problem 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?

$\endgroup$
1
  • $\begingroup$ $\pi$ is a permutation of which set? All I can tell it has a partial order... :-) $\endgroup$
    – David Roberts
    Nov 20, 2012 at 22:39

1 Answer 1

19
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.