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

第1章 排列与组合

1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;()5.aabbab

[解] (a) 5ba

将上式分解，得到55abab

a = 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) 5ba

(610)511(454)1651141531个点。

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个空隙，有58C种选择。将女生插入，有5!种方案。故按乘法原理，有：

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

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

(7+1)! = 8!

由于A，B可交换，如图

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

故按乘法原理，有：

2×35C×3!×8!=4838400（种）

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

(a) 男生不相邻(m≤n+1)；

(b) n个女生形成一个整体；

(c) 男生A和女生B排在一起；

分别讨论有多少种方案.

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

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

n!×mnC1×m!＝n!×)!1(!)!1(mnmn×m!=)!1()!1(!mnnn种方案。

(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个字母的排列数.

[解] 选入26－2＝24个字母中选取5个字母，有524C种方法，5个字母内部排列，有5!种方案，再将X*****Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X与Y可交换，故按乘法原理，有：

2×524C×5!×20!=2×!19!5!24×5!×20!=40×24! ≈ 40×242×2424e

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

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

=25.39325777

所以，结果为2510e＝2.473191664×2510

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 计算

11!22!33!!nn

[解] 1)!1(!!33!22!11nnn (参见p14) )!1!(11nkkkn

1.7 试证

(1)(2)(2)nnn

被2n除尽.

[证] !!)!12(!)!2(!)!2()2()2)(1(nnnnnnnn!)!12(2!!)!12(!2nnnnnn

故能被n2整除。

1.8 求1040和2030的公因数.

[解]因为1040=240·540，2030=(22·5)30=260·530,所以它们的公因数为形如2m·5n的数，其中0≤m≤40，0≤n≤30，故它们的公因数的数目为(40+1)(30+1)=1271。

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

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

设1212nlllnnppp，(12,,,,nppp均为质数)，则12222212nlllnnppp的正除数可表示为1212nkkknppp，其中12,,,,nkkk均为整数，且112202,02,,02,nnklklkl，所以2n的正除数的个数为12(21)(21)(21)nlll，结果是奇数的乘积为奇数。

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

1!,(0,1)iiinaiaii

[证].(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)1,1(jmi，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，使得

n=am-1(m-1)!+am-2(m-1)!++a22!+a11!

这就证明了任何n可表示成以上形式。

(2)唯一性：用证明单射的方法，就可以证明表示法的唯一性(表示方法见P14),留给读者。

1.11 证明(1,)(1)(,1)nCnrrCnr，并给予组合解释.

[证].(参见 P28 (1-8-4))

)1,()1()1()!1()!1(!)!1(!)!1(),1(rnCrrrnrnrnrnnrnnC

组合意义：（等式右边）由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)。

1.12 试证等式：11(,)2nnkkCnkn

[证].证法一：根据二项式定理，(参见 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，即得112),(nnknknkC。

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

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

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

显然，两种放球方法等效，两种放球方案数相等，即112),(nnknknkC。

1.13 有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数.

[解] 设这n个不同的数为nmmmm321。

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

12)2(),()1(12nnmnmnCm（参见第3题等式）。

1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？

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

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