Raney 引理
GI录像机
·
·
算法·理论
Raney 引理
设整数序列 \{A_n\}，前缀和 S_i = \sum^i_{j=1}A_j。
若 S_n=1，那么在 \{A_n\} 的 n 个循环表示（如 A_1,A_2,\cdots,A_n 或 A_2,\cdots,A_n,A_1）中，有且仅有一个序列 \{B_n\}，满足 \{B_n\} 的任意前缀和均大于 0。
不是那么严谨的证明
我们先将 \{A_n\} 在正整数时扩展一倍（\{S_n\} 也同时扩展），使得 A_{n+i}=A_i。我们可以在 i\le n 时找到一个最小的 S_x（假设只有一个最小值），使得 S_x\le S_j(1\le j\le n)。又因为 S_n = 1，而 S_{n+i}=S_i+A_i+A_{i+1}+\cdots+A_{n+i-1}=S_i+S_n=S_i+1，所以 S_x\le S_j(1\le j\le 2n)。
我们用 \{B_n\} 表示 A_{x+1} 到 A_{n+x} 的 n 个数，使得 B_i=A_{i+x}。那么 \{B_n\} 的前缀和 \{S'_n\} 就可以这么表示：
因为所有的 $S_{i+x}$ 都严格大于 $S_x$，所以此时 $\{B_n\}$ 的任意前缀和均大于 $0$。
如果有多个最小值怎么办？选择最靠后的一个即可，因为其他最小值会因为加 $1$ 而变得更大。
到这里，我们只说明了一定有，没有说明仅有一个。
类似地，可以任选一个不是最小值的 $S_y$，那么 $S_{i+x}=S_x+1\le S_y$，前缀和不会大于 $0$。
若选择是最小值，但不是最后一个的 $S_z$，那么 $S_z=S_x$，而 $x$ 可以被表示成 $i+z$（$i$ 为正数），前缀和会等于 $0$。
故有且仅有一个序列 $\{B_n\}$，满足 $\{B_n\}$ 的任意前缀和均大于 $0$。
## Combinatorial Raney lemma（加强版的 Raney 引理）
设整数序列 $\{A_n\}$，前缀和 $S_i = \sum^i_{j=1}A_j$。
若 $S_n=1$，那么在 $\{A_n\}$ 的 $n$ 个循环表示（如 $A_1,A_2,\cdots,A_n$ 或 $A_2,\cdots,A_n,A_1$）中，有且仅有一个序列 $\{B_n\}$，满足 $\{B_n\}$ 中恰有 $k(1\le k\le n)$ 个前缀和大于 $0$。
证明思路和普通的 Raney 引理差不多。找一下从每个 $x$ 开始循环有多少数满足 $S_{i+x}-S_x>0$ 即可。
具体计算的话就将每个 $S_i$ 以 $S_i$ 的大小为第一关键字，$-i$ 为第二关键字排序。$n$ 个前缀和为正的话就从第一个数的 $i$ 加一开始循环，$n-1$ 个前缀和为正的话就从第二个数的 $i$ 加一开始循环，以此类推即可。
## 例题
### P1044
#### 简要题意：
一个栈（无穷大）的进栈序列为 $1,2,3, \cdots ,n$，有多少个不同的出栈序列？
#### 思路：
有些朋友可能已经看出来了，这不就是卡特兰数吗？但别急着跳过，卡特兰数可以用 Raney 引理推出来。
我们将每次进栈操作抽象成 $+1$，出栈操作抽象成 $-1$，可以发现，我们要求的就是一个包含 $n$ 个 $+1$ 和 $n$ 个 $-1$ 的序列，其前缀和大于等于 $0$ 的方案数。
现在我们给序列多加一个 $+1$，问题变为求一个包含 $n+1$ 个 $+1$ 和 $n$ 个 $-1$ 的序列，其前缀和大于等于 $1$ 的方案数。此时 $S_n=1$ 了，前缀和的要求也从非负变成了正，可以用 Raney 引理了。
Raney 引理告诉我们，每一种循环同构的序列都会提供一个方案。一共有 $C^{n}_{2n+1}$ 种不同的序列（在 $2n+1$ 个位置中选择 $n$ 个位置填 $-1$），但每种序列都可以通过循环表示出 $2n+1$ 个序列，所以对于我们增加一个 $+1$ 后，答案为 $\frac{C^{n}_{2n+1}}{2n+1}=\frac{C^{n}_{2n}}{n+1}$（展开一下就能计算出来）。
那么这是否和原问题答案一致呢？是一致的。任意一个满足要求的序列开头一定是两个 $+1$，否则前缀和不可能均为正。把这个序列最前端的 $+1$ 去掉后，我们就能得到一个包含 $n$ 个 $+1$ 和 $n$ 个 $-1$ 的序列，且其前缀和大于等于 $0$ 。这两种序列是一一对应的，所以可以这么做。
### P6672
#### 简要题意：
牌库中有 $m+1$ 张牌，初始手牌为空。牌库中有 $n$ 张特殊牌，摸到第 $i$ 张牌后可以额外摸 $w_i$ 张牌，保证 $\sum w_i=m$；还有 $m-n$ 张无用牌，摸到不会有任何效果；剩下的一张牌必然在牌库最底部，摸到它就会赢。问开局摸一张牌，能赢的牌库顺序有多少种？
#### 思路
我们设 $s_i$ 为摸到第 $i$ 张牌后还剩下的摸牌次数减一（因为要减去最初的一次摸牌）。对于每张特殊牌，摸到它会花费一次摸牌次数再增加 $w_i$ 次摸牌次数，也就是说，摸到它会增加 $w_i-1$ 次摸牌次数。而普通牌则会增加 $-1$ 次摸牌次数。
因为 $\sum w_i=m$，所以 $\sum (w_i-1)=m-n$，而普通牌的数量恰好有 $m-n$ 张，所以 $s_m=\sum (w_i-1)-(-1)\times(m-n)=0$。
序列 $s_i$ 要求大于等于 $0$（本来应该是大于等于 $1$，因为还要摸下一张牌，但 $s_i$ 表示的是摸牌次数减一），而 $s_m = 0$。回忆我们证卡特兰数的过程，那时候我们添加了一个 $+1$ 使得整个序列可以使用 Raney 引理。但这题不能这么做，因为 $+1$ 不一定在第一位，它可以是任何正的 $w_i$。
观察发现该序列的后缀和一定小于等于 $0$（后缀和等于 $s_m$ 减去对应前缀和），而且最小的数是 $-1$。考虑在序列末尾添加一个 $-1$。
这样做有什么用呢？我们将整个序列的数变成其相反数，再将序列倒过来，由我们添加的 $-1$（取反后是 $1$）开头。观察这个序列的性质，发现它完美符合 Raney 引理的条件。前缀和要求大于等于 $1$，那么第一个数就确定是 $1$ 了，而且所有数的和也等于 $1$。
这下就可以使用 Raney 引理了。一共有 $(m+1)!$ 个序列，每个序列有 $m+1$ 个循环同构，那么满足条件的序列一共有 $\frac{(m+1)!}{m+1}=m!$ 种。
但这道题的 $-1$ 是有标号的，上一道没有。因此我们还需要消除标号的影响。$m-n$ 个原来的 $-1$ 之间有 $m-n-1$ 个空，加上首尾，一共有 $m-n+1$ 个地方可供新的 $-1$ 插入。故而最终答案为 $\frac{m!}{m-n+1}$。
## 碎碎念
几何证明实在看不懂……没办法自己琢磨了一个不需要数形结合的证明方式。