$\omega \in S_n$ is an FPFI (fixed point free involution) (also called a matching) if $\omega^2=1$ and $\omega(i) \neq i$ for all $i$.

For $\omega \in S_n$, a descent occurs at $i$ if $\omega(i+1) < \omega(i)$. For example, $(1 \, 3)(2 \, 4) \in S_4$, when written as $3412$, has one descent at $i=2$.

I'm curious as to what kind of mathematical objects there are that FPFIs be bijected onto that preserves the descent set, if any? Or in general, if there are objects that permutations can be bijected onto that preserve the information about descents.

  • 2
    The map that sends a permutation to its descent set itself is a very useful thing. It is the map $S_n \to Q_n$ in Loday/Ronco "Hopf Algebra of the Planar Binary Trees" ( sciencedirect.com/science/article/pii/S0001870898917595 ), and factors through $Y_n$ as shown on page 1 of that paper. – darij grinberg Oct 2 '14 at 2:10
  • 3
    The Robinson-Schensted correspondence restricted to FPFI is a bijection onto standard Young tableaux with every column of even length that preserves descents (i is a descent of a standard Young tableau if i+1 is to the left of i). – Ira Gessel Oct 2 '14 at 2:32
  • 2
    There is no need to restrict to fixed-point-free involutions, is there? – Martin Rubey Oct 2 '14 at 4:49
up vote 7 down vote accepted

In general, to find maps transporting statistics in a well-behaved way, it is useful to try FindStat. In the case at hand, go to

http://www.findstat.org/StatisticsDatabase/St000021/

(which is the statistic "number of descents of a permutation") and click on "Search for values". After a short while, you will be presented with a list of candidates, each of the following type:

  1. a statistic $stat$ on (possibly different) combinatorial objects, and
  2. a map $\phi$ such that $$ des(\pi) = stat(\phi(\pi)) $$ (possibly $\phi$ is in fact a composition of several maps)

You then only have to check which of candidates have maps that are bijective. Furthermore, you will have to check that not only the number of descents but also the descent set itself is preserved.

In the case at hand, Ira's example of standard Young tableaux is found, there is possibly a well behaved bijection to increasing trees, to ordered trees,...

As Christian points out in the comment below, it is also possible to provide values only for a subset of permutations, in your case for fixed point free involutions.

Yet another possibility is to use a collection of objects built into FindStat that fits your problem better, namely http://www.findstat.org/StatisticFinder/PerfectMatchings.

The drawback of the latter two approaches is that you have to enter the values manually (or generate them with a computer program as below and use the "free" box).

for n in range(1,4):
    for pi in PerfectMatchings(2*n):
        print pi, "=>", pi.to_permutation().number_of_descents()
  • 2
    :-) If you hope for a map that does what you want on matchings while possibly doesn't on other permutations, you can as well only search values on involutions. – Christian Stump Oct 2 '14 at 10:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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