We will find the formula for Motzkin numbers and show that they enumerate chord diagrams. Let $\mathcal{M}$ be the following class of combinatorial configurations. A configuration of weight $n$ is a circle with $n$ points, with some collection of chords between the vertices under the condition that no two chords are crossing. Let $M_n$ be the number of configuration of weight $n$. These are called the Motzkin numbers. Let $M(x)=\sum_{n \geq 0} M_n x^n$ be the generating function of the Motzkin numbers.
(a) Show that the Motzkin numbers satisfy the following recurrence relation: $$ M_n=M_{n-1}+\sum_{i=0}^{n-2} M_i M_{n-2-i} $$
(b) Using part (a), show that the generating function of the Motzkin numbers satisfies the the following quadratic equation: $$ x^2 M(x)^2+(x-1) M(x)+1=0 . $$
We have only had 3 lessons in combinatorial enumeration, so my knowledge is still quite limited, but here is what I have accomplished so far, I would like to know if a and b are correct
(a) Imagine a circle with $n > 0$ points where we aim to form chord diagrams. For $M_n$, the $n$-th Motzkin number, there are two possibilities for the first point:
- It is not connected by a chord. The remaining $n-1$ points form a new diagram with weight $n-1$, contributing to $M_{n-1}$ possible configurations.
- It is connected to another point via a chord. Suppose this point is $ i+1 $ (with $0 \leq i \leq n-2 $. This divides the diagram into two parts: one part inside the chord with $ i $ points and another part outside the chord with $ n-2-i $ points. The possible configurations for these two parts are $ M_i $ and $ M_{n-2-i} $ respectively, and the total contribution of these configurations is the sum over all possible $ i$'s, $\sum_{i=0}^{n-2} M_i M_{n-2-i} $.
By adding these two cases, we obtain the recurrence relation: $ M_n = M_{n-1} + \sum_{i=0}^{n-2} M_i M_{n-2-i} $
(b) We will consider the coefficients of $x^n$ on both sides of the equation $x^2 M(x)^2 + (x-1) M(x) + 1 = 0$. First, let's rewrite it as $$ M(x) = xM(x)^2 + xM(x) + 1 $$ The coefficient of $x^0$ on both sides is 1. We assume $n>0$. By the definition of the generating function, we have $\left[x^n\right] M(x) = M_n$. The coefficient of $x^n$ in $1 + x^2M(x)^2$ is the coefficient of $x^{n-2}$ in $M(x)^2$, which is $$ \sum_{i=0}^{n-2} M_i M_{n-2-i} $$ and the coefficient of $x^n$ in $xM(x)$ is the coefficient of $x^{n-1}$ in $M(x)$, which is $$ M_{n-1} $$ Together, this gives $$ M_n = M_{n-1} + \sum_{i=0}^{n-2} M_i M_{n-2-i} $$ which equals $M_n$ according to part (a). By combining these terms into the generating function $M(x)$, we get: $$M(x) = 1 + xM(x) + x^2 M(x)^2 $$ Rearranging gives us the desired quadratic equation: $$ x^2 M(x)^2 + (x-1) M(x) + 1 = 0 $$