第一章：排列与组合

第1章 排列与组合

经过勘误和调整，已经消除了全部的文字错误，不过仍有以下几个题目暂时没有找到解答：

1.8 1.9 1.16

1.41（答案略） 1.42（答案略）

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=0时，b＝5，6，7，…,50。满足a=b-5的点共50-4=46个点. a = b+5，a=5时，b＝0，1，2，…,45。满足a=b+5的点共45-0+1=46个点. 所以，共计2?46?92个点. (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中选5个空隙，有C8种选择。将女生插入，有5!种方案。故按乘法原理，有： 57!×C8×5!=33868800(种)方案。

3(c) 先从5个女生中选3个女生放入A，B之间，有C5种方案，在让3个女生

排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有 (7+1)! = 8!

由于A，B可交换，如图

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

故按乘法原理，有：

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

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

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

第 1 页 共 116 页

第一章：排列与组合

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

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

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

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

m!(n?1?m)!(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个字母的排列数.

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

方案，再将X*****Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种

方案，又因为X与Y可交换，故按乘法原理，有：

2×C524×5!×20!=2×

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

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

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

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!

252524!?24?

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

24

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

1.7 试证

被2n除尽.

?k?k!)

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

(2n)!(2n)!!(2n?1)!!2n?n!?(2n?1)!!???2n(2n?1)!! [证] (n?1)(n?2)?(2n)?n!n!n!n故能被2整除。

1.8 求1040和2030的公因数. [解]

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

第 2 页 共 116 页

第一章：排列与组合

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

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

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，使得

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))

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

r!(n?r?1)!(r?1)!(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)。

第 3 页 共 116 页