math - 有效括号加泰罗尼亚语数说明

Question

在研究catalan numbers时，我遇到的一些应用是：

1. 没有使用 n 个节点的可能的二叉搜索树。
2. 没有任何方法可以在圆上使用 2*n 点绘制不相交的和弦。
3. 没有办法排列 n 对括号。

虽然我了解前两个问题，加泰罗尼亚数字如何适合他们的解决方案，但我无法理解它们如何适合第三个问题。

在互联网上找不到任何其他有用的资源来解释HOW部分。每个人都只是说这是解决方案。

有人可以解释一下。

Answer 1

由于其他人似乎不同意我认为这个问题是题外话，所以我现在决定它是题外话并提供和回答。

维基百科确实对“排列 n 对括号的方法的数量”（此链接中的第二个要点）感到困惑。部分混淆是括号字符串的顺序与二叉树的顺序不匹配，您确实了解，或者与许多其他示例一起使用。

这是一种将正确匹配的括号对字符串转换为具有内部节点n的二叉树的方法。n考虑最左边的括号，这将是一个左括号，以及与之匹配的右括号。将字符串变成二叉树的一个节点。当前考虑的括号内的子字符串成为该节点的左孩子，当前考虑的右括号之后（右侧）的子字符串成为右孩子。一个或两个子字符串可能为空，并且当前考虑的括号被简单地删除。如果任一子字符串不为空，则递归地继续此过程，直到删除所有括号。

这里有两个例子。让我们从字符串开始((()))。我们从

考虑的括号是最外面的括号。这变成

（我没有费心绘制外部叶节点）然后

然后

这是维基百科最左边的二叉树，有 3 个内部节点。

现在让我们做另一个字符串，(())(). 我们从

同样，考虑的括号是最外面的括号。这转变为

现在考虑的括号是前两个，而不是最外面的。这变成

最终变成

这是维基百科列表中的第二棵二叉树。

我希望你现在明白了。这是正确配对的所有五个可能的 3 对括号字符串的列表，然后是 Wikipedia 的二叉树列表。这些列表现在相互对应。

    ((()))       (()())        (())()       ()(())       ()()()