组合数学第四版卢开澄标准答案-第三章

?(n)?n?d|n?(d)d 。

证法二：采用分类法

设n?p11?p22???pkk，其中p1, p2,?, pk是互不相同的k个素数。又设n的因子为d1, d2,?, dm(其中d1=1) ，那么 di?????pj?1k?jj(0??j??j)

考虑和式 n?d|n?(d)d?n(?(d1)d1??(d2)d2???(dm)dm) (*)

对每个di作质因子分解(它们的质因子都属于{p1, p2,?, pk})，根据M?bius函数?(n)的定义，若di具有重复的质因子，则?(di)=0。这就意味着在(*)式中它将不参加计数。去掉这些具有重复质因子的因子di，把剩下的具有不同质因子的di按其质因子个数分类。第一类具有一个质因子，第二类具有两个质因子，?，等等。并考虑到d1=1，那么(*)式等于

n(1?1?i?k?p1i?1?i?j?k?11???(?1)k) (**) pipjp1p2?pk与定理3.6(课件例3.3.7. )比较，(**)式等于? (n)。因此

?(n)?n?d|n?(d)d 。

3.77.设f是满足f(mn)=f(m)f(n)，g(n)??f(d)，试证：g(mn)=g(m)g(n)。

d|n[证].分情况证明如下：

(1)若m与n互素，即(m,n)=1，则根据定理3.9(第三版P256)，我们有g(mn)=g(m)g(n)。 (2)若m与n不互素，则可设(m,n)=d?1，于是不妨设m=dm1(且(m1,d)=1)，n=dkn1(且(n1, dk)=1，k?1)，于是 (m1n1, dk+1)=1(用反证法易证) ，从而根据定理3.9(第三版P256)，我们有g(m)= g(dm1)=g(d)g(m1) ，g(n)= g(dkn1)=g(dk)g(n1) ，并且所以

g(mn)= g(dm1dkn1)= g(dk+1m1n1)

=g(dk+1)g(m1n1) (因为(m1n1, dk+1)=1及定理3.9) =g(d)g(dk)g(m1)g(n1) (g(dk+1)= g(d)g(dk)见下面的证明) =g(d)g(m1)g(dk)g(n1)

=g(m)g(n) 。 (因为已证g(m)= g(d)g(m1) 及g(n)=g(dk)g(n1))

下面的证明g(dk+1)= g(d)g(dk)

g(dk?1)???d1|dd?|d?f(d?)???f(ddk?112)(令:d?=d1d2)

d1|dd2|dkd1|dd2|dk?f(d)f(d1d2|dk2)(根据f(mn)= f(m)f(n)得f(d1d2)=f(d1)f(d2))

。

??f(d1)?f(d2)?g(d)g(dk)3.78. n是正整数，n的正除数的数目用来表示，试证：

??(d)?()?1。

d|nnd【第 41 页 共 42 页】

[证].因为 ?(n)??1，

d|n 所以，根据M?bius反演定理，即得 1?

??(d)?()，就是

d|nnd??(d)?()?1。

d|nnd【第 42 页 共 42 页】