Specifically, say that we label the nodes of $K_n$ with the positive integers between 1 and $n$ and
arrange them around the outside of a circle. Then $m_n$ counts the number of ways to form a
perfect matching on these $n$ nodes whose edges do not cross each other.
The figure below illustrates that $m_5 = 21$ by showing all 21 different ways to do this for $K_5$.
In general, to compute $m_n$ recursively, set $m_0 = m_1 = 1$ and note that node 1
can either be involved in a matching or not.
If node 1 is not involved in a matching, then there are $m_{n-1}$ ways of forming a noncrossing
matching on the remaining $n - 1$ nodes.
If node 1 is involved in a matching, then say it is matched to node $k$: this leaves $k - 2$ nodes on one side of edge$\{1, k\}$ and $n - k$ nodes on the other side; as with the Catalan numbers, no edge can connect
the two sides, which gives us $m_{k-2} \cdot m_{n-k}$ possible ways of matching the remaining edges.
Adding the results of these two cases while allowing $k$ to vary between $2$ and $n$ in the case
that node 1 is included in a matching edge yields the following recurrence relation for the Motzkin
numbers: $m_n = m_{n-1} + \sum_{k = 2}^{n}{m_{k-2} \cdot m_{n-k}}$.
