第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