factory在32位整数的范围外增长得很快。但是退一步说，那个公式（算法）是不正确的。你写：
为此写了一个算法，例如n = 4：[...]总共有3！+2！+2！+3！= 16
但是16不是<$4的正确结果，应该是14。𝑛
以下是所有可能的后序的表格，以及它们是否可以成为BST：
| 后序|有效BST？|
| --|--|
| 1 2 3 4 |是的|
| 1 2 4 3 |是的|
| 1 3 2 4 |是的|
| 1 3 4 2 |没有|
| 1 4 2 3 |没有|
| 1 4 3 2 |没有|
| 2 1 3 4 |是的|
| 2 1 4 3 |是的|
| 2 3 1 4 |是的|
| 2 3 4 1 |是的|
| 2 4 1 3 |没有|
| 2 4 3 1 |是的|
| 3 1 2 4 |没有|
| 3 1 4 2 |是的|
| 3 2 1 4 |是的|
| 3 2 4 1 |是的|
| 3 4 1 2 |没有|
| 3 4 2 1 |是的|
| 4 1 2 3 |没有|
| 4 1 3 2 |是的|
| 4 2 1 3 |没有|
| 4 2 3 1 |没有|
| 4 3 1 2 |没有|
| 4 3 2 1 |是的|
因此，尽管你的算法在< 4时给出了正确的结果，但从4开始，它开始超过预期的结果。𝑛

Catalan数

可以描述BST的后序数实际上对应于一个具有10个节点的二叉树可以具有的 * shape * 的数量。一旦树的 shape 建立，只有一种方法可以用给定的数字标记节点，这样它就可以是BST。因此，这也唯一地对应于后序数。
二叉树的形状数由Catalan数给出。
我们可以使用增量公式来计算其中的前21个，对于x1= 20，结果是6，564，120，420。int没有足够的范围，所以应该使用long。
代码：

#include <iostream>
#include <vector>

std::vector<long> getCatalans(const int n) {
    std::vector<long> results = {1};
    long c = 1;
    for (int i = 1; i <= n; ++i) {
        c = 2*(2*i - 1) * c / (i + 1);
        results.push_back(c);
    }
    return results;
}

int main() {
    std::vector<long> catalans = getCatalans(20);
    for (int n = 1; n <= 20; n++) {
        std::cout << n << ". " << catalans[n] << std::endl;
    }
}

字符串
输出量：

1. 1
2. 2
3. 5
4. 14
5. 42
6. 132
7. 429
8. 1430
9. 4862
10. 16796
11. 58786
12. 208012
13. 742900
14. 2674440
15. 9694845
16. 35357670
17. 129644790
18. 477638700
19. 1767263190
20. 6564120420

型

仅供参考，节点编号为1到n（包括1和n）的BST的数量由第n个Catalan数给出：

的数据
来源：https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1214/sections/section8/

#include <iostream>
#include <vector>

unsigned long long CatalanRecursive(unsigned int n) {
  if (n <= 1) return 1;
  unsigned long long res = 0;
  for (unsigned int i = 0; i < n; i++)
    res += CatalanRecursive(i) * CatalanRecursive(n - i - 1);
  return res;
}

unsigned long long CatalanDynamicProgramming(unsigned int n) {
  std::vector<unsigned long long> catalan(n + 1, 0);
  catalan[0] = catalan[1] = 1;
  for (unsigned int i = 2; i <= n; i++)
    for (unsigned int j = 0; j < i; j++)
      catalan[i] += catalan[j] * catalan[i - j - 1];
  return catalan[n];
}

int main() {
  unsigned int n = 3;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  n = 4;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  n = 5;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  return 0;
}

字符串

输出：

CatalanRecursive(3) = 5
CatalanDynamicProgramming(3) = 5
CatalanRecursive(4) = 14
CatalanDynamicProgramming(4) = 14
CatalanRecursive(5) = 42
CatalanDynamicProgramming(5) = 42

型