如何自然的推出 kthmin-max 容斥

· · 算法·理论

虽然大概率已经有人发过了，但是我觉得很有意思，于是发了。

只考虑 \operatorname{kthmax} 的推导，\operatorname{kthmin} 的是类似的。

我们记 a_1,a_2,\cdots,a_n 为 S 中元素从大到小排序后的结果。

我们希望将 \operatorname{kthmax}(S) 转换为若干个 \min(T) 的线性组合，将式子写出来：\operatorname{kthmax}(S)=a_k=\sum\limits_{i\ge k} a_i\left[i = k\right]。这里莫名其妙的多出了一个 i\ge k 的限制，现在看并没有什么道理，但是在之后的推导中我们希望等式右边的项始终是常数而不是 x^m 这种，所以这个条件是有道理的。

我们令集合 T 的容斥系数为 f_T。则有 \operatorname{kthmax}(S)=\sum\limits_{T\subseteq S,|T| \ge k} f_T\min T = \sum\limits_{i\ge k}a_i\sum\limits_{\max T = i,T\subseteq S}f_T，我们记 T_i = \sum\limits_{\max T = i,T\subseteq S}f_T，则要求 T_i = [i = k]。

为了方便使用一元的形式幂级数，不妨另 f_T = g_{|T|-k}，这样下标便不再是一个集合，而是从 0 开始的整数。这样 T_i 就可以重写为 \sum\limits_{\max T = i,T\subseteq S} g_{|T|-k} = \sum\limits_{t=0}^{i-k}{i-1\choose t+k-1}g_t=\sum\limits_{t=0}^{i-k}(i-1)!\frac{g_t}{(t+k-1)!}\frac{1}{(i-t-k)!}。如果我们将 h_t 定义为 \dfrac{g_t}{(t+k-1)!} 的话，后面这个式子形式是 h_t 与 (i-k)-t 的卷积，而我们希望得到的结果是 T_i = [i-k=0]，所以我们可以考虑用形式幂级数来描述这件事情。

记 H(x) = \sum_{t\ge 0}h_tx^t，则有 H e^x = \dfrac{1}{(k-1)!}，即 H = \dfrac{1}{(k-1)!e^{-x}} = \sum\limits_{t\ge 0}(-1)^t\dfrac{x^t}{(k-1)!t!}。

所以 f_T = g_{|T|-k} = (|T|-1)!h_{|T|-k} = {|T|-1\choose k-1}(-1)^{|T|-k}，我们自然的推出了 kthmin-max 容斥的式子。