组合公式杂记

Raney 引理

对于长度为 \(n\) 的整数序列 \(x\) 满足 \(\sum x_i = 1\)，有且仅有其一个循环序列满足任意非空前缀和为正数（记作合法）。

存在性

考虑找到最大的 \(k\) 满足 \(\sum_{i=1}^k x_i \le 0\)，显然有 \(\sum_{i=k+1} ^n x_i \ge 1\)，把整个序列换成以 \(k+1\) 开头的循环序列 \(x_{k+1,\cdots,n,1,\cdots k}\)，容易发现新序列中原 \([k+1,n]\) 的段前缀和不降且后边的前缀和加上一个正数，于是前缀和的总和加上正数，重复操作直到合法即可。

唯一性

设 \(x\) 是一个合法的循环序列，假设 \(\exists 1 \lt k \le n\)，满足以 \(k\) 开头的循环序列仍然合法。

由 \(x\) 的合法性得 \(\sum_{i=1}^{k-1} x_i \ge 1\)，于是 \(\sum_{i=k}^n x_i \le 0\)，得出矛盾。

应用

Catalan 数推导

Catalan 数的第 \(n\) 项是 \(n\) 个左括号与 \(n\) 个右括号构成的合法括号序列数量。

相当于计数长度为 \(2n\) 的序列中恰有 \(n\) 个 \(1\) 与 \(n\) 个 \(-1\) 且任意前缀非负的序列个数。

考虑增加一个 \(1\)，因为一个有 \(n+1\) 个 \(1\) 与 \(n\) 个 \(-1\) 的任意非空前缀和为正数的序列与上述序列构成双射。

有 \(n+1\) 个 \(1\) 与 \(n\) 个 \(-1\) 的序列一共有 \(\binom{2n+1}{n}\) 个，运用 Raney 引理它的 \(2n+1\) 个循环序列中只有一个合法，于是得到 Catalan 第 \(n\) 项为 \(\dfrac {\binom{2n+1}{n}}{2n+1} = \dfrac{\binom{2n}{n}}{n+1}\)。

P6672 [清华集训 2016] 你的生命已如风中残烛

转化题意为可重集 \(S\) 内有 \(\ge -1\) 的数，每个元素互不相同且元素和为 \(0\)，问将它们排成序列且任意前缀和非负的方案数。

设 \(m=\sum_{i\in S, i \ge 0} i\)，要求 \(\mathrm O(m)\) 的做法。

考虑排成的一个序列 \(x\)，有 \(\sum x_i=0\) 且 \(\forall 1 \le k \le |S|, \sum_{i=1}^k \ge 0\)，于是 \(\forall 0 \le k \lt |S|, \sum_{i=k+1}^{|S|} x_i \le 0\)，发现翻转序列后变为任意前缀为非正数的问题，又把所有数取反转为非负数，这是最大元素是 \(1\)，于是考虑像 Catalan 数的推导一样多加一个 \(1\)，计数得 \(\dfrac {(m+n)!} {m+1}\)。