Raney 引理

b6e0_ · 2024-05-03 14:08:28 · 算法·理论

Raney 引理：对于任意整数序列 \{a_n\}，存在一个循环移位使得每个前缀和都 >0 的充要条件是 \sum a_i>0。

必要性显然，下面证明充分性。

证法一：

运用归纳法，n=1 时显然成立。设 <n 时命题成立，尝试证明 n 成立。

首先，若序列中存在 0，可以删去它们后运用归纳假设，易证。下面假设序列中不存在 0。

将序列看成一个环。首先将环上所有连续的正数以及连续的负数求和，得到一个正负交替的环。记当前环长为 n'，若 n'=1 则直接得证，否则容易发现正负数个数相同。然后，从任意正数开始，将相邻的一个正数和一个负数求和，得到长为 \frac{n'}2 的环。

根据归纳假设，这个环有满足前缀和都 >0 的分割成序列的方式。设这个分割点在 i，第 i 个数是原序列（环）中 [l,r] 的和，那么在原序列（环）中从 l 处分割成序列，容易验证此时所有前缀和都 >0。得证。

此证法的缺陷在于没有给出显式的构造。我把这么长而无用的证法留在这里主要是因为它是我给出的

证法二：取前缀和的最靠后的最小值作为循环移位的第一个元素即可，容易验证满足要求。

根据这个证法，还可对引理进行扩展：若 \sum a_i=1，则存在恰好一个循环移位满足要求。

运用这个扩展，我们可以证明卡特兰数的通项公式。卡特兰数可以看作，长 2n 的序列，只包含 \pm1，和为 0，且每个前缀和 \ge0 的方案数。序列前面添加一个 1，即可变为满足以下要求的序列的个数：

1. 长 2n+1；
2. 只包含 \pm1；
3. 和为 1；
4. 每个前缀和 >0。

根据扩展的引理，对于所有满足前三条的序列，每个循环同构的等价类中只有一个满足第四条。而每个等价类的大小都是 2n+1，这是因为根据数论知识，若 a_i=a_{(i+k)\bmod n}，则若 i\equiv j\pmod{\gcd(k,n)} 则 a_i=a_j，这意味着若 k 不是 n 的倍数，则对于每个数 x，\{a_n\} 中 x 的个数一定不与 n 互质，而 n,n+1 都与 2n+1 互质，所以不可能存在这样的 k。所以