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

【第 1 页 共 42 页】 第三章

3.12.一年级有100名学生参加中文，英语和数学的考试，其中92人通过中文考试，75人通

过英语考试，65人通过数学考试；其中65人通过中，英文考试，54人通过中文和数学考试，45人通过英语和数学考试，试求通过3门学科考试的学生数。

[解].令：A 1={通过中文考试的学生}

A 2={通过英语考试的学生}

A 3={通过数学考试的学生}

于是 |Z| =100，|A 1|=92，|A 2|=75，|A 3|=65

|A 1∩A 2|=65，|A 1∩A 3|=54，|A 2∩A 3|=45

此题没有给出：

有多少人通过三门中至少一门；

有多少人一门都没通过。

但是由 max{ |A 1|,|A 2|,|A 3| }=max{92,75,65}=92

故可以认为：

至少有92人通过三门中至少一门考试，即100≥|A 1∪A 2∪A 3|≥92

至多有8人没通过一门考试，即0≤|1A ∩2A ∩3A | ≤8

于是，根据容斥原理，有

|A 1∪A 2∪A 3|=(|A 1|+|A 2|+|A 3|)-(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)+|A 1∩A 2∩A 3|

即 |A 1∩A 2∩A 3|=|A 1∪A 2∪A 3|-(|A 1|+|A 2|+|A 3|)+(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)

=|A 1∪A 2∪A 3|-(92+75+65)+(65+54+45)

=|A 1∪A 2∪A 3|-232+164

=|A 1∪A 2∪A 3|-68

从而由 92-68≤|A 1∪A 2∪A 3|-68≤100-68

即 24≤|A 1∪A 2∪A 3|-68≤32

可得 24≤|A 1∩A 2∩A 3| ≤32

故此，通过3门学科考试的学生数在24到32人之间。

也可用容斥原理，即

|1A ∩2A ∩3A |=|Z|-(|A 1|+|A 2|+|A 3|)+(|A 1∩A 2|+|A 1∩A 3|+|A 2∩A 3|)-|A 1∩A 2∩A 3|

=100-(92+75+65)+(65+54+45)-|A 1∩A 2∩A 3|

=100-232+164-|A 1∩A 2∩A 3|

【第 2 页 共 42 页】 =32－|A 1∩A 2∩A 3|

从而有 |A 1∩A 2∩A 3|=32-|1A ∩2A ∩3A |

由已知 0≤|1A ∩2A ∩3A |≤8，可得

24≤|A 1∩A 2∩A 3|≤32

故此，通过3门学科考试的学生数在24到32之间。

3.13.试证：(a)|A ∩B|=|B|-|A∩B|

(b)|A ∩B ∩C|=|C|-|A∩C|-|B∩C|+|(A∩B∩C )|

[证].(a)B =B∩Z (因为B ?Z)

= B∩(A ∪A ) (零壹律:且有互补律Z=A ∪A ) =(B∩A )∪(B∩A ) (分配律)

=(A∩B )∪(A ∩B ) (交换律)

另外 (A∩B )∩(A ∩B )

= (A∩A )∩B (结合律，交换律，幂等律) =?∩B (互补律A∩A =?)

=? (零壹律)

所以 |B|=|A∩B|+|A ∩B|

因此 |A ∩B|=|B|-|A∩B| (b)|A ∩B ∩C|=|B A ?∩C| (de Morgan 律) =|C|-|(A ∪B)∩C| (根据(a)，令A 1=A ∪B) =|C|-|(A∩C )∪(B∩C )| (分配律)

【第 3 页 共 42 页】 =|C|-(|A∩C|+|B∩C|-|(A∩C )∩(B∩C )|)

=|C|-|A∩C|-|B∩C|+|(A∩C )∩(B∩C )|

=|C|-|A∩C|-|B∩C|+|(A∩B∩C )| (结合律，交换律，幂等律)

3.1

4. N={1,2,…,1000}，求其中不被5和7除尽，但被3除尽的数的数目。

[解].定义： P 1(x ):3|x A 1={x |x ∈N ∧P 1(x )}

P 2(x ):5|x A 2={x |x ∈N ∧P 2(x )}

P 3(x ):7|x A 3={x |x ∈N ∧P 3(x )}

|A 1| =?1000/3?=333 |A 1∩A 2|=?1000/(3×5)?=66

|A 1∩A 3|=?1000/(3×7)?=47 |A 1∩A 2∩A 3|=?1000/(3×5×7)?=9

因此 |A 1∩2A ∩3A |=|A 1|-|A 1∩A 2|-|A 1∩A 3|+|A 1∩A 2∩A 3|

=333-66-47+9

=229

因此 ，在1～1000中能被3整除，同时不能被5和7整除的数有229个。

3.15. N={1,2,?,120}，求其中被2,3,5,7,m 个数除尽的数的数目，m =0,1,2,3,4 。求不超过120

的素数的数目。

[解].定义 P 1(x ):2|x A 1={x |x ∈N ∩P 1(x )}

P 2(x ):3|x A 2={x |x ∈N ∩P 2(x )}

P 3(x ):5|x A 3={x |x ∈N ∩P 3(x )}

P 4(x ):7|x A 4={x |x ∈N ∩P 4(x )}

|A 1|=?120/2?=60 |A 2|=?120/3?=40 |A 3|=?120/5?=24 |A 4|=?120/7?=17 |A 1∩A 2|=?120/(2×3)?=20 |A 1∩A 3|=?120/(2×5)?=12 |A 1∩A 4|=?120/(2×7)?=8 |A 2∩A 3|=?120/(5×7)?=8 |A 2∩A 4|=120/(3×7)?=5 |A 3∩A 4|=?120/(5×7)?=3 |A 1∩A 2∩A 3|=?120/(2×3×5)?=4 |A 1∩A 2∩A 4|=?120/(2×3×7)?=2

【第 4 页 共 42 页】 |A 1∩A 3∩A 4|=?120/(2×5×7)?=1 |A 2∩A 3∩A 4|=?120/(3×5×7)?=1

|A 1∩A 2∩A 3∩A 4|=?120/(2×3×5×7)?=0 |N|=120

p 0=|N|=120

p 1=|A 1|+|A 2|+|A 3|+|A 4|=60+40+24+17=141

p 2=|A 1∩A 2|+|A 1∩A 3|+|A 1∩A 4|+|A 2∩A 3|+|A 2∩A 4|+|A 3∩A 4|=20+12+8+8+5+3=56

p 3=|A 1∩A 2∩A 3|+|A 1∩A 2∩A 4|+|A 1∩A 3∩A 4|+|A 2∩A 3∩A 4|=4+2+1+1=8

p 4=|A 1∩A 2∩A 3∩A 4|=0

① 当m =0时，q 0=p 0-p 1+p 2-p 3+p 4=120-141+56-8+0=27

当m =1时，q 1=p 1-????

??12p 2+???? ??23p 3-???

? ??34p 4=141-2×56+3×8-4×0=53 当m =2时，q 2= p 2-????

??13p 3+???

? ??24p 4=56-3×8+6×0=32 当m =3时，q 3= p 3-???

?

??14p 4=8-4×0=8 当m =4时，q 4= p 4=0

② 由于120<121=11，所以不超过120的合数一定有不超过10的因子，因而一定有

2,3,5,7的素因子(因为10以内的素数只用2,3,5,7)，所以不超过120的素数一定是那些不能被2,3,5,7除尽的数(当然还要去掉非素数的数1)，故此不超过120的素数的数目=q 0-1=27-1=26个。

3.16.求正整数n 的数目，n 除尽1040,2030中的至少一个数。

[解]. 定义：P 1(x ):x |1040 A 1={x|x ∈N ∩P 1(x )}

P 2(x ):x |2030 A 2={x|x ∈N ∩P 2(x )}

由于 1040=(2×5)40=240×540 2030=(22×5)30=260×530

故此 |A 1|=(40+1)(40+1)=1681

|A 2|=(60+1)(30+1)=1891 (参见第一章第九题)

|A1∩A2|=(40+1)(30+1)=1271

于是|A1∪A2|=|A1|+|A2|-|A1∪A2|=1681+1891-1271=2301

因此，能至少除尽1040和2030之一的正整数的数目是2301。

3.17.n是除尽1060,2050,3040中至少一个数的除数，求n的数目。

[解].定义：P1(x):x|1060A1={x|x∈N∩P1(x)}

P2(x):x|2050A2={x|x∈N∩P2(x)}

P3(x):x|3040A3={x|x∈N∩P3(x)}

由于1060=(2×5)60=260×5602050=(22×5)50=2100×550 3040=(2×3×5)40=240×340×540故此：|A1|=(60+1)(60+1)=3721

|A2|=(100+1)(50+1)=5151

|A3|=(40+1)(40+1)(40+1)=68921

|A1∩A2|=(60+1)(50+1)=3111

|A1∩A3|=(40+1)(40+1)=1681

|A2∩A3|=(40+1)(40+1)=1681

|A1∩A2∩A3|=(40+1)(40+1)=1681

根据容斥原理，有

|A1∪A2∪A3|=(|A1|+|A2|+|A3|)- (|A1∩A2|+|A1∩A3|+|A2∩A3|)+|A1∩A2∩A3|

=(3721+5151+68921)-(3111+1681+1681)+1681

=73001

所以，至少能整除1060,2050,3040之一的正整数n有73001个。

3.18求下列集合中不是2n，3n形式的数的数目，n∈N 。

（a）{1，2，……，4

10} （=N1）

（b）{3

10} （=N2）

10，3

10+1，……，4

【第 5 页共42 页】

【第 6 页 共 42 页】 【解】：（a ）定义：P1（x ）:x=2n （n ∈N ） A1=｛x|x ∈N1∩P1(x)｝ P2（x ）:x=3n （n ∈N ） A1=｛x|x ∈N2∩P2(x)｝

A1={21，22，……，22)10(}1N ? 故|A1|=210=100 A2={31，32，……，321}1N ? 故|A2|=21 （因为321=9261＜410＜10648=322） A1∩A2={61，62，63，64}1N ?，故|A1∩A2|=4 （因为64=4096＜410＜15625=65） 因此，根据容斥原理，有 |1A ∩2A |=|N1|-（|A1|+|A2|）+|A1∩A2| = 410－（100+21）+4 =9883 （b ）定义：P1（x ）:x=2n （n ∈N ） A1=｛x|x ∈N1∩P1(x)｝ P2（x ）:x=3n （n ∈N ） A1=｛x|x ∈N2∩P2(x)｝

A1={231，……，22)10(}2N ? 故|A1|=100-30=70 （因为231=961＜310＜1024=232） A2={310，……，321}2N ? 故|A2|=21-9=12

A1∩A2={64}2N ? 故|A1∩A2|=1

【第 7 页 共 42 页】 （因为63=729＜310＜64=4096＝

因此，根据容斥原理，有 |1A ∩2A |=|N1|-（|A1|+|A2|）+|A1∩A2|

= 9001－（70+12）+1

= 8920

3.19 {1000，1001，……，3000}，求其中是4的倍数但不是100的倍数的数的数目。

【解】： 令N1={1000，1001，……，3000}，则 |N1|=2001

P1（x ）:4|x A1=｛x|x ∈N1∩P1(x)｝

P1（x ）:100|x A1=｛x|x ∈N2∩P2(x)｝

于是由 A1={4·250，4·251，……，4·750}?N1，

故 |A1|=750－250+1=501，

A1∩A2={100·10，100·11，……，100·30}?N1，

故 |A1∩A2|=30－10+1=21

因此 |A1∩2A |=|A1|－|A1∩A2|=501－21=480

所以，1000～3000中只能被4整除，但不能被100整除的数有480个。

3.20 在由a,a,a,b,b,b,c,c,c 组成的排列中，求满足下列条件的排列数， （a ）不存在相邻3元素相同

（b ）相邻两元素不相同

【解】：（a ）定义：Z={9个元素的全排列}，|Z|=！

！！！3339=1680 P1(x)：排列x 中有相邻三元素相同，且是a

【第 8 页 共 42 页】 P2(x)：排列x 中有相邻三元素相同，且是b

P3(x)：排列x 中有相邻三元素相同，且是c

A1={x |x ∈Z ∩P1(x)} |A1 |=!

3!3!7=140 A2={x |x ∈Z ∩P2(x)} |A2 |=

!3!3!7=140 A3={x |x ∈Z ∩P3(x)} |A3 |=!

3!3!7=140 |A1∩A2|=!3!5=20 |A1∩A3|=!

3!5=20 |A2∩A3|=

!3!5=20 |A1∩A2∩A3|=3！=6 于是，根据容斥原理，有

|1A ∩2A ∩3A |=|Z |－（|A1|+|A2|+|A3|）+（|A1∩A2|+|A1∩A3|+|A2∩A3|） －|A1∩A2∩A3|

=1680－3×140＋3×20－6=1314

（b ）定义：Z={9个元素的全排列}，|Z|=！

！！！3339=1680 P1(x)：排列x 中有相邻两个元素相同，且是a

P2(x)：排列x 中有相邻两个元素相同，且是b

P3(x)：排列x 中有相邻两个元素相同，且是c

i A ={x|x ∈Z ∩i P (x)} (1≤i ≤3) |A1|=!3!3!8－!

3!3!7=1120－140=980 (因为将aa 与a 看做为不同的两个元素参与排列，在它们相遇之时会产生重复，

其重复因子刚好是将aaa 看作一个整体参与排列的个数)

同理可得：|A2|=!3!3!8－!

3!3!7=1120－140=980

【第 9 页 共 42 页】 |A3|=!3!3!8－!

3!3!7=1120－140=980 因为A1∩A2为aa,bb 图象都出现的排列集合，当我们将aa 与a,bb 与b 看作

不同的两对元素进行排列时，在aa 与a 相遇而成aaa 图象及bb 与b 相遇而成bbb 图象时会产生重复计数。

当aaa 图象与bbb 图象恰出现一个时，重复因子为2；当图象aaa 与图象bbb

同时出现时，重复因子为4 。

设 q1(x)：排列x 中aa 与a 相遇而有aaa 图象

q2(x)：排列x 中bb 与b 相遇而有bbb 图象

故 B1={x |x ∈A1∩A2∩q1(x)} B2={x |x ∈A1∩A2∩q2(x)} 于是 |B1| = |B2| =!3!6 =120 |B1∩B2| =!

3!5 =20 P1 = |B1| + |B2| =2×120 =240 P2 = |B1∩B2 |=20

q1=P 1－2P2 =240－2×20=200 q2=P2=20

从而 |A1∩A2| =!

3!7－（q1+3q2）=840－(200+3×20)=580 同理，|A1∩A3 | =580 |A2∩A3 |=580

因为A1∩A2∩A3为aa ，bb ，cc 图象出现的排列集合，当我们将aa 与a ，bb 与b ，cc 与c 看作不同的三对元素进行排列时，在aa 与a 相遇而成aaa 图象，bb 与b 相遇而成bbb 图象，cc 与c 相遇而成ccc 图象时会产生重复计数。 当aaa ，bbb ，ccc 图象恰出现一个时，重复因子为2

当aaa ，bbb ，ccc 图象恰出现两个时，重复因子为4

当aaa ，bbb ，ccc 图象恰同时出现时，重复因子为8

设 q1(x)；排列x 中有aaa 图象

q2(x)；排列x 中有bbb 图象

q3(x)；排列x 中有ccc 图象

i B ={x |x ∈A1∩A2∩A3∩i q (x)} (1≤i ≤3)

|B1| =|B2|=|B3|=5! |B1∩B2|=|B1∩B3|=|B2∩B3|=4!=24

【第 10 页 共 42 页】 |B1∩B2∩B3|=3!=6

P1=|B1|+|B2|+|B3|=3×120=360

P2=|B1∩B2|＋|B1∩B3|＋|B2∩B3|=3×24=72

P3=|B1∩B2∩B3|=6

q1=P 1－2P2+3P3=360－2×72＋3×6=234

q2=P 2－3P3=72－3×6=54

q3=P3=6

因此 |A1∩A2∩A3| = 6！－（q 1＋3q2＋7q3）=720－(234+3×54+7×6)=282 所以 |1A ∩2A ∩3A | =|Z |-（|A1|+|A2|＋|A3|）+（|A1∩A2|+|A1∩A3|+|A2∩A3|） －|A1∩A2∩A3|

= 1680－3×980＋3×580－282=198

即 相邻两元素不相同的排列数为198

3.21 求出O （0，0）点到（8，4）点的路径数，已知（2，1）到（4，1）的线路，（3，1）到（3，2）的线路被封锁。

【解】：令P （8，4），A （2，1），B （4，1），C （3，1），D （3，2）

P1（x ）：线段AB 在从O 到P 的路径X 上

P2（x ）：线段CD 在从O 到P 的路径X 上

i A ={x |x ∈Z ∩)(x q i } (1≤i ≤2) Z={从O 到P 的路径}

|Z|=???? ??+448=???

? ??412=12349101112??????=495 |A1| = ???? ??+112·???? ??--+-14)14()48(=???? ??13???? ??37=3×123567????=1

|A2| = ???? ??+113·???? ??--+-24)24()38(= ???? ??14???

? ??27=4·1267??=84

【第 11 页 共 42 页】 |A1∩A2| = 0

故此 |1A ∩2A | =|Z|－（|A1|+|A2|）+|A1∩A2|=495－（105+84）+0=306 因此，从O 到P 的路，不过线段AB 和CD 的有306条。

3.22.求满足条件：x 1+x 2+x 3=20

3≤ x 1≤9，0≤ x 2≤8，7≤ x 3≤17

的整数解的数目。

[解].方法一：利用容斥原理二

不定方程 与如下的不定方程 等价：

x 1+x 2+x 3=10

0≤ x 1≤6，0≤ x 2≤8，0≤ x 3≤10

(这可通过作变换?????-==-=7

3

332211x x x ξξξ来实现)。

对应于不定方程 的不受限的不定方程为：

x 1+x 2+x 3=10

x 1≥0，x 2≥0，x 3≥0

设：X={x |x =(x 1,x 2 ,x 3)是不定方程●的解};

A 1={ x |x =(x 1,x 2 ,x 3) 是不定方程●的解且x 1≥6+1=7};

A 2={ x |x =(x 1,x 2 ,x 3) 是不定方程●的解且x 2≥8+1=9};

A 3={ x |x =(x 1,x 2 ,x 3) 是不定方程●的解且x 3≥10+1=11};

因此,根据定理3.6.4.可知，不定方程●的解的数目：

p 0=|X|=???? ??-+101103=???? ??1012=???? ??212=1211

12??=66

A 1对应的不定方程是：

x 1+x 2+x 3=10

x 1≥7，x 2≥0，x 3≥0

??? ??? ???● ????

【第 12 页 共 42 页】 令：?????==-=3

322117

x x x ξξξ (ξ1≥0, ξ2≥0, ξ3≥0)。利用?我们得到：

ξ1+ξ2+ ξ3=( x 1-7)+ x 2+ x 3=( x 1+x 2+x 3)-7=10-7=3

所以不定方程?的解与下列不定方程：

ξ1+ξ2+ ξ3=3

ξ1≥0, ξ2≥0, ξ3≥0

的解一一对应。故根据定理3.6.4.可知，不定方程?的解的数目为：

|A 1|=????

??-+3133=???? ??35

=???? ??25=124

5??=10

同理可得：

|A 2|=????

??---+9101)910(3=????

??13

=3

A 3对应的不定方程是：

x 1+x 2+x 3=10

x 1≥0，x 2≥0，x 3≥11

由于解若满足条件x 1≥0，x 2≥0，x 3≥11，则有

x 1+x 2+x 3≥0+0+11=11>10

故不定方程?没有解，即

|A 2|=0

因此p 1=|A 1|+|A 2|+|A 3|=10+3+0=13

A 1?A 2对应的不定方程是：

x 1+x 2+x 3=10

x 1≥7，x 2≥9，x 3≥0

由于解若满足条件x 1≥7，x 2≥9，x 3≥0，则有

x 1+x 2+x 3≥7+9+0=16>10

故不定方程?没有解，即

|A 1?A 2|=0

同理可得：|A 1?A 3|=0，|A 2?A 3|=0

因此p 2=|A 1?A 2|+|A 1?A 3|+|A 2?A 3|=0+0+0=0

A 1?A 2?A 3对应的不定方程是：

x 1+x 2+x 3=10

x 1≥7，x 2≥9，x 3≥11

由于解若满足条件x 1≥7，x 2≥9，x 3≥11，则有

????' ???? ???? ????

【第 13 页 共 42 页】 x 1+x 2+x 3≥7+9+11=27>10

故不定方程?没有解，即

p 3=| A 1?A 2?A 3|=0

所以，不定方程 、也即不定方程 的解的数目为：

q 0=|321A A A ??|= p 0-p 1+ p 2- p 3=66-13+0-0=53 。

方法二：利用母函数方法

不定方程 对应的母函数是：

(1+x +x 2+x 3+x 4+x 5+x 6)(1+x +x 2+x 3+x 4+x 5+x 6+x 7+x 8)(1+x +x 2+x 3+x 4+x 5+x 6+x 7+x 8+x 9+x 10)

=(1+2x +3x 2+4x 3+5x 4+6x 5+7x 6+7x 7+7x 8+6x 9+5x 10+4x 11+3x 12+2x 13+x 14)

(1+x +x 2+x 3+x 4+x 5+x 6+x 7+x 8+x 9+x 10)

不定方程 的解的数目为上述母函数中x 10的系数：

1?1+2?1+3?1+4?1+5?1+6?1+7?1+7?1+7?1+6?1+5?1

=1+2+3+4+5+6+7+7+7+6+5

=53 。

3.23.求满足下列条件：

x 1+x 2+x 3=40 6≤ x 1≤15，5≤ x 2≤20，10≤ x 3≤25

的整数解的数目。 [解].(仿3.22题)方法一.利用容斥原理二，不定方程 与如下的不定方程 等价：

x 1+x 2+x 3=19 0≤ x 1 ≤9，0≤ x 2 ≤15，0≤ x 3 ≤15 (这可通过作变换?????-=-=-=105633

2211x x x ξξξ来实现)。

对应于不定方程 的不受限的不定方程为：

x 1+x 2+x 3=19 x 1≥0，x 2≥0，x 3≥0

???

???

???●

【第 14 页 共 42 页】 设：X={x |x =(x 1,x 2 ,x 3)是不定方程●的解};

A 1={ x |x =(x 1,x 2 ,x 3) 是不定方程●的解且x 1≥9+1=10};

A 2={ x |x =(x 1,x 2 ,x 3) 是不定方程●的解且x 2≥15+1=16};

A 3={ x |x =(x 1,x 2 ,x 3) 是不定方程●的解且x 3≥15+1=16};

因此,根据定理3.6.4.可知，不定方程●的解的数目：

p 0=|X|=???? ??-+191193=???? ??1921=???

? ??221=122021??=210 A 1对应的不定方程是：

x 1+x 2+x 3=19 x 1≥10，x 2≥0，x 3≥0 令：?????==-=33

221110x x x ξξξ (ξ1≥0, ξ2≥0, ξ3≥0)。利用?我们得到：

ξ1+ξ2+ ξ3=( x 1-10)+ x 2+ x 3=( x 1+x 2+x 3)-10=19-10=9

所以不定方程?的解与下列不定方程：

ξ1+ξ2+ ξ3=9 ξ1≥0, ξ2≥0, ξ3≥0 的解一一对应。故根据定理3.6.4.可知，不定方程?的解的数目为：

|A 1|=????

??-+9193=???? ??911=???? ??211=121011??=55 同理可得：

|A 2|=???? ??---+1619116193)(=???? ??35=???? ??25=1

245??=10 |A 3|=????

??---+1619116193)(=???? ??35=???? ??25=1245??=10因此p 1=|A 1|+|A 2|+|A 3|=55+10+10=75 A 1?A 2对应的不定方程是：

x 1+x 2+x 3=19 x 1≥10，x 2≥16，x 3≥0

由于解若满足条件x 1≥10，x 2≥16，x 3≥0，则有

x 1+x 2+x 3≥10+16+0=26>19

故不定方程?没有解，即

|A 1?A 2|=0

同理可得：|A 1?A 3|=0，|A 2?A 3|=0

因此p 2=|A 1?A 2|+|A 1?A 3|+|A 2?A 3|=0+0+0=0

???

???

???

【第 15 页 共 42 页】 A 1?A 2?A 3对应的不定方程是：

x 1+x 2+x 3=19 x 1≥10，x 2≥16，x 3≥16

由于解若满足条件x 1≥10，x 2≥16，x 3≥16，则有

x 1+x 2+x 3≥10+16+16=42>19

故不定方程?没有解，即

p 3=| A 1?A 2?A 3|=0

所以，不定方程 、也即不定方程 的解的数目为：

q 0=|321A A A ??|= p 0-p 1+ p 2- p 3=210-75+0-0=135 。

方法二：利用母函数方法

不定方程 对应的母函数是：

(1+x +x 2+x 3+x 4+x 5+x 6+x 7+x 8+x 9) (1+x +x 2+x 3+x 4+x 5+x 6+x 7+x 8+x 9+x 10+x 11+x 12+x 13+x 14+x 15)2 2

16101111???? ??----=x x x x 3321610)1()21)(1(x x x x -+--= =(1-x 10-2x 16+2x 26+x 32-x 42

)??????+???? ??+++???? ??+???? ??+???? ?? n x n x x 222423222 (参见第三版习题2.16(P 199)或第二版第二章习题7(P 131))

不定方程 的解的数目为上述母函数中x 19的系数：

1?????

??221-1????? ??211-2????? ??25 =122021??-121011??-2?1

245?? =210-55-20

=135 。

3.2

4.求满足下列条件的整数解的数目：

x 1+x 2+x 3+x 4=20 1≤ x 1≤5，0≤ x 2≤7，4≤ x 3≤8，2≤ x 4≤6。

[解].(仿题3.22)方法一：利用容斥原理二，不定方程 与如下的不定方程 等价： x 1+x 2+x 3+x 4=13 0≤ x 1≤4，0≤ x 2≤7，0≤ x 3≤4，0≤ x 4≤4

???

??? ???

【第 16 页 共 42 页】 (这可通过作变换???????-=-==-=2

4

144332211x x x x ξξξξ来实现)。

对应于不定方程 的不受限的不定方程为：

x 1+x 2+x 3+x 4=13 x 1≥0，x 2≥0，x 3≥0，x 4≥0

设：X={x |x =(x 1,x 2 ,x 3,x 4)是不定方程●的解};

A 1={ x | x =(x 1,x 2 ,x 3,x 4)是不定方程●的解且x 1≥4+1=5};

A 2={ x | x =(x 1,x 2 ,x 3,x 4)是不定方程●的解且x 2≥7+1=8};

A 3={ x | x =(x 1,x 2 ,x 3,x 4)是不定方程●的解且x 3≥4+1=5};

A 4={ x | x =(x 1,x 2 ,x 3,x 4)是不定方程●的解且x 4≥4+1=5};

因此,根据定理3.6.4.可知，不定方程●的解的数目： p 0=|X|=???? ??-+131134=???? ??1316=???

? ??316=123141516????=560 A 1对应的不定方程是：

x 1+x 2+x 3+x 4=13 x 1≥5，x 2≥0，x 3≥0，x 4≥0 令：???????===-=4

433

22115x x x x ξξξξ (ξ1≥0, ξ2≥0, ξ3≥0, ξ4≥0)。利用?我们得到： ξ1+ξ2+ ξ3+ξ4=( x 1-5)+ x 2+ x 3+x 4=( x 1+x 2+x 3+x 4)-5=13-5=8

所以不定方程?的解与下列不定方程：

ξ1+ξ2+ξ3+ξ4=8

ξ1≥0, ξ2≥0, ξ3≥0, ξ4≥0 的解一一对应。故根据定理3.6.4.可知，不定方程?的解的数目为：

|A 1|=????

??-+8184=???? ??811=???? ??311=12391011????=165 同理可得：

|A 2|=???? ??---+8131)813(4=???? ??58=???? ??38=1

23678????=56 ???

???

???

【第 17 页 共 42 页】 |A 3|=????

??---+

5131)513(4=????

??811

=????

??311=1239

1011????=165

|A 4|=???? ??---+5131)513(4=???? ??811=???? ??311=1239

1011???

?=165

因此 p 1=|A 1|+|A 2|+|A 3|+|A 4|=165+56+165+165=551

A 1∩A 2对应的不定方程是：

x 1+x

2+x 3+x 4=13

x 1≥5，x 2≥8，x 3≥0，x 4≥0

令：???????==-=-=4

43

3221185

x x x x ξξξξ (ξ

1≥0,

ξ2≥0, ξ3≥0, ξ4≥0)。利用?我们得到：

ξ1+ξ2+ξ3+ξ4=(x 1-5)+(x 2-8)+ x 3+x 4=( x 1+x 2+x 3+x 4)-(5+8)=13-13=0 所以不定方程?的解与下列不定方程：

ξ1+ξ2+ξ3+ξ4=0

ξ1≥0, ξ2≥0, ξ3≥0, ξ4≥0

的解一一对应。故根据定理3.6.4.可知，不定方程?的解的数目为：

|A 1∩A 2| =????

??-

+0104=????

??03

=1

同理可得：|A 1∩A 3| =???? ??-----+55131)5513(4=???? ??36=1234

56???

?=20

|A 1∩A 4| =???? ??-----+55131)5513(4=???? ??36=1234

56????=20

|A 2∩A 3| =????

??-----+58131)5813(4=????

??03

=1

|A 2∩A 4| =????

??

-----+58131)5813(4=????

??03

=1

|A 3∩A 4| =????

??-----+55131

)5513(4=???? ??36=1

2345

6????=20因此 p 2=|A 1∩A 2|+|A 1∩A 3|+|A 1∩A 4|+|A 2∩A 3|+|A 2∩A 4|+|A 3∩A 4|

=1+20+20+1+1+20=63A 1∩A 2∩A 3对应的不定方程是：

??? ???

【第 18 页 共 42 页】 x 1+x 2+x 3+x 4=13 x 1≥5，x 2≥8，x 3≥5，x 4≥0 由于解若满足条件x 1≥5，x 2≥8，x 3≥5，x 4≥0，则有 x 1+x 2+x 3+x 4≥5+8+5+0=18>13

故不定方程?没有解，即 |A 1∩A 2∩A 3| = 0

同理可得：|A 1∩A 2∩A 4| = 0，|A 1∩A 3∩A 4| = 0，|A 2∩A 3∩A 4| = 0

p 3=|A 1∩A 2∩A 3|+|A 1∩A 2∩A 4|+|A 1∩A 3∩A 4|+|A 2∩A 3∩A 4| = 0+0+0+0 = 0 A 1∩A 2∩A 3∩A 4对应的不定方程是：

x 1+x 2+x 3+x 4=13 x 1≥5，x 2≥8，x 3≥5，x 4≥5

由于解若满足条件x 1≥5，x 2≥8，x 3≥5，x 4≥0，则有

x 1+x 2+x 3+x 4≥5+8+5+5=23>13

故不定方程?没有解，即

p 4=| A 1∩A 2∩A 3∩A 4|=0

所以，不定方程 、也即不定方程 的解的数目为：

q 0=|1A ∩2A ∩3A ∩4A | = p 0－p 1+p 2－p 3+p 4=560－551+63－0+0=72。 方法二.利用母函数方法,不定方程 对应的母函数是：

(1+x +x 2+x 3+x 4+x 5+x 6+x 7)(1+x +x 2+x 3+x 4)3 3581111???

? ??----=x x x x 4151058)1()331)(1(x x x x x --+--= =(1-3x 5-x 8+3x 10+3x 13-x 15-3x 18+x 23)???

???+???? ??+++???? ??+???? ??+???? ?? n x n x x 333534332 (参见第三版习题2.16(P 199)或第二版第二章习题7(P 131))

不定方程 的解的数目为上述母函数中x 13的系数：

1?????

??316-3????? ??311-1????? ??38+3????? ??36+3????? ??33 =123141516????-3?12391011????-123678????+3?123456????+3?1 =560-495-56+60+3

=72 。

3.25.试证满足下列条件：x 1+x 2+…+x n =r 0≤ x i ≤k ，i =1,2,…,n

???

???

???

【第 19 页 共 42 页】 的整数解的数目为：∑=-n

i i 0)1(???? ??i n ???? ??--++-11)1(n n i k r 。 [证].方法一.利用容斥原理二，取不定方程：

x 1+x 2+……+x n =r

x i ≥0，i =1,2,…，n

设：X={x |x =(x 1,x 2,?,x n )是不定方程 的解}

令：P i (x ): x =(x 1,x 2,?,x n )是不定方程 的解且满足条件：x i ≥k +1 (i =1,2,…,n )

A i ={x | x ∈X ∧P i (x )} (i =1,2,…,n )

因此,根据定理3.6.4.可知，不定方程 的解的数目为：

p 0=|X|=???? ??-+r r n 1=???? ??--+11n n r =???? ??0n ???

? ??--+11n n r 并且，参考第三版P 238 第3.9节的方法一，做相应的变换，可得：

| A i | =???? ??+--+-+)1(1))1((k r k r n =???? ??--++-11)1(n n k r (1≤ i ≤ n ) p 1=∑=n i 1| A i | =???? ??1n ????

?

?--++-11)1(n n k r | A i ∩A j | =???? ??+--+-+)1(21))1(2(k r k r n =???? ??--++-11)1(2n n k r (1≤ i < j ≤ n ) p 2=∑

?--++-11)1(2n n k r | A i ∩A j ∩A k |=???

? ??--++-11)1(3n n k r (1≤ i < j < k ≤ n ) p 3=

∑<

?--++-11)1(3n n k r ………………………… p n =|A 1∩A 2∩?∩A n |=???? ??--++-11)1(n n k n r =???

? ??n n ???? ??--++-11)1(n n k n r 于是，根据容斥原理二，可知 q 0=|1A ∩2A ∩?∩n A |=p 0－p 1+ p 2－p 3+ ……+n )1(-p n

=???? ??0n ???? ??--+11n n r －???? ??1n ???? ??--++-11)1(n n k r +???? ??2n ???

? ??--++-11)1(2n n k r ???

【第 20 页 共 42 页】 －???? ??3n ????

??--++-11)1(3n n k r +……+n )1(-???? ??n n ???? ?

?--++-11)1(n n k n r =∑=-n i i 0)1(???? ??i n ???? ?

?--++-11)1(n n i k r 即不定方程 的整数解的数目为: ∑=-n i i 0)1(???? ??i n ???? ?

?--++-11)1(n n i k r 。 方法二.利用母函数方法，不定方程 对应的母函数是：

(1+x +x 2+…+x k )n

n k x x ???

? ??--=+111 =[???? ??0n -???? ??1n x k +1+???? ??2n x 2(k +1)+…+(-1)n ????

??n n x n(k +1)]? [???? ??--11n n -???? ??-1n n x +???? ??-+11n n x 2+…+???

? ??--112n n x n +…] (参见第三版习题2.16(P 199)或第二版第二章习题7(P 131))

不定方程 的解的数目为上述母函数中x r 的系数：

???? ??0n ???? ?

?--+11n n r －???? ??1n ???? ??--++-11)1(n n k r +???? ??2n ???? ??--++-11)1(2n n k r －???? ??3n ????

??--++-11)1(3n n k r +……+n )1(-???? ??n n ???? ??--++-11)1(n n k n r =∑=-n i i 0)1(???? ??i n ???? ?

?--++-11)1(n n i k r 。 3.26.试证满足下列条件：x 1+x 2+…+x n =r 1≤ x i ≤k ，i =1,2,…,n

的整数解的数目为：∑=-n i i 0)1(???? ??i n ???

? ??---11n ki r 。

[证].方法一.利用习题3.25的结论，对不定方程 做变换：

???

【第 21 页 共 42 页】 ???????-=-=-=1112211n n x x x ξξξ (于是???????+=+=+=1

112211n n x x x ξξξ

) 则不定方程 转化为题3.25型的不定方程：

ξ1+ξ2+…+ξn =r －n 0≤ ξ1≤ k －1, 0≤ ξ2≤ k －1,…, 0≤ ξn ≤ k －1 不定方程 与不定方程 的解是一一对应的，故不定方程 的整数解的数目就是不定方程 的整数解的数目。

因此,不定方程 的整数解的数目,也即不定方程 的整数解的数目按题3.25为：

∑=-n i i 0)1(???? ??i n ???? ??--++---11)1)1(()(n n i k n r =∑=-n i i 0)1(???? ??i n ???

? ??---11n ki r 。

方法二.利用母函数方法，不定方程 对应的母函数是：

(1+x +x 2+…+x k -1)n

n

k

x x ???? ??--=11 = [???? ??0n －???? ??1n x k +???? ??2n x 2k +…+(-1)n ???

? ??n n x n k ]? [???? ??--11n n +???? ??-1n n x +???? ??-+11n n x 2+…+???

? ??--112n n x n +…] (参见第三版习题2.16(P 199)或第二版第二章习题7(P 131))

不定方程 的解的数目为上述母函数中x r-n 的系数：

???? ??0n ???? ??--+-11n n n r －???

? ??1n ???? ??--+--11n n k n r +???? ??2n ???? ??--+--112n n k n r －???? ??3n ???? ??--+--113n n k n r +…+n )1(-???

? ??n n ???? ??--+--11n n nk n r =???? ??0n ???? ??--11n r －???? ??1n ???? ??---11n k r +???? ??2n ???

? ??---112n k r －???? ??3n ???? ??---113n k r +…+n )1(-???? ??n n ???

? ??---11n nk r =∑=-n i i 0)1(???? ??i n ???

? ??---11n ki r 。 ???

本文来源：https://www.bwwdw.com/article/uf3l.html