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.