又有老哥不明白容斥的g,f关系了,强行解释一波

一般的容斥方法是首先钦定i个点固定,剩下的随便做,然后对\sum_i的情况带系数求和。

常常见的式子是这样的f(i)=\sum_{i\geq 0}\binom{n}{i}g(i)\alpha(n,i)

其中\alpha(n,i)是有关n,i的二元系数,g可能会被叫“至少”。

我们发现g前面有一个\binom{n}{i}的系数,说明已经钦点出了i个点,

所以对于g(i),再进行钦点的时候需要从剩下n-i个点里面钦点,也就是g(i)=\sum_{j\geq 0}^{n-i}\binom{n-i}{j}f(i+j)=\sum_{j\geq i}^{}\binom{n-i}{j-i}f(j)

所以f(i)=\sum_{i\geq 0}\binom{n}{i}\sum_{j\geq i}\binom{n-i}{j-i}f(j)\alpha(n,i)

然后考虑对于单个f(i)的贡献,交换\sum,变成\sum_{j\geq 0}f(j)\sum_{i\leq j}\binom{n-i}{j-i}\binom{n}{i}\alpha(n,i)

套那个经典的二项式系数转化,变成\sum f(j)\binom{n}{j}\sum \binom{j}{i}\alpha(n,i)就可以导出单个f(j)被计算的次数;

后面当\sum_i\binom{j}{i}\alpha(n,i)=[j=0],所以\alpha(n,i)=(-1)^{i},如果要求条件并,全集减去即可。

注意到f(j)有一个\binom{n}{j}的系数,所以其实对于满足恰好j个条件的应该是\binom{n}{j}f(j)f(j)本身是满足的条件集{\rm P},|{\rm P}|=|j|确定后,方案数只跟条件集大小相关罢了.

如果用贡献法证明,选的对象是{\rm P},|{\rm P}|=|j|条件集贡献,实际需要再加一个二项式系数

上面这是狭义容斥,广义容斥的g和f都是还未钦点的,具体可以用生成函数证明,发现里面还要再做钦点。

对比二项式反演,g的定义事至多,区分一下狭义容斥和广义容斥的至少

2022.9.26补
上一篇 «
2022.9.20补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors