The $n$-th Motzkin number $m_n$ counts the total number of distinct noncrossing matchings in the complete graph $K_n$.

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}}$.