数学知识

莫比乌斯反演 设F(n)和f(n)为定义在非负整数集合上的函数，令 F(n)=∑d|nf(d) ,则有结论： f(n)=∑d|nμ(d)F(nd) 函数μ的定义如下： （1）若d=1，那么 μ(d)=1 ; （2）若 d=p1∗p2∗…∗pk ，pi均为互异素数，那么 μ(d)=(−1)k ; （3）其它情况下 μ(d)=0 ;

对于函数，它有如下的常见性质： （1）对任意正整数有 （2）对任意正整数有 证明: ∑d|nμ(d)F(nd)=∑d|nμ(d)∗∑d′|ndf(d′)=∑d′|nf(d′)∑d|nd′=f(n)

错排公式 D(n)=n!∗∑ni=2−1i∗1i!=[n!e+0.5] ;