# Number of non-crossing sets of intervals

Consider the integers $$[1,n]=\{1,\dots,n\}$$ and call subsets of the type $$[a,b]=\{a,\dots,b\}$$ with $$1\le a < b\le n$$ intervals. We say that two intervals $$[a,b],[c,d]$$ are crossing if either $$a or $$c. Otherwise we say that the intervals are non-crossing. So $$[1,3],[2,4]$$ are crossing, but $$[1,3],[2,3]$$ or $$[1,3],[3,4]$$ are non-crossing.

Let $$A_n$$ denote the collection of pairwise non-crossing sets of intervals. So the first few are \begin{align} A_2&=\Bigl\{\emptyset,\{[1,2]\}\Bigr\}\\ A_3&=\Bigl\{ \emptyset,\{[1,2]\},\{[2,3]\},\{[1,2],[2,3]\},\\ &\qquad\{[1,3]\},\{[1,2],[1,3]\},\{[2,3],[1,3]\},\{[1,2],[1,3],[2,3]\} \Bigr\}\\ A_4 &= \Bigl\{ \emptyset,\{[1,2]\},\{[1,3],[3,4]\},\{[1,2],[2,4],[1,4]\},\dots \Bigr\}. \end{align}

It seems that there is an easy recursion for the number of such sets of non-crossing intervals: $$|A_n| = 2 \Bigl(2|A_{n-1}||A_2|-|A_2|^2|A_{n-2}|\Bigr)=8(|A_{n-1}| - |A_{n-2}|) \tag{*},$$ so that $$(|A_2|,|A_3|,|A_4|,\dots)=(2,8, 48, 320, 2176, 14848, 101376,\dots)$$ which seems to be https://oeis.org/A228568.

Questions:

• Is there some standard name for sets sets of non-crossing intervals in the literature? Is the number of such sets known?
• Is the recursion above correct?

My reasoning for (*) is as follows: Any non-crossing collection of sets on $$[1,n]$$ can be obtained from non-crossing collections on $$[1,n-1]$$ and $$[n-1,n]$$ or $$[1,2]$$ and $$[2,n]$$ by optionally adding the interval $$[1,n]$$. However, this is over-counting the intervals which can be obtained from combining non-crossing collections on $$[1,2],[2,n-1],[n-1,n]$$.

Edit: My reasoning for (*) was flawed and the conclusion was incorrect. The correct number of sets seems to be $$(|A_2|,|A_3|,\dots)=(2, 8, 48, 352, 2880, 25216, 231168, \dots)$$ which is https://oeis.org/A054726.

• This is reminiscent of non-crossing partitions, but not quite. – Per Alexandersson Mar 28 '20 at 20:06
• Have you done computations to verify $|A_8|=101376$? – Gerry Myerson Mar 29 '20 at 11:32
• @GerryMyerson I got the number just from ($\ast$). But today I noticed that ($\ast$) is actually flawed, and in particular the numbers of sets I got was wrong. I updated the post with an updated guess for the number of sets – Julian Mar 29 '20 at 15:06
• The "number of graphs on n nodes on a circle without crossing edges" interpretation is clearly right, FWIW. – Sam Hopkins Mar 29 '20 at 15:08
• @GerryMyerson: Done. – Sam Hopkins Mar 30 '20 at 18:18

As discussed in the comments, the number in question is clearly the same as the number of graphs on $$n$$ vertices drawn on a circle without crossing edges, which is in the OEIS at https://oeis.org/A054726. As discussed in that OEIS entry, the number is $$2^n$$ times a "little Schroeder number": recall that one interpretation of the little Schroeder number is as the number of (not necessarily maximal) dissections of a convex $$n$$-gon; in other words, these count collections of noncrossing diagonals; the only difference between these and graphs without crossing edges is that the graphs may include edges of the form $$\{i,i+1\}$$, and any such subset is also allowed, hence the factor of $$2^n$$. Since the little Schroeder numbers are very well-studied, this is the best formula you could hope for.
• Thanks! Small addition: The little-Schroeder numbers count the number of non-crossing graphs on the circle without next-neighbour edges. Since there are $n$ such next-neighbour edges it follows that the total number of graphs is $2^n$ times the little-Schroeder numbers. For more details on the generating functions the paper <mathscinet.ams.org/mathscinet-getitem?mr=345872> is also a good reference. – Julian Mar 30 '20 at 23:16
• @Julian: ah, yes, I see- if we think of the little Schroeder numbers as counting (not necessarily maximal) dissections of an $n$-gon then this interpretation is indeed clear. – Sam Hopkins Mar 30 '20 at 23:53