二项式反演/minmax容斥初探

世界是物质的，物质是运动的，运动是有规律的，规律是可以被认识的

二项式反演

[ g_n=sum_{i=0}^n binom{n}if_iRightarrow f_n=sum_{i=0}^n(-1)^{n-i}binom{n}ig_i ]

证明如下

[ begin{aligned} sum_{i=0}^n(-1)^{n-i}binom{n}ig_i &=sum_{i=0}^n(-1)^{n-i}binom{n}isum_{j=0}^ibinom{i}jf_i\ &=sum_{j=0}^nf_i sum_{i=j}^n(-1)^{n-i}binom{n}ibinom{i}j\ &=sum_{j=0}^nf_i sum_{i=j}^n(-1)^{n-i}binom{n}jbinom{n-j}{i-j}\ &=sum_{j=0}^nbinom{n}jf_j sum_{i=j}^n(-1)^{n-i}binom{n-j}{i-j}\ &=sum_{j=0}^nbinom{n}jf_j sum_{i=0}^{n-j}(-1)^{n-j-i}binom{n-j}i\ &=sum_{j=0}^nbinom{n}jf_jtimes (1-1)^{n-j} end{aligned} ]

在默认(0^0=1)的情况下，显然

[ sum_{j=0}^nbinom{n}jf_jtimes (1-1)^{n-j}=f_n\ f_n=f_n ]

最值反演

[ max(S)=sum_{Tsubseteq S} (-1)^{|T|-1}min(T)\ E(max S)=sum_{Tsubseteq S} (-1)^{|T|-1}E(min T)\ text{lcm}(S)=prod_{Tsubseteq S} (-1)^{|T|-1}gcd(T)\ ]

其中，(S,Tnot=varnothing)。

推导第一类

设系数函数(f)满足
[ max(S)=sum_{Tsubseteq S} f(|T|)min(T) ]

考虑(S)中第(x+1)大元素作为子集的最小值的情况数，显然
[ sum_{i=0}^xbinom{x}if(i+1) = [x=0]\ f(x+1)=sum_{i=0}^x(-1)^{x-i}binom{x}i[i=0]=(-1)^x ]
于是(f(x)=(-1)^{x-1})。

扩展
[ text{maxk}(S)=sum_{Tsubseteq S} f(|T|)min(T) ]
此时需要满足
[ sum_{i=0}^xbinom{x}if(i+1) = [x=k-1]\ f(x+1)=sum_{i=0}^x(-1)^{x-i}binom{x}i[i=k-1]=(-1)^{x-k+1}binom{x}{k-1} ]
即(f(x)=(-1)^{x-k}binom{x-1}{k-1})。
[ text{maxk}(S)=sum_{Tsubseteq S}(-1)^{|T|-k}binom{|T|-1}{k-1}min(T) ]