什么是反演:
有函数,令,其中x与s的关系自定,在已知求的过程叫反演。
集合反演:
公式:
推导过程: 核心是容斥。
首先,当那么所有都被加入,我们要把除了之外的都删掉。
我们将与相差的都减去,他们两两之间的交***减两次,还要再加回,那么就变成了容斥的形式。
莫比乌斯反演:
公式:
推导过程:与集合反演类似,但是更加复杂,核心也是容斥。
首先,代表要加入还是删除,类似于集合反演,我们想要找到在与的某种关系下固定的系数,对于集合是,对于莫比乌斯反演,我们选择。我们令,分类讨论:
若,即,我们必须选,于是
若是质数,是变成“子集”的最小单位,我们把他删除,
若是两个不同质数的乘积,那么被这两个质数删了两次要加回,那么。
那么三个质数时呢 ,我们又要减去,现在又变成了容斥的形式,所以当是个不同质数的乘积时。
我们发现整个过程已经完毕,那么其余。
总结-莫比乌斯函数:
一些公式:
(组合数可证)
(左面通分,同去掉分母,根据反演可得)
(反演回去可得)
扩展-莫比乌斯反演的另一种形式(更加常用):
与原式一样容斥可得到。
应用:
求
设是的数对个数,是的数对个数,那么:
根据扩展:
于是
全部评论
(4) 回帖