Motzkin numbers

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.

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

Motzkin numbers