Number of non-crossing and non-partially-overlapping arcs -- Catalan numbers?

Question

Let $n$ be an integer and consider the $n$ points $1,2,\ldots,n$ on a horizontal line. Consider sets of arcs on these points such that

• no two arcs cross each other, i.e. there exist no two arcs $(a,b),(c,d)$ with $a<b<c<d$,
• no two arcs do partially overlap, i.e. there exist no two arcs $(a,b),(a,c)$ with $a<b<c$ or $(b,a),(c,a)$ with $b<c<a$.

However, note that two arcs are allowed to fully overlap, e.g. $(a,b),(c,d)$ with $c<a<b<d$.

The set for all such graphs for $n=2,3,4$ is

Now it seems that the number of such graphs is $$2, 5, 14, 42, 132, 429, 1430,\ldots$$ which are simply Catalan numbers.

I know there are many interpretations of Catalan numbers, but I could not directly find the above one. Is the above set of non-crossing and non-partially-overlapping arcs (a) known under a different name, or (b) in a one-to-one correspondence to a known interpretation of Catalan numbers?

Answer 1

I’ll briefly sketch a bijection between these diagrams on $n$ points and valid strings of $n$ pairs of parentheses. The sketch will be a bit rough, as I’m going to have to shut down shortly and will explain it largely by example.

Start with one of your diagrams. Each point represents a matched pair () of parentheses. If $k<\ell$, and there is an arc from point $k$ to point $\ell$, then all of the pairs corresponding to points $k+1,\ldots,\ell$ are inside pair $k$. If this is a maximal arc, all pairs $j$ with $j<k$ are to the left of pair $k$, and all pairs $j$ with $\ell<j$ are to the right of pair $j$. If it is maximal within a larger arc from $p$ to $q$, all pairs $j$ with $p<j<k$ are to the left of pair $k$ within pair $p$, and all pairs $j$ with $\ell<j<q$ are to the right of pair $j$ within pair $p$.

These rules, applied recursively if necessary, suffice to convert your diagrams to valid parenthesis strings. For $n=4$, for instance, your diagrams, in order from the top down, correspond to the following strings, in which each pair of matched parentheses is labelled with the number of the corresponding point:

$$\begin{align*} &(_1)_1(_2)_2(_3)_3(_4)_4\\ &(_1(_2)_2)_1(_3)_3(_4)_4\\ &(_1(_2)_2(_3)_3)_1(_4)_4\\ &(_1(_2)_2(_3)_3(_4)_4)_1\\ &(_1)_1(_2(_3)_3)_2(_4)_4\\ &(_1)_1(_2(_3)_3(_4)_4)_2\\ &(_1)_1(_2)_2(_3(_4)_4)_3\\ &(_1(_2(_3)_3)_2)_1(_4)_4\\ &(_1(_2(_3)_3(_4)_4)_2)_1\\ &(_1(_2)_2)_1(_3(_4)_4)_3\\ &(_1(_2)_2(_3(_4)_4)_3)_1\\ &(_1(_2(_3)_3)_2(_4)_4)_1\\ &(_1)_1(_2(_3(_4)_4)_3)_2\\ &(_1(_2(_2(_4)_4)_3)_2)_1 \end{align*}$$

With a bit of thought it’s clear that the procedure produces only valid parenthesis strings.

Starting with a valid string of $n$ pairs of parentheses, you simply reverse the process to get a set of arcs on a line of $n$ points. First number the pairs from $1$ to $n$ in the order in which their left parentheses appear. For example the string (()(())) becomes $(_1(_2)_2(_3(_4)_4)_3)_1$. There are parentheses inside pair $1$, so there will be an arc from point $1$. The top level pairs inside pair $1$ are pairs $2$ and $3$, so the arc from point $1$ will be to point $3$, corresponding to the rightmost of these pairs. Pair $4$ is inside pair $3$, so there will be an arc from point $3$ to point $4$. The resulting graph is the fourth one up from the bottom in your list.

Again, a bit of thought shows that no crossing arcs are created by this process.