**默慈金数 (Motzkin Number)**是特殊计数序列中的一种。在中文互联网上比较难查到有关默慈金数的资料，能获得的信息基本局限于默慈金数的定义和（一种）应用，并且这两者之间没有什么比较明显的联系。事实上，作为一种特殊计数序列，想研究默慈金数就逃不开大名鼎鼎的卡特兰数。下面就让我们通过引入卡特兰数，逐步认识默慈金数，以及阐释51Nod 1556利用默慈金数的思路。
什么是默慈金数
网上能查到的有关默慈金数的资料一般局限于两点：默慈金数的定义和默慈金数在格路径（也就是网格中的路径）中的应用。
默慈金数是这样定义的：在数学中，一个给定的数n的默慈金数（下文记作Mn)是在一个圆上的n个点间，画出彼此不相交的弦的全部方法的总数。
比如n = 4时，M4 = 9：
且n = 5时，M5 = 21：
但显然这种定义很难直接利用（毕竟让你在圆上画弦的机会不多）。相应地，我们可以见到默慈金数的这种应用：在一个网格上，若限定每步只能向右移动一格（可以向右上、右下和水平向右），并禁止移动到y=0以下的地方”，则以这种走法用n步从（0,0）移动至（n,0）的可能形成的路径的总数为n的默慈金数。
比如从(0, 0)运动到(4, 0)，同样有9种方式：
但是很明显，默慈金数的定义和这种应用形式之间的关系十分不显然。但是好在默慈金数有这样一个计算公式： $$ M_{n} = \sum_{k=0}^{\left \lfloor n/2 \right \rfloor}C^{2k}{n}Catalan(k) $$ 其中Catalan(k)是第k个卡特兰数（下文记作C{k}）。这个公式将默慈金数与卡特兰数联系起来，这就为我们提供了理解默慈金数的方向。
什么是卡特兰数
如果我们要写一个计算中缀表达式的程序，很显然我们会遇到括号的处理。正常情况下，表达式中的括号应该是成对出现的，像这样： $$ ((a+b)((c+d)*e)) $$ 但是有时我们可能会遇到这样不合法的表达式：出现了不成对的左括号或右括号，比如： $$ (a+b)(a+b $$ 或者是 $$ (a+b)*c)(a+b) $$ 我们忽略括号中具体表达式的值，将第一种情况中正确使用的括号序列称作好括号列，而将下面两种情况中错误使用的括号序列称作坏括号列。显然一个括号列是好是坏一读便知。
易证，一个括号序列是好括号列的充分必要条件为：
- 该括号序列由偶数个括号组成，其中半数是 ‘(’，半数是 ‘)’。
- 从左向右阅读括号序列时，读出的右括号 ‘)’ 的数目不会比左括号 ‘(’ 的数目多。（因为括号是成对出现的）
我们考虑这样一个问题：由2n个括号（半数为左括号，半数为右括号）可以组成多少个好括号列？
为了计算这个值，我们先考虑一个坏括号列：设 $$ p_{1}p_{2}p_{3} \cdots p_{2n-1}p_{2n} $$ 是一个由n个左括号和n个右括号组成的坏括号列。则根据好括号列充要条件中的第二条，这个坏括号列中必然存在一个前缀，其中的右括号 ‘)’ 数目比左括号 ‘(’ 多。
那么，我们设 $$ p_{1}p_{2}p_{3} \cdots p_{j-1}p_{j} $$ 是该括号列中最短的一个“坏”前缀。显然这个“坏”前缀中右括号’)‘只比左括号’(‘多一个（否则就一定能通过缩小长度把第二个右括号删掉）。之后，如果我们把p_{j}之后的部分翻转过来（把原本的左括号 ‘(’ 换成右括号 ‘)’ ，右括号亦然），这个坏括号列就变成了一个由(n - 1)个左括号和(n + 1)个右括号组成的括号序列，也就是说，**n个左括号和n个右括号组成的坏括号列同由(n - 1)个左括号和(n + 1)个右括号组成的括号序列是一一对应的。**那么，我们就可以得到由n个左括号和n个右括号组成的好括号列的个数为 $$ C_{2n}^{n}-C_{2n}^{n+1} $$ 采用二项式系数的记法，也即 $$ \begin{pmatrix} 2n\n
\end{pmatrix}- \begin{pmatrix} 2n\n+1
\end{pmatrix} $$ 简化后得 $$ \frac{1}{n+1}\begin{pmatrix} 2n\n
\end{pmatrix} $$ 我们把这个表达式称作卡特兰数。
但是现在卡特兰数和默慈金数仍然看起来没有一点关系！别急，如果我们把左括号记成“向右移动”，将右括号记作”向上移动“，则一个好括号列可以转化为一条**在n × n格点中不越过对角线的单调路径 **:
这样卡特兰数就变成所有在n × n格点中不越过对角线的单调路径的个数 。（这样就给出了 51Nod 1120 机器人走方格 V3 这道题的解法。）如果把这张图旋转45°，把”向右移动“变成”向右上移动“，把”向上移动“变成”向右下移动“，这样获得的“卡特兰路径”是不是跟上面默慈金数格路径的图很相似了？
下面是重头戏：默慈金数是用圆上绘制不相交弦的个数定义的，那么卡特兰数有没有相似的展现方式呢？我们考虑这样一个问题：在圆上均匀地取2n个点，用n条彼此不相交的弦**（但允许在端点处相交）**将这些点两两连接成n对，求全部方法的总数。
如果我们将这2n个点按照顺时针顺序排成一行，当且仅当这个序列中两点是一条弦的两个端点，就把它们用括号括起来。这样，**每种弦的连接方式都会生成一个好括号列。**同时，对于任给的好括号列，也都可以画出对应的弦的连接方式。这就证明了弦图与好括号列之间构成双射关系，因此，这个问题的答案也是卡特兰数。
下面我们给出C5（第5个卡特兰数）对应的42种连接方式，以及10种错误的连接方式。相应地，我们上文中提到过，M5=21，这揭示了总有
$$
M_{n} \leq C_{n}
$$
同时这个问题的等价说法是：卡特兰数代表集合{1, 2, …, n}的不交叉划分的个数。意义很明显。
对默慈金数的分析
通过上文我们对卡特兰数相似的分析，现在我们可以肯定默慈金数的格路径应用和默慈金数的定义是有关系的了。现在我们要先通过我们已经获得的卡特兰数的计算公式，来构造默慈金数的计算公式。
我们发现：默慈金数的定义不允许弦在端点处相交，而卡特兰数的性质允许。为了防止这种局面，我们必须将整个圆大致分成两部分，每一次各从每部分中取相同数目的点，之后再将这两部分中的点连接成弦。而我们已经取出的点因为是分处于两个部分中，可以保证不会有弦在端点处相交，**所以这时我们可以用卡特兰数来计算取出的点构成的“子集圆“中弦不相交连接的数目！**又，因为允许有不连接弦的点存在，所以我们要逐个取出0, 2, 4, … , n/2个点来分别计算。因此我们可以得到公式 $$ M_{n} = \sum_{k=0}^{\left \lfloor n/2 \right \rfloor}\begin{pmatrix} n\2k
\end{pmatrix} C_{k} $$ 这也正与上文我们提到的公式相符。
上文分析卡特兰数时我们提到了好括号列。如果用左括号 ‘(‘表示 ”向右上前进“， 用右括号 ‘)‘表示”向右下前进“，我们就能获得一条上面提到的”卡特兰路径“。现在的问题是，用这两个字符描述一条”默慈金路径“显然不够，因为”默慈金路径“中有水平向右移动的部分。因此，我们还需要一个字符 ‘=’ 来表示”水平向右移动。这样，对于图3中的第4张图，我们就可以写出一个对应的默慈金括号列： $$ ()== $$ 现在的问题是把默慈金括号列和默慈金数的定义联系起来。我们再次在圆上均匀地取n个点，并将它们按照顺时针排成一行。如果有两个点连接成一条弦，我们就把左侧的端点用左括号 ‘(‘代替，将右侧的端点用右括号 ‘)‘代替，将没有弦连接的端点用 ‘=’ 代替。这样，我们就把一个圆上的定点序列替换成了一个默慈金括号列。我们将上面提到的默慈金括号列还原成圆上的弦图，它正是图一中的第2张图。
这样，51Nod 1556的思路就很明显了：要求相邻数的差不能超过1，也就是说第n个数和第n-1个数之间的差可以是1, 0, -1，如果这三个数分别代表向右上移动、水平移动、向右下移动，那么这道题几乎就是描述了一个裸的默慈金数的计算。
51Nod 1556的具体思路
但是这道题的要求又与默慈金数不一样：默慈金数计算从 (0, 0) 开始，到 (n, 0) 处结束的路径总数，而这道题要求计算从 (0, 0) 开始，到 (n, x) 处 (x >= 0) 结束的路径总数。
此时，我们可以换一种思路来考虑：默慈金数是从(0, 0)运动到(n, 0)的总数，但是在(n, 0)处就不能再向右下走了，因为再向右下走就越过了y >= 0的限制，之后的路径都是非法的。也就是说，如果我们令x = n + 1（错误的位置），至少在x = n - 1处我们就不能选择向右下走。又因为我们在每一个点可以向三个方向走，所以我们最后可以给出公式 $$ ans[x] = 3 * ans[x - 1] - M[x-2] $$ 而默慈金数的计算可以参照 $$ M_{n+1} = \frac{(2n+3)M_{n}+3nM_{n-1}}{n+3} $$ 推导过程详见Motzkin Number，在此不再多谈。