如何计算括号顺序的所有可能组合？求组合数计算公式

你要找的这个计算合法括号最大组合数的公式，其实就是咱们常说的卡特兰数（Catalan Number）——这可是组合数学里解决这类括号合法序列问题的经典工具，完美匹配你列出的所有规则：括号合法、n为偶数、不同顺序视为不同组合。

核心公式 #

首先明确：我们设总括号数为n（必须是偶数，即n=2k，k代表括号的对数，k≥1），那么合法的括号组合数就是第k个卡特兰数，公式如下：

C_k = (1/(k+1)) × C(2k, k)

这里的C(2k, k)是组合数，表示从2k个位置中挑选k个位置放置左括号的总可能数；除以k+1是为了排除所有非法的括号序列（也就是那些在遍历过程中右括号数量超过左括号的情况）。

验证你的例子 #

咱们用你给出的例子来验证一下：

• 当n=2（k=1）：C_1 = (1/2) × C(2,1) = (1/2)×2 = 1，对应唯一的合法序列()，正确。
• 当n=4（k=2）：C_2 = (1/3) × C(4,2) = (1/3)×6 = 2，对应()()和(())两种，和你说的一致。
• 当n=6（k=3）：C_3 = (1/4) × C(6,3) = (1/4)×20 = 5，对应的合法序列分别是：((()))、(()())、(())()、()(())、()()()，正好5种，完全匹配。

为什么符合你的规则？ #

1. 合法性保证：卡特兰数的推导逻辑就是先算出所有可能的括号排列（C(2k,k)），再减去那些非法的序列——比如出现)()这种右括号先于左括号的情况，最终得到的结果全是合法的括号序列。
2. n为偶数要求：因为每对括号是2个，所以总括号数n必须是2k（k为正整数），如果n是奇数，那合法组合数直接为0，毕竟没法形成成对的括号。
3. 顺序敏感：公式计算的是所有不同顺序的合法序列，比如()()和(())因为结构顺序不同，会被算作两个独立的组合，完全符合你“a,b与b,a视为2种组合”的要求。

递推公式（可选） #

如果你不想直接用组合数计算，也可以用递推的方式从已知项算出下一个卡特兰数：

• 初始项：C_0 = 1（对应0对括号的空序列）
• 递推式：C_{k+1} = sum_{i=0}^k C_i × C_{k-i}

举个例子：
C_1 = C_0×C_0 = 1×1 =1
C_2 = C_0×C_1 + C_1×C_0 =1×1 +1×1=2
C_3 = C_0×C_2 + C_1×C_1 + C_2×C_0=1×2+1×1+2×1=5
结果和之前的公式完全一致。

内容的提问来源于stack exchange，提问作者reByte