问题标签 [catalan]

例如，对于 elements a,b,c,d，有 5 种可能的方式来获取相邻元素并将它们缩减为单个元素，其中必须一次组合两个元素（以下用括号表示）：

第一个示例相乘a*b，然后将该乘积乘以 ，然后将该乘积c乘以d。第二个示例首先乘以b*c，然后乘以乘积a，然后乘以乘积d。

任何 2n 个元素的有效括号表达式都必须具有 n(和 n)的属性，从左到右阅读，总是至少(有).

我知道对于 n 个数字，方式的数量是 (n-1)th Catalan number。但是如何准确地生成所有结果分组？

谢谢

（顺便说一句：这个问题有超过 160 种等效公式，所有公式都基于加泰罗尼亚数字枚举的不同组合对象。有关这些的最新列表，请参阅Richard Stanley 的加泰罗尼亚附录。）

任何人都可以解释算法以在仅使用单个堆栈时生成可能的排列，并且推送和弹出是唯一允许的操作。搜索了很多，但没有明确的答案。这种排列的总数也由加泰罗尼亚数字给出。但我没有得到证明。如果可能的话，请解释一下。

谢谢！！

考虑笛卡尔坐标系中的一个点 P(n,n)。机器人必须从原点开始并到达这一点。机器人可以采取的唯一步骤是：

• 1个单位权利
• 1个单位。

机器人到 P 点可以走多少条不同的路径？

是否有到达 P 点的最优路径？（向上和向右的步骤都会产生相同的成本）。

让是具有节点bi的二叉树的数量。i计算b10。

这是我遇到的一个问题。

到目前为止，我已经能够提出这些：

随着我变大，它很快变得有点太多了。

谁能想到比仅仅画出树并计算它们更好的方法来计算 Bi？

我正在开发一个通用解析算法，我正在使用下一条规则对其进行测试

好吧，该算法向我展示了为由n a's 组成的字符串生成的所有树。

例如，下表显示了算法使用的时间，因为a's的数量

我不知道O我的算法是什么（大 O 表示法）。我如何测量它，因为时间当然取决于三件事：

1. 要解析的字符串的长度
2. 语法复杂度
3. 算法的性能

我想使用动态编程技术编写一个算法，该算法执行以下操作：查找沿具有 n × n 方形单元格的网格边缘的单调路径数，这些单元格不超过对角线。单调路径是从左下角开始，在右上角结束，并且完全由指向右侧或向上的边组成的路径。

我有一些想法，但无法弄清楚如何正确地做到这一点。

我尝试在 Excel 中使用 N 值进行以下操作：

http://upload.wikimedia.org/math/b/a/d/bad5db400fcfd7092e2008e376993a27.png

我可以使用 =COMBIN(2*N;N)/(N+1) 制作 Ci，但是考虑到我的 n >= 0，如何制作 ni-1 ？

谢谢

给定二叉树节点数 (X) 写入方法，该方法返回具有 X 节点的二叉树的随机排列数。

例子：

X=1：1

X=2：2

X=3：5

我最终得到：

我很感激在这里分享更好的解决方案。

考虑我有一个数组[3,18,15,25,26]，可以从中形成多少个可能的二叉搜索树？

问题是要找到第n 个加泰罗尼亚数 mod m，其中m不是素数，m = (10^14 + 7)。以下是我尝试过的方法列表：（max N = 10,000）

1. 查表的动态编程，太慢了
2. 使用加泰罗尼亚公式ncr(2*n, n)/(n + 1)，由于函数的原因，它又不够快，不能使用指数平方ncr加速，因为它不是素数。m
3. 对预先生成的表进行硬编码Catalans，但由于文件大小限制而失败。
4. 递归关系C(i,k) = C(i-1,k-1) + C(i-1,k)，这太慢了

所以我想知道有没有其他更快的算法来找到我不知道的第 n 个加泰罗尼亚数字？

使用动态规划

使用原始公式

使用递归关系