最新组合数学习题答案(1-4章全)

第1章 排列与组合

1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：

(a)a?b?5;(b)a?b?5.

[解] (a) a?b?5

将上式分解，得到?a?b??5

??a?b??5a = b–5，a=1，2，?，45时，b＝6，7，?，50。满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，?，50时，b＝0，1，2，?，45。满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) a?b?5

(6?10)?5?11?(45?4)?16?5?11?41?531个点。

1.2 5个女生，7个男生进行排列，

(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？

(c) 两男生A和B之间正好有3个女生的排列是多少？

[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。

（7＋1）!×5!=8!×5!＝40320×120=4838400

(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有C8种选择。将女生插入，有5!种方案。故按乘法原理，有：

7!×C8×5!=33868800(种)方案。

(c) 先从5个女生中选3个女生放入A，B之间，有C5种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有

(7+1)! = 8!

由于A，B可交换，如图

**A***B** 或 **B***A**

故按乘法原理，有：

2×C5×3!×8!=4838400（种）

1.3 m个男生，n个女生，排成一行，其中m，n都是正整数，若

(a) 男生不相邻(m?n+1)； (b) n个女生形成一个整体； (c) 男生A和女生B排在一起； 分别讨论有多少种方案.

[解] (a) 先将n个女生排列，有n!种方法，共有n+1个空隙，选出m个空隙，共有Cn?1种

【第 1 页 共 129 页】

m3355

方法，再插入男生，有m!种方法，按乘法原理，有：

n!×Cn?1×m!＝n!×

m(n?1)!m!(n?1?m)!×m!=

n!(n?1)!(n?1?m)!种方案。

(b) n个女生形成一个整体，看作一个人，与m个男生做重排列，然后，n个女生内部再作排列，按乘法原理，有(m+1)!×n!种方案。

(c) 男生A和女生B排在一起，看作一人，和其余n-1+m-1=n+m-2个人一起，作排列，共有(n+m-2+1)=(n+m-1)!种方法，A，B两人内部交换，故有2×(n+m-1)!种方案。 1.4 26个英文字母进行排列，要求x和y之间有5个字母的排列数.

5[解] 选入26－2＝24个字母中选取5个字母，有C24种方法，5个字母内部排列，有

5!种方案，再将X*****Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X与Y可交换，故按乘法原理，有：

?24?52×C24×5!×20!=2××5!×20!=40×24! ≈ 40×2??24×??5!?19!e??24!24

又因为：ln40+0.5(lg?+lg48)+24(lg24–lge)

≈1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481) =25.39325777

所以，结果为e?1025＝2.473191664×1025

1.5 求3000到8000之间的奇整数的数目，而且没有相同的数字. [解] 3000~8000中各位不同的奇数，分类讨论：

首位3，1×8×7×4（末位不能取3） 首位4，1×8×7×5（末位全取）

首位5，1×8×7×4 首位6，1×8×7×5

首位7，1×8×7×4

从而，由加法原理，得：

8×7×（4＋5＋4＋5＋4）=56×22＝1232个。 1.6 计算

1?1!?2?2!?3?3!???n?n!

n?1[解] 1?1!?2?2!?3?3!???n?n!?(n?1)!?1 (参见p14) (n!?1?1.7 试证

被2n除尽.

[证] (n?1)(n?2)?(2n)?(2n)!n!?(2n)!!(2n?1)!!n!?k?k!)

k?1(n?1)(n?2)?(2n)

?2?n!?(2n?1)!!n!n?2(2n?1)!!

n故能被2整除。

n【第 2 页 共 129 页】

1.8 求10和20的公因数.

[解]因为10=2·5，20=(2·5)=2·5,所以它们的公因数为形如2·5的数，其中0?m?40，0?n?30，故它们的公因数的数目为(40+1)(30+1)=1271。

2

1.9 试证n的正除数的数目是奇数.

[证]当n=1时，因数为10；当n=2时，因数为20，21，22；当n=3时，因数为30，31，32；

l2l2ll2设n?p1lp2?pn?，(p1,p2,?,pn,?均为质数)，则n?p1p2?pn?的正除

12n124030

404040302306030mn

2ln数可表示为

p11p22?pnn?kkk，其中k1,k2,?,kn,?2均为整数，且

0?k1?2l1,0?k2?2l2,?,0?kn?2ln,?，所以n的正除数的个数为

(2l1?1)(2l2?1)?(2ln?1)?，结果是奇数的乘积为奇数。

1.10 证明任一正整数n可惟一地表示成如下形式：

n??ai!,(0?aii?1i?i,i?1)

[证].(1)可表示性：

令M={(am-1,am-2,?,a2,a1):0?ai?i，i=1,2,?,m-1}，显然?M?=m!；

N={0,1,2,?,m!-1}，显然?N?=m!，其中m是大于n的任意整数。

定义函数f : M?N

f(am-1,am-2,?,a2,a1)=am-1(m-1)!+am-2(m-1)!+?+a22!+a11! (*)

显然，0= 0(m-1)!+0(m-1)!+?+0?2!+0?1!

? am-1(m-1)!+am-2(m-1)!+?+a22!+a11!

? (m-1)(m-1)!+(m-2)(m-1)!+?+2?2!+1?1!= m!-1 （见P14） 即0? f(am-1,am-2,?,a2,a1)?m!-1

由于f是用普通乘法和普通加法所定义的，故从而f无歧义。从而有一确定的数K（0?K?m!-1），使K=f(am-1,am-2,?,a2,a1) 为证N中的任一数均可表示成上边(*)的形式，只要证明f是满射函数即可。但由于在两相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f是单射函数即可。

否则，设存在某数K0?N,有(am-1,am-2,?,a2,a1)?(bm-1,bm-2,?,b2,b1)均属于M，使

K0=f(am-1,am-2,?,a2,a1)且K0=f(bm-1,bm-2,?,b2,b1) 由于不相等,故必有某个j(?m-1)，使aj?bj。不妨设这个j是第一个不使相等的，即ai=bi(i?m?1,j?1)，aj?bj且aj?bj，从而由

am-1(m-1)!+am-2(m-1)!+?+a22!+a11!= bm-1(m-1)!+bm-2(m-1)!+?+b22!+b11! 就可有(bj-aj)j!+(bj-1-aj-1)(j-1)!+?+(b2-a2)2!+(b2-a1)1!=0 但是

(bj-aj)j!+(bj-1-aj-1)(j-1)!+?+(b2-a2)2!+(b2-a1)1! ?(bj-aj)j!-[?bj-1-aj-1??(j-1)!+?+?b2-a2??2!+?b2-a1??1!]

?j!-[(j-1)?(j-1)!+?+2?2!+1?1!]=j!-(j!-1)=1 矛盾，这说明f是单射函数。

由于?M?=?N?=m!有限，故f是双射函数，当然是满射函数，从而0到m!-1中的任何一个数都可以表示成上边(*)的形式。故，由n?N，都有(am-1,am-2,?,a2,a1)?M，使得

【第 3 页 共 129 页】

n=am-1(m-1)!+am-2(m-1)!+?+a22!+a11! 这就证明了任何n可表示成以上形式。 (2)唯一性：用证明单射的方法，就可以证明表示法的唯一性(表示方法见P14),留给读者。 1.11 证明nC(n?1,r)?(r?1)C(n,r?1)，并给予组合解释. [证].(参见 P28 (1-8-4))

nC(n?1,r)?n(n?1)!r!(n?r?1)!?n!(r?1)!(n?r?1)!(r?1)?(r?1)C(n,r?1)

组合意义：（等式右边）由n个元素中取出r+1个元素组合（有C(n,r+1)种），再从每个组合中取出1个（有r+1种），全部结果为C(n,r+1)(r+1)。（等式左边）由此所得的全部结果相当于从n个元素中直接取1个元素（有n种），但有重复，其重复数等于剩下的n-1个元素中取r个元素的组合C(n-1,r)，故nC(n-1,r)= (r+1)C(n,r+1)。

n1.12 试证等式：?kC(n,k)?n2n?1

k?1[证].证法一：根据二项式定理，(参见 P29 (1-8-5))

(1+x)n=1+C(n,1)x+C(n,2)x2+?+ xn

两边对x求导，有n(1+x)n-1=C(n,1)+2C(n,2)x+?+ nxn-1

令x=1，即得?kC(n,k)?n2n?1。

k?1n证法二：组合意义：设有n个不同的小球，并有A、B两个合子，A合中恰好放入一个球，B合中可放入任意多个球。有两种放球方法：

(1)（等式左边）先从n个球中选取k个，再从这k个球中任选一个放入A合，剩下的k-1个球全部放入B合中，方案数共为?kC(n,k)；

k?1n(2)（等式右边）先从n个球中任选一个放入A合，剩下的n-1个球每个都有两种可能，要么放入B合，要么不放，方案数共为n2n-1；

显然，两种放球方法等效，两种放球方案数相等，即?kC(n,k)?n2n?1。

k?1n1.13 有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数. [解] 设这n个不同的数为m1?m2?m3???mn。

若假定第一组取k1个数，第二组取k2个数，并且令m=k1+k2(m?2)，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n个数中任选m个数(有C(n,m)种选法)，再从这m个数中从大到小取k1个数作为第一组数(有k1=1,2,?,m-1共m-1种取法)，将其余k2个数作为第二组数，即可。故总方案数为

n?1。 ?(m?1)C(n,m)?(n?2)2?1（参见第3题等式）m?2n1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少

种方案？

[解] 第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种,??。

即方案数为1?3?2?2?1?1=12。

【第 4 页 共 129 页】

1.15 试求从1到1 000 000的整数中，0出现的次数.

[解] (参见P8)从1到1 000 000的整数中，0出现的次数相当于10-99，100-999，1000-9999, 10000-99999,100000-999999,以及1 000 000中的0的个数。 10-99中的零的个数为： 9

?9?9?9?9?9?18?81?81?180 100-999中的零的个数为： 2???十位、个位为零，故对百位的每一种取法，有两个零十位为零个位为零1000-9999中的零的个数为：3?9?有三位为零?2?C3?9?9?C3?9?9?9

??????????????有两位为零有一位为零21 =27+486+2 187 =2 700

10000-99999中的零的个数为：

321 4?9?3?C4?9?9?2?C4?9?9?9?C4?9?9?9?9 ?有四位零???????有三位零???????有二位零???????有一位零 =36+972+8 748+26 244 =36 000

100000-99999中的零的个数为：

有五位零5?9?4?C5?9?9?3?C5?9?9?9?2?C5?9?9?9?9?C5?9?9?9?9?9 ?????????????????????????????????有四位零有三位零有二位零有一位零4321=45+1 620+21 870+131 220+295 245=450 000 1，000，000中的0的个数为： 6 故1到1，000，000的整数中0的个数为：9+180+2 700+36 000+450 000+6=488 895。 1.16 n个完全一样的球放到r个有标志的盒（n?r）中，无一空盒，试问有多少种方案？ [解]

1.17 n和r都是正整数，而且r?n，试证下列等式：

(a)Pr?nPr?1nnn?1n(b)Pr?(n?r?1)Pr?1(c)Pr?(d)Pr(e)Prn?1nnn?rnPrn?1,r?nn

?Pr?rPr?1?r!?r(Pr?1?Pr?1???Pr?1)nn?1rn?1[解] (a) 方法一

Pr?nn!(n?r)!?n(n?1)?(n?r?1)?n(n?1)?[n?1?(r?1)?1](n?1)!?nPr?1n?1

?n[(n?1)?(r?1)?1]!方法二（组合意义）

等式左边：从n个元素种取r个元素做排列有Pr种，就是等式左边；

【第 5 页 共 129 页】

n

等式右边：先从n个元素中拿出一个元素排在首位，有n种方法，然后再从剩下的n-1

11个元素中取r-1个元素做后面r-1位的排列,有Prn??种方法,按乘法原理,共有nPrn??种方法。 11(b) 方法一

Pr?nn!(n?r)!?n(n?1)?(n?r?2)(n?r?1)?(n?r?1)?n(n?1)?[n?(r?1)?1]?(n?r?1)n![n?(r?1)]!?(n?r?1)Pr?1n

方法二（组合意义法）

等式左边：从n个元素中取r个元素做r位排列，有Prn种方案。

等式右边：先从n个元素中取r-1个元素做r-1位排列，有Prn?1种方法；再从剩下的n-r+1个元素中取1个元素，共有n-r+1种选法，按乘法原理，共有(n?r?1)Prn?1

(c) 方法一

Pr???nn!(n?r)!nn?rnn?r?n(n?1)?(n?r?2)(n?r?1)(n?1)?(n?r?2)(n?r?2)(n?r?1)(n?r)(n?1)?(n?r?1)[(n?1)?r?1]?n(n?1)!?nn?rPrn?1

n?r[(n?1)?r]!方法二：（组合意义法）

等式左边：从n个元素中取r个元素做r位排列，其方案数为Prn；

等式右边：从n个元素中先取出一个元素放在第一位，有n种方法，再从剩下的n-1个元素种取出r个元素放在第2位，?，第r位，第r+1位，有Prn?1种方法，这样就多了一

nPrn?1位，故应除去第r+1位的选取方法，共有n-r种选法，故总方案为

(d) 方法一

Prn?1n?r。

?(n?1)!(n?1?r)!?(n?1)n?(n?r?2)?[(n?r?1)?r]n?(n?r?2)?n?(n?r?2)(n?r?1)?r?n?[n?(r?1)?1]?n!(n?r)!?r?n!(n?r?1)!?Pr?rPr?1nn

方法二：（组合意义）

等式左边：从n+1个不同的元素中取r个元素进行r位排列。其方案为Prn?1；

等式右边：(a) 不取某特定元素b，则r个元素需从剩下的n个元素中取，然后做r位

【第 6 页 共 129 页】

排列，共有Prn种方案。

(b) 取定某特定元素b，则其余r-1个元素需从剩下的n个元素中取，先做r-1位排列，共有Prn?1种方法，再将特定元素b插入这r-1个元素形成的r个空隙中，有r种方法，故按乘法原理，共有rPrn种方案。

(e) 方法一 （根据(d)可得）

Prn??Pr?rPr?1?Pr?Pr?Prn?1n?2n?2nn?rPr?1?rPr?1?rPr?1?rPr?1?rPr?1?rPr?1?rPr?1?rPr?1rr?1n?1nn?2n?1nn?2n?1nn?1n????Pr?rPr?1?rPr?1???rPr?1?rPr?1?r!?r(Pr?1?Pr?1???Pr?1?Pr?1)?r!?r(Pr?1?Pr?1???Pr?1?Pr?1nn?1r?1rrr?1n?1nr

方法二：组合意义（同样根据d）

等式左边：从n+1个不同元素取r个元素做r位排列，其方案数为：Prn?1 等式右边：设b1,b2,b3,?,bn?1?r是n-r+1个特定元素。

(a) 不取特定元素b1,b2,b3,?,bn?1?r，剩下的r个元素做全排列，有Prr=r!种方案。 (b)(1)：取特定元素b1，但不取特定元素b2,b3,?,bn?1?r，于是先在剩下的r个元素中取r-1个元素做排列，有Pr?1种方法，然后将b1插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有rPr?1种方案。

(2)：取特定元素b1，但不取特定元素b3,?,bn?1?r，于是先在剩下的r+1个元素中取r-1个元素做排列，有Pr?1种方法，然后，将b1插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有rPr?1种方案。

??

(n-r)：取特定元素b1，但不取特定元素bn?1?r，于是先在剩下的n-1个元素中取r-1个元素做排列，有Pr?1种方法，然后，将b1插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有rPr?1种方案。

【第 7 页 共 129 页】

n?1n?1r?1r?1rr

(n-r+1）：取特定元素b1，先在剩下的n个元素中取r-1个元素做排列，有Prn?1种方法，然后，将b1插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有rPrn?1种方案。

最后，按加法原理，共有：

r!?r(Pr?1?Pr?1???Pr?1)

nn?1n1.18 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？

[解] 先将5个球进行全排列，有5!种方法，再将三个空格插入5个球的6个空隙中，有

C36种方法，然后将这些元素的排列一对一的放入8个盒子中，即完成了每盒最多一球，空盒不相邻的放球要求，总方案有：C36?5!?2400（种）

1.19 n+m位由m个0，n个1组成符号串，其中n?m+1，试问不存在两个1相邻的符号串的数目。

[解]：先将m个0排成一排，再将n个1插入m个0的m+1个空隙（因为n?m+1,这可实现）,就得到了无相邻的n+m位0-1符号串，其方案数为??n??m?1???。 ?1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位.试问有多少种方案？ [解] 甲单位选4人，则乙单位只能选3人；另外男同志要5人，而乙单位的3人全是男同志，还差2名男同志，故甲单位的男同志人数应至少是2，至多为4。

?10??4??15??10??10??4??15??10??10??4??15??10???2????2????3????0?????3????1????2????1?????4????0????1????2???768600 ????????????????????????1.21 一个盒子里有7个无区别的白球，5个无区别的黑球. 每次从中随机取走一个球，已知前面取走6个，其中3个是白的. 试问取第6个球是白球的概率. [解] 已知前面取走6个球，有3个白球，则有3个黑球。

故总的取球方案是?????7?6?5?5?4?3；

?3??5?第六个球是白球的方案是??2???7?6?5?5?4?3

???6??5???2???7?6?5?5?4?31????0.5 因此取出第6个球是白球的概率P?2?6????7?6?5?5?4?3?3???1.22 求下图中从0到P的路径数：

(a) 路径必须过A点； (b) 路径必须过道路AB；

【第 8 页 共 129 页】

(c) 路径必须过A和C；

(d) 道路AB封锁（但A，B两点开放）.

[解] O(0,0), A(3,2), B(4,2), P(8,5), C(6,3)

(a) 路分为两段：先从O到A，再从A到P，则有：

?3?2??8?3?5?2??5??8?????2???5?2????2????3???560????????

(b)路分为三段：先从O到A，再从A到B；再从A到B；然后从B到P；

?3?2??8?4?5?2??5??7??????1??2??5?2????2????3???350????????

(c) 路分为三段：先从O到A；再从A到C；然后从C到P；

?3?2??6?3?3?2??8?6?5?3??5??4??4??????2????3?2????5?3????2????1????2???240????????????

(d) (采用排除法)

从O到P的满足不过AB的路 ＝ 从O到P的路－从O到P经过AB的路，因此：

?8?5??3?2??8?4?5?2??13???1???????????350?1287?350?937 525?2???????5?1.23 另s={1,2,3…,n+1},n?2

T?{(x,y,z)|x,y,z?s,x?z,y?z}，试证：

?n?1??n?1?2k??2?2?????

23k?1????n [证]

T?n?1z?1z?1n?12nT????1???z?1?z?1y?1x?1z?12??kk?132

32而?k?1??k?3k?3k?1，故k3?13??k?1?3?k?3k?1

?【第 9 页 共 129 页】

nn1?n3?1?333k?(k?1)?k?3k?n?n?1?1?n?n?1???????????332?k?1k?1k?1?k?1?2n?n??13(n?1)?13?n?1?3?12n?n?1??(n?1)3?12n(n?1)?13(n?1)?n(n?1)?3?n?1?1??n?1?1?122???(n?1)(n?1)?n????(n?1)(n?2n?1?3n?1)????3??2?3?2??3?n?1?1?n?1??n?1?(n?1)n(n?1)?n?1?2???(n?1)(n?n)??2???2???????3?2?1?2?3?2??2??3?

1.24 A={(a, b)|a, b∈Z, 0?a?9,0?b?5}

(a) 求x-y平面上以A作顶点的长方形的数目. (b) 求x-y平面上以A作顶点的正方形数目.

[解] (a) 先选定横作标，再选定纵坐标，其方案数为：

?10??6?10?96?5???675?2????2???22????

(b) 求x－y平面上以A作顶点的正方形数目。

按边长分类：

边长为1的正方形：9×5＝45

边长为2的正方形：(9-1)×(5-1)=32

边长为3的正方形：(9-2)×(5-2)=21 边长为4的正方形：(9-3)×(5-3)=12 边长为5的正方形：(9-4)×(5-1)=5

故总的以x－y平面上A点作顶点的正方形的数目，按加法原理可得数目为115. 1.25 平面上有15个点P1, P2, … , P15，其中P1, P2, P3, P4, P5共线，此外不存在3点共线的.

(a) 求至少过15个点中两点的直线的数目. (b) 求由15个点中3点组成的三角形的数目. [解] (a) (采用排除法)

至少过15个点中两点的直线数目＝在15个点中任选2个点将有一条直线－从P1～P5中选2点构成直线＋P1～P5所在的直线l

?15??5????2?????2???1?????96

(b) (采用排除法)

由15个点中3点组成的三角形的数目＝任在15个点中取3点构成三角形的数目－在5个点P1～P5中取3点构成的“三角形”的数目

?15??5????3?????3???????445

【第 10 页 共 129 页】

在{r+1+k+1, ?,n+r+1}这[(n+r+1)-(r+1+k)]=n-k个数中取，故有???n?k??r?k??n?k??n?k?。根据乘????????n?m??m?k??n?k??r?k?法原理，当ir+1=r+1+k时，这样的组合数为?。根据加法?m?k???1???k?????m?k????k??????????原理，对k=0,1,2,?,m作和，就有

?n??r???m????0????????n?1??r?1???m?1????1????????n?2??r?2??n?m??r?m??n?r?1???????????m?2??2??0????m??????m??????????。

注：参见《 Combinatorial Problems and Exercise》 by L.Lovasz 0143.7 L896c

P18-42 (i) P96 P172

(i)The number of those(n+r+1-m)-tuples of{1,2,?,n+r+1}Whose (r?1)stelement is r+k+1is

?r?k??n?k?. Summing for k=0,1,2,?,m,we ??k????m?k??????get the result.

组合意义二：（格路方法）

等式左端：从点A(-r-1,0)到点C(-1,k)(k=0,1,2,?,m)直接经过点D(0,k)再到点B(n-m,m)的路径数(参见本题图1)；

等式右端：从点A(-r-1,0)到点B(n-m,m)的路径数。

C (-1, k) D(0, k) A (-r-1, 0) O (0, 0) 第15题图1 ?r??r?1??r?2??n??n?1?1.38 给出????????????????的组合意义.

rrrrr?1??????????[证].组合意义一：

等式右端是从n+r+1个元素a1,a2,?,an?1中取出r+1个作不允许重复的组合，结果不外乎有以下几种情况(参见P25等式3的组合意义)：

(1) r+1个元素的组合中含有a1的，相当于从n个元素a2,a3,?,an?1中取r个组合，其组合数为?（即A）。 ????r??n? (2)r+1个元素的组合中不含有a1，但又含有元素a2的。即一个(r-1)-第16题图1

组合。依a1来分，不外乎含a1和不含a1；不含a1的又依a2分，不外乎含a2和不含a2。不含a1而含a2的组合，相当于从n-1个元素a2,a3,?,an?1中取r个元素的组合，然后加上a2【第 16 页 共 129 页】

而成，其组合数为???n?1??即A1?A2。 ??r???(3)r+1个元素的组合中不含a1和a2，但含有元素a3的。即不含a1,a2的依a3来分，不外乎含a3和不含a3。不含a1,a2而含a3的组合，相当于从n-2个元素a4,?,an?1中取出r

?n?2?个元素的组合，然后再加上a3而成，其组合数为??r??即A1?A2?A3。

????取出的r+1个组合元素中不含a1,a2,a3,?,an?r?1，但含有元素an?r的。即不含又依an?r来分，不外乎含有an?r和不含有an?r。不含a1,a2,?,an?r?1a1,a2,a3,?,an?r?1的，

而含an?r的组合，相当于从n-(n-r-1)=r+1个元素an?r,an?r?1,?,an?1中取出r个元素的组合而加上an?r而成，其组合数为???r?1?。 ??(即A1?A2??An?r?1?An?r)r???r?1??r??????r?? r?1????(4)由an?r?1,an?r?2,?,an?1组成的(r+1)-组合的组合数为??(即A1?A2???An?r)。而且

A1?(A1?A2)?(A1?A2?A3)???(A1?A2???An?r?1?An?r)?(A1?A2???An?r?1?An?r)??(即全集)

组合意义二：

等式右端：从n+1个不同元素a1,a2,?,an,an+1,中任选r+1个元素的组合方案数； 等式左端：从n+1个不同元素a1,a2,?,an,an+1,中选取r+1个元素，一定选元素ar+k+1(k=0,1,2,?,n-r)，但是不选元素ar+k+2,?,an,an+1的组合方案数。 1.39 证明

m??m??m??m??m?1??m??m?n?n??????????????????2?? 0n1n?1n0?????????????n?[证].借助P28等式4，可知：???m??m?????n???0?????m??m?r??m??n??????? (n?r) (r=0,1,2,?,n) ??????????r??n?r??n??r??m??n??m??n??????????n??1??n????n?? ????????从而有???m??m?1??m??m?n??m??n??????????1??n?1??n????0?????n????0???????????????m??m???n??n??n??n????????????????2???n??0??1??n??n??(用了P29等式5)

????????????【第 17 页 共 129 页】

组合意义一：

等式右端可看作从m个元素中取出n个元素进行组合。然后对这取出的n个元素进行染色（红，白）的所有方案，它为???m?n?2； ??n??m?），全部染以红色。再从剩??k??等式左端可看作先从m个元素中取出k个元素（个数为??下的(m-k)个元素中取出(n-k)个元素（个数为???m?k?），全部染以白色。根据乘法原理，从??n?k???m??m?k?，????n?k??k????m个元素中取出n个元素，k个染上红色，(n-k)个染上白色的方案数为??k=0,1,2,?,n；

而从m个元素中取出n个元素染以红白两色的方案可分解成有0个，1个，?，n个染以红色的总和。故根据加法原理，17题成立。

组合意义二：

等式右端：将从m个不同的小球中任意选出的n个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数；

等式左端：先从m个球中任选k个球放入第一个合子里(k=0,1,2,?,n)，再从剩下的m-k个球中任选n-k个球放入第二个合子里，然后对k从0到n求和，就得到了所有可能的放球方案数。

1.40 从n个人中选r个围成一个圆圈，问有多少种不同的方案？

?a1,a2,?,ar?1,ar??a2,a3,?ar,a1[解].每一个r个人围成的圈（圆排列）a1,a2,?,ar?1,ar?(线排列)?

????????a,a,?a,ar?2r?1?r1即每一个r圈相当于r个r排列。故不同的方案数为N?1rP(n,r)?1n!r(n?r)!

若不计顺逆方向，则为N?12rP(n,r)?12r(n?r)!?n!。

1.41 分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法. [解].（略）

1.42 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法.

(b) 写出按照邻位对换法由给定排列生成其下一个排列的算法. [解].（略）

1.43 对于给定的正整数n，证明，当

【第 18 页 共 129 页】

n?1?n?1或，若n是奇数??22k??时，C(n,k)的最大值.

n?，若n是偶数??2[证] 取C(n,k)与C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)/k。 当k?n/2时，(n-k+1)/k?1，即C(n,k)?C(n,k-1)；

当k?n/2时，(n-k+1)/k?1，即C(n,k)?C(n,k-1)；

因此，得到当k=n/2或最接近n/2时，C(n,k)取得最大值。 1.44 (a) 用组合方法证明

(n)!(n!)n?12(2n)!2n和

(3n)!2?3nn都是整数.

(b) 证明是整数.

[证] (a)考虑2n个不同的球放入n个不同的合子里，每合两个的方案数。这个方案数应该是整数。

对2n个球进行排列的方案数为(2n)!。而把2个球放入同一个合子里不计顺序，重复因子是2。n个合子内部的排列共重复计算了2n次，故总的重复因子是2n。因此，把2n个不同的球放入n个不同的合子里，每合两个的方案数是

(2n)!2n。所以，

(2n)!2n是整数。

同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。

对3n个球进行排列的方案数为(3n)!。而把3个球放入同一个合子里不计顺序，重复因子是3!=2?3。n个合子内部的排列共重复计算了2n?3n次，故总的重复因子是2n?3n。因此，把3n个不同的球放入n个不同的合子里，每合3个的方案数是数。

(b)考虑n2个不同的球放入n个相同的合子里，每合n个的方案数。这个方案数应该是整数。

对n2个球进行排列的方案数为(n2)!。而把n个球放入同一个合子里不计顺序，重复因子是n!。n个合子内部的排列共重复计算了(n!)次，故重复因子是(n!)。另外，由于n个合子相同，放入不同的合子是没有区别的，其重复因子是n!。故此，总的重复因子是(n!)n+1。因此，把n个不同的球放入n个相同的合子里，每合n个的方案数是是整数。

1.45 (a) 在2n个球中，有n个相同. 求从这2n个球中选取n个的方案数.

(b) 在3n+1个球中，有n个相同. 求从这3n+1个球中选取n个的方案数.

[解] (a)相当于从n个不同的小球中取出m个小球(0?m?n),再从n个相同的小球中取出n-m个小球，m=0,1,2,?,n的方案数。

根据加法原理，这个方案数应该是：C(n,0)+ C(n,1)+?+ C(n,n)=2n。

同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。

(b)相当于从2n+1个不同的小球中取出m个小球(0?m?n),再从n个相同的小球中取出

【第 19 页 共 129 页】

2

n

n

(3n)!2?3nn。所以，

(3n)!2?3nn是整

(n)!(n!)n?12。所以，(n)!n?12(n!)

n-m个小球，m=0,1,2,?,n的方案数。

根据加法原理，这个方案数应该是：C(2n+1,0)+ C(2n+1,1)+?+ C(2n+1,n)。 1.46 证明在由字母表{0, 1, 2}生成的长度为n的字符串中

(a) 0出现偶数次的字符串有

3n?12个；

n?n?n?n?n?2?n?n?q3?1?n??????2?,其中q?2?? (b) ??2???22?2??0??2??q?[证] (a)方法一：采用（串值）数学归纳法

［基始］当n=1时，0出现偶数次，长度为1的字符串有长度为1的字符串）。所证结论成立；

［归纳假设］当n=m(1?m?k)时，假设所证结论成立。即，0出现偶数次，长度为m的字符串有

3m3?121=2个（即1和2两个

?12个；

［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分：

(1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，按乘法原理，由归纳假设，此种字符串有

3?12k?2=3+1个；

k

(2)给0出现奇数次，长度为k的字符串后面再增加一位是0的数，因此，按乘法原理，

k?k3k?1?3?1?由归纳假设，此种字符串有??3?2??1=2个；

??所以，按加法原理，0出现偶数次，长度为k+1的字符串共有 (3+1)+

k

3?12k=

3k?1?12个。所证结论成立；归纳完毕。

方法二：采用指数型母函数方法

设：an—0出现偶数次，长度为n的字符串的个数，则{an}的指数型母函数

?A(x)??an?0n?2xnn!?x4?(1?xx2!24!?e2x?x66!??)(1?x1!?x22!?x33!??)????e?ee12123x?x?e2x

[(1?3x1!?(3x)2!1!2??(3x)3!23??)?(1?23x1!3!?x322!?x33!??)][(1?1)?(3?1)x(3?1)x2!?(3?1)x??]【第 20 页 共 129 页】

第二章 母函数与递推关系

2.1 求序列{0,1,8,27,??，n3,??}的母函数.

[解]设其母函数为A(x)?0?x?8x?27x????nx???方法一：由于1?x?x????x????2n233n

11?x12两边求导：0?1?2x?3x3????nxn?1????（1?x）

x(1?x)2同乘以x： xB'(x)?x?2x2?3x3????nxn?????

两边求导： B'(x)?xB''(x)?1?22x?32x2????n2xn?1????

1?(1?x)?x?2(1?x)(?1)(1?x)42 ??1?x(1?x)3

两边同乘以x：xB'(x)?x2B''(x)?x?22x2????n2xn????x(1?x)(1?x)3

两边求导： 1?23x?32x2????n3xn?1???

?(1?2x)(1?x)?x(1?x)?3(1?x)(?1)(1?x)46232

?(1?x)3233

(1?2x)(1?x)?3(1?x)x?1?4x?x(1?x)n4两边同乘以x：x?2x?3x????nx????3x(1?4x?x)(1?x)42

即A(x)?x(1?4x?x)(1?x)42

方法二：令n?A??3?n?3??n?2??n?1???????B?C?D ??????3??2??1??n?3??n?2??n?1?则有 0?A? ① ?3???B??2???C??1???D?A?B?C?D　??????

1= A??3???B??2???C??1???D?4A?3B?2C?D ② ???????4??3??2?【第 26 页 共 129 页】

8=A??3???B??2???C??1???D?10A?6B?3C?D ③

?????? 27=A??3???B??2???C??1???D?20A?10B?4C?D ??????1=3A+2B+C ⑤ 8=9A+5B+2C ⑥

27=19A+9B+3C ⑦ 6=3A+B ⑧ 24=10A+3B 6=A

⑨ ⑩

③－①有

⑦－3*⑤ 有

?6??5??4??5??4??3? ④

于是 ②－①有

于是 ⑥－2*⑤ 有 于是有⑨－3*⑧有 将⑩代入⑧有 将⑩，⑾代入⑤有 ?A?6??B??12故解为：?

?C?7?D??1?B=6-3A=6-3*6=-12 ⑾

C=1-3A-2B=1-3*6-2*(-12)=7

将⑩，⑾，⑿代入⑨有D=-A-B-C=-6-(-12)-7=-1

于是有n?6??3?n?3??n?2??n?1???????12?7?1 ??????3??3??1??n故此 母函数 A(x)??n3xn?0

?n?3??n?2??n?1?n?????[6??12??7??1]x??????n?0?3??2??1??????n?3?n?n?2?n?n?1?nn??????6??x?12?x?7?x??x?3??2??1?n?0n?0n?0n?0??????? ?6?1(1?x)4?121(1?x)43?721(1?x)23?11?x

6?12(1?x)?7(1?x)?(1?x)(1?x)x(x?4x?1)(1?x)42??3??4?2.2 已知序列{??3??,??3??,...????????n?3??,...},求母函数 3???n?3?n??3??x?... ???3??3??A(x)?[解]设其母函数为?3?????4??x?...?????【第 27 页 共 129 页】

则A(x)?1(1?x)3?1?1(1?x)4

2.3 已知母函数G(x)?3?78x1?3x?54x2,求序列{an}

［解］由于G(x)?3?78x1?3x?54x2?3?78x(1?6x)(1?9x)?A1?6x?B1?9x

则有A(1?9x)?B(1?6x)?(A?B)?(?9A?6B)x?3?78x A?B?3....①?于是有?

??9A?6B?78.....②由②－6*①有 故此 将④代入①有 从而有??A??4?B?7-15A=60 ③ A=-4 ④ B=3-A=3-(-4)=7

471?9xn故此G(x)??1?6x??

?n??4?(?6x)?7?(9x)n?0?n?0n

nn??[7?9n?0?(?1)n?14?6]xnn?1n故此：an?7?9?(?1)?4?6

2.4 已知母函数

3?78x1?3x?54x2,求对应的序列{an}.

［解］由于G(x)?3?9x1?x?56x2?3?9x(1?7x)(1?8x)?A1?7x?B1?8x

则有A(1?8x)?B(1?7x)?(A?B)?(?8A?7B)?3?9x

?A?2?B?1?于是有?,故此G(x)?21?7x?n?11?8x

?n?n?2?(?7x)?n?0?(8x)n?0n??[2?(?1)n?0n?7?8]x?nnn?[8n?0n?(?1)?2?7]x

nnn故

an?8?(?1)?2?7

n2.5 设Gn?F2n,其中Fn是第n个Fibonacci数。证明：

【第 28 页 共 129 页】

Gn?3Gn?1?Gn?2?0,n?2,3,4...求{G0,G1,G2,..}的母函数

[证]Gn?3Gn?1?Gn?2?F2n?3F2(n?1)?F2(n?2)?F2n?3F2n?2?F2n?4?(F2(n?1)?F2n?2)?3F2n?2?F2n?4

?F2(n?1)?2F2n?2?F2n?4?(F2n?2?F2n?3)?2F2n?2?F2n?4??F2n?2?F2n?3?F2n?4??F2n?2?F2n?2?02

设G(x)?G0?G1x?G2x?......x:G2?3G1?G0?0x:G3?3G2?G1?0x:G4?3G3?G2?0.....?G0?0??G1?F2?1.?G?F?34?2(G(x)?G0?G1x)?3x(G(x)?G0)?xG(x)?0G(x)?(x?3x?1)?x?0G(x)?xx?3x?13?25,??3?25,???1

222234

解其根为?? 故G(x)?x(1??x)(1??x)?A1??x?B1??x

A(1??x)?B(1??x)?x

?A?B?0....① ??A??B??1....②?1?A??????有?

1?B???????【第 29 页 共 129 页】

于是有 G(x)?1???1??x?(1?11??xn)

?1?nn

?????(??x?n?0??n?0nnx)n??n?01??

(???)xn

即 Gn?15151???3?21?2(???)

nn?[(5)?(2nn3?21?25)]2nn

?[(5)?(5)]

?F2n2.6 求序列{1,0,2,0,3,0,4,0,??}的母函数

[解] 令G(x)?1?2x2?3x4?4x6?......?nx2(n?1)?...... ?x2G(x)?x2?2x4?3x6?.......?(n?1)x2(n?1)?nx2n?......

而 (1-x)2G(x)?1?x2?x4?x6?.......?x2(n?1)?x2n?......

?11?x2

故此G(x)?1(1?x)222

2.7 设G(x)?1?2x?3x?4x?......?n?1x

求(1?x)G,(1?x)G.

1(1?x)22222462n?......

[解]根据题2.6可知G?

从而(1?x)G?21(1?x)22

并且(1?x)G?1

22.8 求下列序列的母函数： (a)1,0,1,0,1,0,?? (b)0,-1,0,-1,0,-1,??

【第 30 页 共 129 页】

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