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

?(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 页】