What is the number of noncrossing acyclic digraphs? A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross each other.
I am interested in the integer sequence for the number of noncrossing acyclic digraphs on $n$ vertices. I computed the first few terms of this sequence using a brute-force method. Starting with $n = 1$, they are:
1, 3, 25, 335, 5521
I was not able to find this sequence in the OEIS, which does contain integer sequences for many other classes of noncrossing graphs.
Does anybody know the sequence, or has an idea for how to derive it? Thanks for your time!
 A: You can split noncrossing graphs and get equations for the generating functions. I like to take the minimal root edge (if it exists).
$$N=1+xN+2xN\bar N$$
This says that an acyclic noncrossing graph is either empty ($1$), or has an isolated root ($xN$), or has a minimal root edge ($2$ counts either direction) with a noncrossing graph on one side and an edge-rooted noncrossing graph on the other side (counted by $\bar N$). But now we have to deal with $\bar N$.
$$\bar N = \frac{1+xN}{(1-2x\bar N)^2}+\frac{4x\bar N^2}{1-2x\bar N}-\frac{x\bar N^2}{1-x\bar N}$$
It's easier to explain this one with a picture.

Note that $x$ is not counting the root(s), so if you need to weight the root you'd get $x\bar N$. If you need to include the (truly) empty case too you'd need $1+xN$, as in both equations above. You could easily modify these equations to count by components with $z$ by replacing $1+xN$ with $1+xzN$ in both equations.
Then we can compute:
$$N(x)=1 + 3x + 25x^2 + 335x^3 + 5521x^4 + 101551x^5 + 1998753x^6 + 41188543x^7 + 877423873x^8 + 19166868607x^9 + \dots$$
$$\bar N(x)=1 + 8x + 106x^2 + 1740x^3 + 31944x^4 + 628040x^5 + 12932888x^6 + 275367248x^7 + 6013043424x^8 + 133923593728x^9 + \dots$$
This method works in general for counting types of noncrossing graphs weighted by different things but the equations can get monstrous.
A: It is well known that evaluation of the chromatic polynomial of a graph gives (up to sign depending only on the number of vertices) the number of its acyclic digraph. Therefore it is enough to solve the stronger problem: How many pairs (noncrossing graph on $n$ points,good $k$-coloration of it) are there?
Let $f(n,k)$ be that number. Let also $g_1(n,k)$ be that but with restriction that point 1 must be with color 1; $g_2(n,k)$ with restriction that point 1 must have color 1 and point 2 must have color 2, but they are not connected to each other; $g_3(n,k)$ with the restriction that both points 1,2 must have the color 1. (We define $g_1$ only for $n \geq 1$ and $g_2,g_3$ only for $n \geq 2$)
Now the following can be proven:


*

*$f(n,k)=k g_1(n,k)$

*$g_1(n,k)=g_3(n,k)+2(k-1) g_2(n,k)$

*$g_2(n,k)=g_1(n-1,k)+\sum_{m=2}^{n-1} g_2(n-m+1,k)\left(g_3(m,k)+2(k-2)g_2(m,k)\right)$

*$g_3(n,k)=g_1(n-1,k)+\sum_{m=2}^{n-1} 2g_2(n-m+1,k)g_2(m,k) (k-1)$


The first two are trivial, and the last two follows from considering the first point that connects to point 1, and dividing the graph to two smaller graphs.
From those relations it is possible to obtain algebraic relations between the ordinary generating functions (over variable $n$). It follows from the calculation that $\sum_{n=0}^{\infty} f(n,k) x^n$ is an algebraic function, a solution of degree 3 polynomial that can be calculated explicitly.
