1. Motzkin数的概念
Motzkin数是指由0, 1和2组成的长度为n的序列中，不互相交叉的不同路径数。即在一条路径上，任何后面的点都不能穿过之前的点。
设M(n)为n阶Motzkin数，则有以下三种情况：
最高点为0，则有M(n-1)条路径。
最高点为1，则有n-1个位置可以放置这个点，每个位置的长度为n-2的序列有M(n-2)种可能，故此情况下有(n-1)M(n-2)条路径。
最高点为2，则有n-1个位置可以放置这个点，每个位置的长度为n-2的序列有M(n-1)种可能，故此情况下有(n-1)M(n-1)条路径。
因此，M(n)可以用以下递推公式计算：
int Motzkin(int n) {
if (n <= 1) {
return 1;
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += Motzkin(i) * Motzkin(n - i - 1);
}
for (int i = 0; i < n - 2; i++) {
ans += (n - 1) * Motzkin(i) * Motzkin(n - i - 2);
}
return ans;
}
2. Motzkin数的计算方法
2.1 暴力枚举
暴力枚举是一种最简单的计算Motzkin数的方法，但它的时间复杂度高达O(3^n)。
int count(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
if (n == 2) return 2;
int sum = count(n - 1) + count(n - 2);
for (int i = 2; i < n; i++) {
sum += count(i - 1) * count(n - i);
}
return sum;
}
2.2 递推
递推是一种时间复杂度为O(n^2)的计算Motzkin数的方法。它的思想是通过M(n-1)、M(n-2)、...、M(0)计算出M(n)。
vector Motzkin(101);
void Init() {
Motzkin[0] = Motzkin[1] = 1;
Motzkin[2] = 2;
for (int i = 3; i <= 100; i++) {
Motzkin[i] = Motzkin[i - 1] + Motzkin[i - 2];
for (int j = 0; j < i - 2; j++) {
Motzkin[i] += Motzkin[j] * Motzkin[i - j - 3] * (j + 2);
}
}
}
3. Motzkin数的应用
3.1 求连通无向图生成树个数
对于一张n个点的连通无向图，它的生成树个数可以表示为下面的式子：
int CountGraphTree(int n) { return Motzkin(n); }证明可以参考这篇文章。
3.2 求Dyck路径数量
Dyck路径是一种特殊的$n * n$方格图，由2×1的砖块构成，满足以下两个条件：
不会穿过x轴，即任意时刻在路径上x轴上方的格子数量都大于等于x轴下方的格子数量；
在任意时刻x轴上方的格子数量不大于1。
对于一个n×n的Dyck路径图，它的Dyck路径数量可以表示为：
int CountDyck(int n) { return Motzkin(n) - Motzkin(n - 1); }证明可以参考这篇文章。
4. 总结
Motzkin数的计算涉及到组合数学、递推等多方面知识，因此多次被用作算法竞赛中的一道经典题目。另外，Motzkin数的应用也是非常广泛的，如图论、组合数学等领域中。