有效括号序列的数量——卡特兰数解释

Question

在研究卡特兰数时，我发现其中的一些应用：

1. 使用n个节点进行二叉搜索树的可能数量。
2. 在圆上使用2n个点绘制不相交弦的方法数量。
3. 安排n对括号的方式数量。

虽然我理解前两个问题，卡特兰数如何适用于它们的解决方案，但我无法理解它们如何适用于第三个问题。

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

可以有人解释一下吗？

- Yash

---

在实际的计算机编程中，这是一个什么问题？虽然Catalan数在一些编程问题中被使用（包括至少一个我在这个网站上回答过的问题，该问题使用了括号），但看起来这个问题更适合数学堆栈交换网站。 - Rory Daulton

有趣的枚举二叉树 - 这是使用Motzkin数完成的，但Catalan也与之相关。 - Guy Coder

感兴趣的内容：OEIS [Catalan]（https://oeis.org/search?q=catalan&sort=&language=&go=Search） - Guy Coder

Answer 1

由于其他人似乎不同意我认为这个问题是离题的，所以我现在决定它是有关的，并提供一个答案。

维基百科确实让人困惑关于“排列n对括号的方式数量”（this link中的第二个要点）。部分混淆是括号字符串的顺序与二叉树的顺序不匹配，你理解了这一点，或者与许多其他例子不同。

这里有一种方法可以将一个由正确匹配的括号对组成的长度为n的字符串，转换为一个具有n个内部节点的二叉树。考虑最左边的括号，它将是一个左括号，与其匹配的右括号一起。将该字符串转换为二叉树的一个节点。当前考虑的括号内的子串成为该节点的左子节点，当前考虑的右括号之后(向右)的子串成为右子节点。任何一个或两个子串都可能为空，并且当前考虑的括号会被简单地删除。如果任何一个子串不为空，则继续递归执行此过程，直到所有括号都被删除。

以下是两个示例。让我们从字符串((()))开始。我们从

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

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

那么

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

现在让我们来看另一个字符串，(())()。我们从以下内容开始：

再次强调，被考虑的括号是最外层的括号。这将被转换为

现在被考虑的括号是前两个，而不是最外层的那个。这就变成了

最终成为

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

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

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

- Rory Daulton

---

既然其他人似乎不同意我认为这个问题是不相关的，但我理解。 - Guy Coder

你可以尝试使用简单的DFS（从根到叶子，从左到右）。 左边缘是“（”，右边缘是“）”，除了已访问的边缘以外都会被忽略。 - NoraBora

@RoryDaulton 感谢您提供这个清晰易懂的答案，并配有图片支持。 :) - Abhishek Ghosh