Raney 引理和它的一个扩展

具体数学我劝你多读．

Raney 引理

对于长度为 $n$，所有元素和为 $1$ 的整数序列 $a_i$，其恰好存在 $1$ 个循环位移满足所有前缀和大于 $0$．

证明：

1. 存在性：

   记 $s_i = \sum_{j \le i} a_j$，取最大的 $k$ 满足 $\forall i, s_i \ge s_k$，构造循环位移 $\langle b_i \rangle = \langle a_{k + 1}, a_{k + 2}, \cdots, a_n, a_1, a_2, \cdots, a_k \rangle$，我们尝试说明 $b_i$ 的所有前缀和大于 $0$．记 $t_i = \sum_{j \le i} b_i$：

   1. $1 \le i \le n - k$ 时，$t_i = s_{k + i} - s_k$，由于 $s_k$ 是最小的前缀和中最靠后的，有 $t_i > 0$．
   2. $n - k < i \le n$ 时，$t_i = s_n - s_k + s_i = 1 + (s_i - s_k) > 0$．

2. 唯一性：

   假设有两个循环位移的起始位置分别是 $i$ 和 $j$，且这两个循环位移均满足条件．不妨令 $s_0 = 0$，有 $s_{j - 1} - s_{i - 1} > 0, s_n - s_{j - 1} > 0$，整理后得 $s_n > s_{j - 1} > s_{i - 1}$．考察 $j$ 位移后 $i - 1$ 所在位置的前缀和，为 $s_n - s_{j - 1} + s_{i - 1} = 1 + (s_{i - 1} - s_{j - 1}) < 1$．又元素均为正整数，则 $s_n - s_{j - 1} + s_{i - 1} \le 0$，与条件矛盾，故最多存在 $1$ 个．

得证．

Raney 引理可以用来计算长度为 $2n$ 的合法括号序列的个数，即卡特兰数．考察任意括号序列，将 ( 看作 $1$，) 看作 $-1$，括号序列合法的条件是对应的整数序列所有前缀和 $\ge 0$．问题转化为计算有 $n$ 个 $1$ 和 $n$ 个 $-1$，且所有前缀和 $\ge 0$ 的整数序列个数．考察任意合法的序列，我们在其前面添加一个 $1$，就转化成了一个有 $n + 1$ 个 $1$ 和 $n$ 个 $-1$，且所有前缀和 $> 0$ 的序列．考察任意一个有 $n + 1$ 个 $1$ 和 $n$ 个 $-1$ 的序列，由 Raney 引理，它的所有循环移位中恰有 $1$ 个满足所有前缀和 $> 0$ 的限制，问题转化为计算 $n + 1$ 个 $1$ 和 $n$ 个 $-1$ 构成的圆排列的数量．由于序列的和为 $1$，任意一个圆排列一定对应着 $2n + 1$ 个不同的排列，故答案为 $\frac{1}{2n + 1} \binom{2n + 1}{n + 1} = \frac{1}{n + 1} \binom{2n}{n}$．

一个扩展

如果 $\langle a_1, a_2, \cdots, a_n\rangle$ 满足 $a_i \le 1$，且 $\sum_i a_i = l > 0$，那么它的循环位移中恰好有 $l$ 个满足所有前缀和大于 $0$．

证明：

若未加额外说明，变元均为整数．

考虑将序列进行周期延拓，即复制很多份接在后面．设延拓后的序列为 $b_i$，记 $t_i = \sum_{j \le i} b_j$．

对于 $t_i$ 中的一个位置 $p$，我们称 $1 \le q \le n, q + \alpha n = p$ 为 $p$ 在原序列对应的位置．容易发现这样的 $q$ 唯一，记作 $o_p$．$o_p$ 被挪到最后的循环移位合法，等价于 $\forall 1 \le i \le n, t_{p + i} - t_p > 0$，即 $t_{p + i} > t_p$，又 $t_{i + n} = t_i + l > t_i$，可推出 $\forall i > p, t_i > t_p$．进一步的，我们有 $\forall k \ge 0, \forall i > o_p + kn, t_i > t_{o_p + kn}$．记 $t_{o_p} = x$，考虑 $1 \le y \le l, y + \beta l = x$，显然 $y$ 唯一，且 $t_{o_p + \beta n}$ 是 $y$ 最后一次出现的位置．由于 $a_i \le 1$，对于 $1$ 到 $l$ 的所有值，这样的位置都存在．设 $\mathrm{lst}_y$ 是 $y$ 在 $t_i$ 序列中最后出现的位置，对于所有 $y$，将 $o_{\mathrm{lst}_y}$ 挪到最后的循环位移均合法．这样的位置恰好有 $l$ 个，选取这些 $\mathrm{lst}_y$ 就构造了 $l$ 个合法的循环位移．而考虑任意不在这 $l$ 个位置中的任意位置 $r$，一定存在 $z > r$ 使得 $t_z = t_r$，使得 $r$ 被挪到最后的循环位移一定不合法．