第一章课后习题答案
1、5个女生，7个男生进行排列，
(a) 若女生在一起有多少种不同的排列？
(b) 女生两两不相邻有多少种不同的排列？
(c) 两男生A和B之间正好有3个女生的排列是多少？
解：(a) 若女生在一起，可将5个女生看作一个整体参与排列，有8!种方式， 然后5个女生再进行排列，有5!种方式， 根据乘法法则，共有8!5!种方式。
(b) 若女生两两不相邻，可将7个男生进行排列，有7!种方式，
考虑到两个男生之间的6个位置和两头的2个位置，每个位置安排一个女生均符合题意， 故从中选出5个位置，然后5个女生再进行排列，按顺序安排到这5个位置， 有C(8, 5)5!种方式，根据乘法法则，共有7!C(8, 5)5!=7!P(8, 5)种方式。 (c) 若两男生A和B之间正好有3个女生，可以按照顺序操作如下：
首先将女生分为两组，一组3人，一组2人，有C(5, 3)种方式；
将男生A和B看作一个整体，加上其他5个男生，2人一组的女生进行排列，有8!种方式； 将3人一组的女生安排到男生A和B之间进行排列，有3!种方式； 男生A和B进行排列，有2!种方式。 根据乘法法则，所求的排列方式为
8!C(5, 3)3!2!=8!P(5, 3)2!
2、求3000到8000之间的奇整数的数目，而且没有相同的数字。
解：设介于3000到8000之间的奇整数表示为abcd，则a{3, 4, 5, 6, 7}, d{1, 3, 5, 7, 9}， 对a进行分类如下：
(1) 若a{3, 5, 7}，则d有4种选取方式，bc有P(8, 2)种方式，根据乘法法则，此类数字有34P(8, 2)=672个
(2) 若a{4, 6}，则d有5种选取方式，bc仍有P(8, 2)种方式，根据乘法法则，此类数字有25P(8, 2)=560个
根据加法法则，3000到8000之间数字不同的奇整数的数目为
672+560=1232个
3、证明nC(n-1, r)=(r+1)C(n, r+1)，并给出组合解释。
证明：等式左端=nC(n-1, r)
=n(n-1)!/[r!(n-r-1)!] =n!/[r!(n-r-1)!]
=n!(r+1)/[(r+1)!(n-r-1)!] =(r+1)C(n, r+1)
=等式右端
得证。
组合意义：从n个不同元素中取r+1个元素，并放到A和B两个盒子中，要求A中放一个元素，B中放r个元素。可以有两种方法：
一是先从n个不同元素中取1个元素，放到A中，再从剩下的n-1个不同元素中取r个元素，放到B中。根据乘法法则，方式数为nC(n-1, r)。
另一种方法是，先从n个不同元素中取r+1个元素，放到B中，再从B的r+1个不同元素中取1个元素，放到A中。根据乘法法则，方式数为(r+1)C(n, r+1)。 显然两种取法的方式数是一样的。
4、甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志。从中产生一个7人代表团，要求甲单位占4人，而且7人中有5个男同志。问有多少方案？
解：我们首先根据选出7人中的甲单位的4人的组成进行分类，再分析乙单位的3人的组成： 如甲单位的4人均为男同志，乙单位的3人须包括1个男同志，2个女同志，其方案数为
C(10, 4)C(15, 1)C(10, 2)
如甲单位的4人包括3个男同志，1个女同志，乙单位的3人须包括2个男同志，1个女同志，其方案数为
C(10, 3)C(4, 1)C(15, 2)C(10, 1)
如甲单位的4人包括2个男同志，2个女同志，乙单位的3人须包括3个男同志，0个女同志，其方案数为
C(10, 2)C(4, 2)C(15, 3)
根据加法法则，总的方案数为
C(10, 4)C(15, 1)C(10, 2)+C(10, 3)C(4, 1)C(15, 2)C(10, 1)+C(10, 2)C(4, 2)C(15, 3)=768600
5、求右图中从O(0, 0)到P(8, 5)的路径数。 (a) 路径必须过A点； (b) 路径必须过AB道路； (c) 路径必须过A点和C点；
(d) 道路AB封锁但A、B点开放。
, 5)
O解：(a) 路径必须过A点，即所求的路径数
可分两部分计算，先计算O→A，再计算A→P，根据乘法法则，所求路径数为
C(3+2, 3)C(8-3+5-2, 8-3)=C(5, 3)C(8, 5)=560
(b) 路径必须过AB道路，可分两部分计算，先计算O→A，再计算B→P，根据乘法法则，所求路径数为
C(3+2, 3)C(8-4+5-2, 8-4)=C(5, 3)C(7, 4)=350 (c) 路径必须过A点和C点，可分三部分计算，先计算O→A，再计算A→C，最后计算C→P，根据乘法法则，所求路径数为
C(3+2, 3)C(6-3+3-2, 6-3)C(8-6+5-3, 8-6)=C(5, 3)C(4, 3)C(4, 2)=240
(d) 道路AB封锁但A、B点开放，可分两部分计算，先计算O→P，再计算必须过AB道路的路径数，前者减去后者，即为所求路径数
C(8+5, 8)-C(3+2, 3)C(8-4+5-2, 8-4)=C(13, 8)-C(5, 3)C(7, 4)=937 6、6位男宾，5位女宾围一圆桌而坐， (a) 女宾不相邻有多少种方案？
(b) 所有女宾在一起有多少种方案？
(c) 一女宾A和两位男宾相邻有多少种方案？
解：(a) 若女宾不相邻，可先安排6位男宾围圆桌而坐，有6!/6=5!种方案；再在6位男宾之间的6个空中，任选5个位置安排5位女宾，有P(6, 5)种方案，根据乘法法则，总的方案数为
5!P(6, 5)=86400 (b) 若所有女宾在一起，可先把5位女宾看作一个整体，和6位男宾围圆桌而坐，有7!/7=6!种方案；再让5位女宾进行全排列，有5!种方案，根据乘法法则，总的方案数为
6!5!=86400 (c) 若一女宾A和两位男宾相邻，可先从6位男宾中任选2位与A看作一个整体，和其他8位男女宾围圆桌而坐，有C(6, 2)9!/9=C(6, 2)8!种方案；再让与A相邻的2位男宾进行全排列，有2!种方案，根据乘法法则，总的方案数为
C(6, 2)8!2!=1209600
7、 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必须在两个x中间（不一定相邻），求不同
的方案数。
解：在任一个排列中，均有11个位置，只需从中选出5个位置，按照x, y, x, y, x的顺序安排这5个元素，再将其他的6个元素进行全排列，即可满足题目要求，根据乘法法则，有C(11, 5)6!=332640种方案
8、 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相
邻，问有多少种排列方案？
9、 (a) 用组合方法证明(2n)!/2n和(3n)!/(2n3n)都是整数。
(b) 证明(n2)!/(n!)n+1是整数。
证明I：(a) 考虑重集B2={a1*2, a2*2, …, an*2}的全排列，全排列数为(2n)!/2n，显然为整数。
nn
同理，重集B3={a1*3, a2*3, …, an*3}的全排列数为(3n)!/(23)，显然为整数。
(b) 考虑重集Bn={a1*n, a2*n, …, an*n}的全排列，全排列个数为(n)!/(n!)，这个数为整数。如对每一个排列进行如下操作，如ij，将所有的ai与aj互换，将得到另一个不同的排列，
2n+1
这样的操作形成一个等价类，每个等价类中包含n!个不同的排列，显然(n)!/(n!)代表重集Bn的全排列中共包含的等价类数目，肯定是整数。
证明II：(a) 设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。
2
n
对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2n次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2n。
n
同理，若有3n个不同的球，放入n个不同盒子，故得(3n)!/(3!)是整数。
(b) 有n2个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。因此得到(n)!/(n!)
10、(a) 在2n个球中，有n个相同，求从这2n个球中选取n个的方案数。
(b) 在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。
解：(a) 在2n个球中，有n个相同，相当于从n个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。不同的方案数为：
C(n, 0)+C(n, 1)+…+C(n, n)=2n种
(b) 在3n+1个球中，有n个相同，相当于从2n+1个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。不同的方案数为：
C(2n+1, 0)+C(2n+1, 1)+…+C(2n+1, n)
=[C(2n+1, 0)+C(2n+1, 1)+…+C(2n+1, n)+C(2n+1, n+1)+…+C(2n+1, 2n+1)]/2 2n+12n
=2/2=2种
2
n+1
是整数。
第一章课后习题答案
1、5个女生，7个男生进行排列，
(a) 若女生在一起有多少种不同的排列？
(b) 女生两两不相邻有多少种不同的排列？
(c) 两男生A和B之间正好有3个女生的排列是多少？
解：(a) 若女生在一起，可将5个女生看作一个整体参与排列，有8!种方式， 然后5个女生再进行排列，有5!种方式， 根据乘法法则，共有8!5!种方式。
(b) 若女生两两不相邻，可将7个男生进行排列，有7!种方式，
考虑到两个男生之间的6个位置和两头的2个位置，每个位置安排一个女生均符合题意， 故从中选出5个位置，然后5个女生再进行排列，按顺序安排到这5个位置， 有C(8, 5)5!种方式，根据乘法法则，共有7!C(8, 5)5!=7!P(8, 5)种方式。 (c) 若两男生A和B之间正好有3个女生，可以按照顺序操作如下：
首先将女生分为两组，一组3人，一组2人，有C(5, 3)种方式；
将男生A和B看作一个整体，加上其他5个男生，2人一组的女生进行排列，有8!种方式； 将3人一组的女生安排到男生A和B之间进行排列，有3!种方式； 男生A和B进行排列，有2!种方式。 根据乘法法则，所求的排列方式为
8!C(5, 3)3!2!=8!P(5, 3)2!
2、求3000到8000之间的奇整数的数目，而且没有相同的数字。
解：设介于3000到8000之间的奇整数表示为abcd，则a{3, 4, 5, 6, 7}, d{1, 3, 5, 7, 9}， 对a进行分类如下：
(1) 若a{3, 5, 7}，则d有4种选取方式，bc有P(8, 2)种方式，根据乘法法则，此类数字有34P(8, 2)=672个
(2) 若a{4, 6}，则d有5种选取方式，bc仍有P(8, 2)种方式，根据乘法法则，此类数字有25P(8, 2)=560个
根据加法法则，3000到8000之间数字不同的奇整数的数目为
672+560=1232个
3、证明nC(n-1, r)=(r+1)C(n, r+1)，并给出组合解释。
证明：等式左端=nC(n-1, r)
=n(n-1)!/[r!(n-r-1)!] =n!/[r!(n-r-1)!]
=n!(r+1)/[(r+1)!(n-r-1)!] =(r+1)C(n, r+1)
=等式右端
得证。
组合意义：从n个不同元素中取r+1个元素，并放到A和B两个盒子中，要求A中放一个元素，B中放r个元素。可以有两种方法：
一是先从n个不同元素中取1个元素，放到A中，再从剩下的n-1个不同元素中取r个元素，放到B中。根据乘法法则，方式数为nC(n-1, r)。
另一种方法是，先从n个不同元素中取r+1个元素，放到B中，再从B的r+1个不同元素中取1个元素，放到A中。根据乘法法则，方式数为(r+1)C(n, r+1)。 显然两种取法的方式数是一样的。
4、甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志。从中产生一个7人代表团，要求甲单位占4人，而且7人中有5个男同志。问有多少方案？
解：我们首先根据选出7人中的甲单位的4人的组成进行分类，再分析乙单位的3人的组成： 如甲单位的4人均为男同志，乙单位的3人须包括1个男同志，2个女同志，其方案数为
C(10, 4)C(15, 1)C(10, 2)
如甲单位的4人包括3个男同志，1个女同志，乙单位的3人须包括2个男同志，1个女同志，其方案数为
C(10, 3)C(4, 1)C(15, 2)C(10, 1)
如甲单位的4人包括2个男同志，2个女同志，乙单位的3人须包括3个男同志，0个女同志，其方案数为
C(10, 2)C(4, 2)C(15, 3)
根据加法法则，总的方案数为
C(10, 4)C(15, 1)C(10, 2)+C(10, 3)C(4, 1)C(15, 2)C(10, 1)+C(10, 2)C(4, 2)C(15, 3)=768600
5、求右图中从O(0, 0)到P(8, 5)的路径数。 (a) 路径必须过A点； (b) 路径必须过AB道路； (c) 路径必须过A点和C点；
(d) 道路AB封锁但A、B点开放。
, 5)
O解：(a) 路径必须过A点，即所求的路径数
可分两部分计算，先计算O→A，再计算A→P，根据乘法法则，所求路径数为
C(3+2, 3)C(8-3+5-2, 8-3)=C(5, 3)C(8, 5)=560
(b) 路径必须过AB道路，可分两部分计算，先计算O→A，再计算B→P，根据乘法法则，所求路径数为
C(3+2, 3)C(8-4+5-2, 8-4)=C(5, 3)C(7, 4)=350 (c) 路径必须过A点和C点，可分三部分计算，先计算O→A，再计算A→C，最后计算C→P，根据乘法法则，所求路径数为
C(3+2, 3)C(6-3+3-2, 6-3)C(8-6+5-3, 8-6)=C(5, 3)C(4, 3)C(4, 2)=240
(d) 道路AB封锁但A、B点开放，可分两部分计算，先计算O→P，再计算必须过AB道路的路径数，前者减去后者，即为所求路径数
C(8+5, 8)-C(3+2, 3)C(8-4+5-2, 8-4)=C(13, 8)-C(5, 3)C(7, 4)=937 6、6位男宾，5位女宾围一圆桌而坐， (a) 女宾不相邻有多少种方案？
(b) 所有女宾在一起有多少种方案？
(c) 一女宾A和两位男宾相邻有多少种方案？
解：(a) 若女宾不相邻，可先安排6位男宾围圆桌而坐，有6!/6=5!种方案；再在6位男宾之间的6个空中，任选5个位置安排5位女宾，有P(6, 5)种方案，根据乘法法则，总的方案数为
5!P(6, 5)=86400 (b) 若所有女宾在一起，可先把5位女宾看作一个整体，和6位男宾围圆桌而坐，有7!/7=6!种方案；再让5位女宾进行全排列，有5!种方案，根据乘法法则，总的方案数为
6!5!=86400 (c) 若一女宾A和两位男宾相邻，可先从6位男宾中任选2位与A看作一个整体，和其他8位男女宾围圆桌而坐，有C(6, 2)9!/9=C(6, 2)8!种方案；再让与A相邻的2位男宾进行全排列，有2!种方案，根据乘法法则，总的方案数为
C(6, 2)8!2!=1209600
7、 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必须在两个x中间（不一定相邻），求不同
的方案数。
解：在任一个排列中，均有11个位置，只需从中选出5个位置，按照x, y, x, y, x的顺序安排这5个元素，再将其他的6个元素进行全排列，即可满足题目要求，根据乘法法则，有C(11, 5)6!=332640种方案
8、 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相
邻，问有多少种排列方案？
9、 (a) 用组合方法证明(2n)!/2n和(3n)!/(2n3n)都是整数。
(b) 证明(n2)!/(n!)n+1是整数。
证明I：(a) 考虑重集B2={a1*2, a2*2, …, an*2}的全排列，全排列数为(2n)!/2n，显然为整数。
nn
同理，重集B3={a1*3, a2*3, …, an*3}的全排列数为(3n)!/(23)，显然为整数。
(b) 考虑重集Bn={a1*n, a2*n, …, an*n}的全排列，全排列个数为(n)!/(n!)，这个数为整数。如对每一个排列进行如下操作，如ij，将所有的ai与aj互换，将得到另一个不同的排列，
2n+1
这样的操作形成一个等价类，每个等价类中包含n!个不同的排列，显然(n)!/(n!)代表重集Bn的全排列中共包含的等价类数目，肯定是整数。
证明II：(a) 设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。
2
n
对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2n次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2n。
n
同理，若有3n个不同的球，放入n个不同盒子，故得(3n)!/(3!)是整数。
(b) 有n2个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n2)!/(n!)n是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。因此得到(n)!/(n!)
10、(a) 在2n个球中，有n个相同，求从这2n个球中选取n个的方案数。
(b) 在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。
解：(a) 在2n个球中，有n个相同，相当于从n个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。不同的方案数为：
C(n, 0)+C(n, 1)+…+C(n, n)=2n种
(b) 在3n+1个球中，有n个相同，相当于从2n+1个不同的小球中分别取出m个小球(0≤m≤n)，再从n个相同的小球中取出n-m个小球。不同的方案数为：
C(2n+1, 0)+C(2n+1, 1)+…+C(2n+1, n)
=[C(2n+1, 0)+C(2n+1, 1)+…+C(2n+1, n)+C(2n+1, n+1)+…+C(2n+1, 2n+1)]/2 2n+12n
=2/2=2种
2
n+1
是整数。