括号序列

Kubic · 2022-06-14 21:10:54 · 个人记录

此处讨论的括号序列指的是一个 1,-1 序列满足所有前缀和都 \ge 0。

常见转化：与无标号，儿子有顺序的有根森林，有根二叉树一一对应，或者转化为格路计数。

有一种比较难想到的是把问题放到一个长度为 n+1 的环上，初始默认都是 -1，然后按照任意顺序插入所有 1。

插入一个 1 的过程如下：

• 钦定这个 1 要放位置 x。

• 顺时针走，直到找到一个空位，并把当前这个 1 放入空位中。

那么括号序列合法当且仅当 n+1 是空位。

这个模型有很好的对称性，因为是在环上，所以每一个位置是等价的。很多题都需要利用这一点来做。

通过这个就可以非常轻易地证明卡特兰数的公式 C_n=\dfrac{\dbinom{2n}{n}}{n+1}。