在C++中，Motzkin数

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数的应用也是非常广泛的，如图论、组合数学等领域中。