5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – darij grinberg
    Commented Oct 2, 2014 at 2:10
  • 4
    $\begingroup$ 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). $\endgroup$
    – Ira Gessel
    Commented Oct 2, 2014 at 2:32
  • 2
    $\begingroup$ There is no need to restrict to fixed-point-free involutions, is there? $\endgroup$
    – Martin Rubey
    Commented Oct 2, 2014 at 4:49

1 Answer 1

Reset to default
7
$\begingroup$

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()
Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ :-) 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. $\endgroup$
    – Christian Stump
    Commented Oct 2, 2014 at 10:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .