Skip to main content
3 of 3
edited body
Qfwfq
  • 23.3k
  • 14
  • 122
  • 225

This answer follows from a bijection of De Mèdicis and Viennot (1994, Adv. Appl. Math.) Let $\mathcal{M}_n$ denote the set of perfect matchings of $[2n]$, i.e. the set of partitions of $[2n] := \{1,2,\ldots,2n\}$ into pairs. Let $M \in \mathcal{M}_n$. For $p = \{a,b\}, q = \{c,d\} \in M$ with $a<b$, $c<d$, and $a<c$, we say that $p$ and $q$ cross if $a < c < b< d$ and we say they nest if $a<c<d<b$. Finally, we say they are aligned if they neither cross nor nest, i.e., $a<b<c<d$. Define:

$\mathrm{ne}(M):= |\{\{p,q\}\subset M\colon \textrm{$p$ and $q$ nest}\}|;$

$\mathrm{cr}(M):= |\{\{p,q\}\subset M\colon \textrm{$p$ and $q$ cross}\}|;$

$\mathrm{al}(M):= |\{\{p,q\}\subset M\colon \textrm{$p$ and $q$ are aligned}\}|.$

Then $\sum_{M \in \mathcal{M}_n}x^{\mathrm{ne}(M)}y^{\mathrm{cr}(M)}=\sum_{M \in \mathcal{M}_n}x^{\mathrm{cr}(M)}y^{\mathrm{ne}(M)}$. However, crossings and alignments (or nestings and alignments) are not equidistributed: $\sum_{M \in \mathcal{M}_n}x^{\mathrm{al}(M)}y^{\mathrm{cr}(M)} \neq \sum_{M \in \mathcal{M}_n}x^{\mathrm{cr}(M)}y^{\mathrm{al}(M)}$.

Here we see a symmetry between crossings and nestings that is at least to some degree nonobvious. In fact, the symmetry between "non-crossing" objects and "non-nesting" objects is an important and somewhat mysterious phenomenon in modern research in algebraic/enumerative combinatorics, especially in the context of "Coxeter-Catalan combinatorics." For an introduction to the basic story, see the classic monograph by Armstrong: https://arxiv.org/abs/math/0611106v2.

Sam Hopkins
  • 24.2k
  • 5
  • 97
  • 171