Min-Max 容斥，即 $$\max(S)=\sum_{T\in S,T\neq\emptyset}(-1)^{|T|-1}\min(T)$$
接下來證明上面那個式子是對的。定義 \(S\) 中共有 \(N\) 個元素，由大到小分別為 \(s_1,s_2,\dots,s_N\)，\(T_i\) 為所有 \(S\) 大小為 \(i\) 的子集。
所有元素都大于 \(s_i\) 且大小為 \(j\) 的子集有 \(\tbinom{i-1}{j}\) 個；則最小元素為 \(s_i\) 且大小為 \(j\) 的子集，即 \(s_i\) 并上任意一個所有元素都大于 \(s_i\) 且大小為 \(j-1\) 的子集，有 \(\tbinom{i-1}{j-1}\) 個。
那么，滿足 \(\min(T)=s_i\) 的 \((-1)^{|T|-1}\) 之和為 \(\sum\limits_{j=1}^{i}(-1)^{j-1}\tbinom{i-1}{j-1}\)，根據(jù)二項式定理，這個東西等于 \((1+(-1))^{i-1}\) 即 \(0^{i-1}\)。除了 \(s_1\) 即最大值，其他元素的系數(shù)都為 \(0\)；而 \(0^0\) 無意義，根據(jù)組合數(shù)的定義， \(s_1\) 的系數(shù)為 \(1\)（這就相當(dāng)于構(gòu)造了一個“開關(guān)”，只有最大值才不會被抵消）。于是得證。文章來源：http://www.zghlxwxcb.cn/news/detail-844407.html
在組合計數(shù)中，Min-Max 容斥有時很有用。比如有 \(N\) 種球，每次會隨機(jī)抽到 \(1\) 種，求每種球都至少抽到 \(A_i\) 個的期望次數(shù)，相當(dāng)于求最晚滿足要求的那種球滿足要求的時間，這是沒有上限的。但是如果使用 Min-Max 容斥，就可以轉(zhuǎn)換為每個子集最早滿足要求的那種球滿足要求的時間，這個東西的上限是 \(\sum{(A_i-1)}+1\)，可以簡單改寫式子，然后合并類似狀態(tài)進(jìn)行 DP。文章來源地址http://www.zghlxwxcb.cn/news/detail-844407.html
到了這里，關(guān)于組合數(shù)學(xué)——Min-Max容斥的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
