Specifically, say that we label the nodes of Kn with the positive integers between 1 and n and
arrange them around the outside of a circle. Then mn 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 m5=21 by showing all 21 different ways to do this for K5.
In general, to compute mn recursively, set m0=m1=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 mn−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 mk−2⋅mn−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: mn=mn−1+∑nk=2mk−2⋅mn−k.