5
$\begingroup$

It is well-known that the number of non-nesting perfect matchings on $2n$ points is given by the Catalan number $C_n$; see part (a) of the figure below. This is item e^5 in Stanley's list (http://www-math.mit.edu/~rstan/ec/catadd.pdf).

[The following section has been edited to account for an initial mistake in the description.] Now I am interested in non-nesting arc diagrams on $n+1$ points, where no arc connects two neighboring points (two arcs may meet in the same point, one arc from above and one arc from below, so the arcs may not form a matching); see part (b) of the figure below. These diagrams are also counted by $C_n$, and it is easy to prove this.

This must be a known fact, but the second type of arc diagrams is not in Stanley's book (maybe I overlooked it), so who has references for this type of arc diagrams with regards to Catalan numbers?

enter image description here

$\endgroup$
  • 2
    $\begingroup$ I only find 12 non-nesting matchings of $\{1,2,3,4,5\}$ without arcs connecting neighbouring points. Did I misunderstand your definition? $\endgroup$ – Martin Rubey Nov 27 '19 at 13:14
  • $\begingroup$ (this would be oeis.org/A089372, Motzkin paths without peaks on level 1) $\endgroup$ – Martin Rubey Nov 27 '19 at 13:42
  • 1
    $\begingroup$ I get the same count as Martin Rubey, my list is $(\ )$, $(13)$, $(14)$, $(15)$, $(24)$, $(25)$, $(35)$, $(13, 24)$, $(13, 25)$, $(14, 25)$, $(14, 35)$, $(24, 35)$. What are the two that I am missing? $\endgroup$ – David E Speyer Nov 27 '19 at 14:20
  • $\begingroup$ Thanks to Martin and David for pointing out a mistake in my description. I really meant arc diagrams and not matchings (description above is now corrected), i.e., it may happen that two arcs meet in the same point. This gives the two missing diagrams for $n=4$, namely $(13,24,35)$ and $(13,35)$, which are the last two diagrams in the picture I added above. $\endgroup$ – Torsten Mütze Nov 27 '19 at 20:34
3
$\begingroup$

These are nonnesting partitions, which are usually defined as anti-chains in the root poset. Namely, the root poset (in $S_n$) is $\{ e_j-e_i : 1 \leq i < j \leq n \}$ with $e_k - e_j \leq e_{\ell} - e_i$ if $i \leq j < k \leq \ell$. Your arc diagrams turn into nonnesting partitions by $(i,j+1) \mapsto e_j-e_i$.

Googling "nonnesting partition" will give you a ton of hits.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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