Raney 定理

· · 个人记录

Raney 定理：对于一个总和为 1 长度为 n 的整数序列 a，其 n 种循环移位中一定有一种满足对于任意 i,\sum_{i=1}^i a_i=s_i>0。

证明：考虑我们将 k 这个位置放到最前面，那么 k 后的位置相当于 -s_k，前面的位置由于 s_n=1 相当于 -s_k+1。 那么在除了最小值中最靠后的以外均不满足要求（不能为 0）。

另外一个引理：序列 a 没有 <n 的循环节。原因是总和为 1 不能分解。

作用：这两个加起来相当于我们可以将所有的方案划分成若干个循环移位组（不难发现组间没有相同）。这使得我们对于类括号匹配（一个位置可能有多个）提供了一种方便的刻画（仅需除一个值即可）。

一个例子是证明卡塔兰数的公式：

ans_n=\frac{\binom{2n}{n}}{n+1}

不难发现，对于所有的合法方案，我们在前面加上一个左括号就变成了 Raney 定理（一一对应才能转化），那么答案即为：

ans_n=\frac{\binom{2n+1}{n+1}}{2n+1}=\frac{\binom{2n}{n}}{n+1}

使用吸收公式可得。

题目有 agc065d，P6672 等。