Processing math: 100%

Glossary

Motzkin numbers

The n-th Motzkin number mn counts the total number of distinct noncrossing matchings in the complete graph Kn.

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.

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=mn1+nk=2mk2mnk.

Motzkin numbers

Wikipedia