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

Improve this question
$\endgroup$
4
  • 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
    Commented Nov 27, 2019 at 13:14
  • $\begingroup$ (this would be oeis.org/A089372, Motzkin paths without peaks on level 1) $\endgroup$
    – Martin Rubey
    Commented Nov 27, 2019 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
    Commented Nov 27, 2019 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
    Commented Nov 27, 2019 at 20:34

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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