《组合数学》其次版（姜建国著）

本文格式为Word版，下载可任意编辑——《组合数学》其次版（姜建国著）组合数学（其次版）

习题一（排列与组合）

1．在1到9999之间，有多少个每位上数字全不一致而且由奇数构成的整数？解：该题相当于从“1，3，5，7，9〞五个数字中分别选出1，2，3，4作排列的

方案数；

（1）选1个，即构成1位数，共有P51个；（2）选2个，即构成两位数，共有P52个；（3）选3个，即构成3位数，共有P53个；（4）选4个，即构成4位数，共有P54个；

由加法法则可知，所求的整数共有：P51?P52?P53?P54?205个。

2．比5400小并具有以下性质的正整数有多少个？（1）每位的数字全不同；

（2）每位数字不同且不出现数字2与7；解：（1）比5400小且每位数字全不同的正整数；按正整数的位数可分为以下几种状况：

①一位数，可从1～9中任取一个，共有9个；

②两位数。十位上的数可从1～9中选取，个位数上的数可从其余9个数

字中选取，根据乘法法则，共有9?9?81个；

③三位数。百位上的数可从1～9中选取，剩下的两位数可从其余9个数

中选2个进行排列，根据乘法法则，共有9?P92?648个；

④四位数。又可分三种状况：

?千位上的数从1～4中选取，剩下的三位数从剩下的9个数字中选

3个进行排列，根据乘法法则，共有4?P93?2023个；

?千位上的数取5，百位上的数从1～3中选取，剩下的两位数从剩

下的8个数字中选2个进行排列，共有3?P82?168个；

?千位上的数取5，百位上的数取0，剩下的两位数从剩下的8个数

字中选2个进行排列，共有P82?56个；

9?81?648?2023?168?56?2978个；根据加法法则，满足条件的正整数共有：

（2）比5400小且每位数字不同且不出现数字2与7的正整数；

按正整数的位数可分为以下几种状况：设A?{0,1,3,4,5,6,8,9}①一位数，可从A?{0}中任取一个，共有7个；

第1页（共93页）

组合数学（其次版）

②两位数。十位上的数可从A?{0}中选取，个位数上的数可从A中其余7

个数字中选取，根据乘法法则，共有7?7?49个；

③三位数。百位上的数可从A?{0}中选取，剩下的两位数可从A其余7

个数中选2个进行排列，根据乘法法则，共有7?P72?294个；

④四位数。又可分三种状况：

?千位上的数从1，3，4中选取，剩下的三位数从A中剩下的7个

数字中选3个进行排列，根据乘法法则，共有3?P73?630个；?千位上的数取5，百位上的数从0，1，3中选取，剩下的两位数从

A中剩下的6个数字中选2个进行排列，共有3?P62?90个；

根据加法法则，满足条件的正整数共有：7?49?294?630?90?1070个；

3．一教室有两排，每排8个座位，今有14名学生，问按以下不同的方式入座，各有多少种做法？

（1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定；（2）要求前排至少坐5人，后排至少坐4人。解：（1）由于就坐是有次序的，所有是排列问题。

5人坐前排，其坐法数为P(8,5)，4人坐后排，其坐法数为P(8,4)，

剩下的5个人在其余座位的就坐方式有P(7,5)种，根据乘法原理，就座方式总共有：

P(8,5)?P(8,4)?P(7,5)?28449792000（种）

（2）因前排至少需坐6人，最多坐8人，后排也是如此。

可分成三种状况分别探讨：

①前排恰好坐6人，入座方式有C(14,6)P(8,6)P(8,8)；②前排恰好坐7人，入座方式有C(14,7)P(8,7)P(8,7)；③前排恰好坐8人，入座方式有C(14,8)P(8,8)P(8,6)；各类入座方式相互不同，由加法法则，总的入座方式总数为：

C(14,6)P(8,6)P(8,8)?C(14,7)P(8,7)P(8,7)?C(14,8)P(8,8)P(8,6)?10461394944000

?典型错误：

先选6人坐前排，再选4人坐后排，剩下的4人坐入余下的6个座位。故总的入坐方式共有：C(14,6)P?8,6?C(8,4)P?8,4?P?6,4?种。

但这样计算无疑是有重复的，例如恰好选6人坐前排，其余8人全坐后排，那么上式中的C(8,4)P?8,4?就有重复。

第2页（共93页）

组合数学（其次版）

4．一位学者要在一周内安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？

解：用xi表示第i天的工作时间，i?1,2,?,7，则问题转化为求不定方程

x1?x2?x3?x4?x5?x6?x7?50的整数解的组数，且xi?5，于是又可以转

化为求不定方程y1?y2?y3?y4?y5?y6?y7?15的整数解的组数。该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。

故安排方案共有：RC(?,15)?C(15?7?1,15)?54264（种）?另解：

由于允许yi?0，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋〞号，每个空放置的“＋〞号数不限，未放“＋〞号的线段合成一条线段，求放法的总数。从而不定方程的整数解共有：

RC(?,6)?C(16?6?1,6)?21?20?19?18?17?166?5?4?3?2?1?54264（组）

即共有54264种安排方案。

5．若某两人拒绝相邻而坐，问12个人围圆周就坐有多少种方式？解：12个人围圆周就坐的方式有：CP(12,12)?11!种，

设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为1人，则这样的就坐方式有：CP(11,11)?10!种；由于甲乙相邻而坐，可能是“甲乙〞也可能是“乙甲〞；所以

则满足条件的就坐方式有：11!?2?10!?32659200种。

6．有15名选手，其中5名只能打后卫，8名只能打前锋，2名只能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？

解：用A、B、C分别代表5名打后卫、8名打前锋、2名可打前锋或后卫的集合，

则可分为以下几种状况：

（1）7个前锋从B中选取，有C87种选法，4个后卫从A中选取，有C54种，根据乘法法则，这种选取方案有：C87?C54种；

（2）7个前锋从B中选取，从A中选取3名后卫，从C中选1名后卫，

1根据乘法法则，这种选取方案有：C87?C53?C2种；

（3）7个前锋从B中选取，从A中选取2名后卫，C中2名当后卫，根据乘法法则，这种选取方案有：C87?C52种；

第3页（共93页）

组合数学（其次版）

（4）从B中选6个前锋，从C中选1个前锋，从A中选4个后卫，

14根据乘法法则，这种选取方案有：C86?C2?C5种；

（5）从B中选6个前锋，从C中选1个前锋，从A中选3个后卫，C中剩

13下的一个当后卫，选取方案有：C86?C2?C5种；

（6）从B中选5个前锋，C中2个当前锋，从A中选4个后卫，选取方案有：C85?C54种；根据加法法则，总的方案数为：

C8?C5?C8?C5?C2?C8?C5?C8?C2?C5?C8?C2?C5?C8?C5?1400747317261461354

7．求(x?y?2z?w)8展开式中x2y2z2w2项的系数。

解：令a?x,b??y,c??2z,d?w，则(a?b?c?d)8中a2b2c2z2项的系数为???8!7!??，即(x?y?2z?w)?22222!2!2!2!2??88中，x2(?y)2(?2z)2w2的系数，

因此，x2y2z2w2的系数为：7!2?(?1)2?(?2)2?10080。

8．求(x?y?z)4的展开式。

解：n?4,t?3，展开式共有RC(?,4)?C(4?3?1,4)?15（项），所以，

?4?4?4?4?4?4?4?3?4?34(x?y?z)??x?y?z?xy??????????xz?400??040??004??310??301??4?22?4?22?4?2???xy???xz???xyz?220??202??211??4?3?4?3?4??4?22???xy???xz???xyz???xyz130103112121?????????4?3?4?3?4?22???yz???yz???yz013031022???????x?y?z?4xy?4xz?4xy?4xz?4yz?4yz?6xy?6xz?6yz?12xyz?12xyz?12xyz222222222444333333

9．求(x1?x2?x3?x4?x5)10展开式中x23x3x46的系数。解：x23x3x46的系数为：?

10．试证任一整数n可唯一表示成如下形式：n??aii!i?1??10!??840?031603!?1!?6!??10

,0?ai?ii,?1?,2,第4页（共93页）

组合数学（其次版）

证明：（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!，定义函数f:M?N，

f(am?1,am?2,?,a2,a1)?am?1(m?1)!?am?2(m?2)!???a2?2!?a1?1!，

0?0?(m?1)!?0?(m?2)!???0?2!?0?1!显然，

?am?1(m?1)!?am?2(m?2)!???a2?2!?a1?1!?(m?1)(m?1)!?(m?2)(m?2)!???2?2!?1?1!?m!?(m?1)!?(m?1)!?(m?2)!???3!?2!?2!?1!?m!?1

即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中的任一数n均可表示成n??ai!的形式，

ii?1只需证明f是满射函数即可。又由于f是定义在两个有限且基数相等的函数上，因此假使能证明f单射，则f必是满射。

假设f不是单射，则存在(am?1,am?2,?,a2,a1),(bm?1,bm?2,?,b2,b1)?M，

(am?1,am?2,?,a2,a1)?(bm?1,bm?2,?,b2,b1)，且有K0?NK0?f(am?1,am?2,?,a2,a1)?f(bm?1,bm?2,?,b2,b1)

,,b2,b1，故必存在)由于(am?1,am?2,?,a2,a1)?(bm?1,bm?2?j?m?1，使得aj?bjaj?bj，使得

。不妨设这个j是第一个使之不相等的，即ai?bi(i?m?1,?,j?1)，且aj?bj，

am?1(m?1)!?am?2(m?2)!???a2?2!?a1?1!?bm?1(m?1)!?bm?2(m?2)!???b2?2!?b1?1!由于

0??bm?1(m?1)!?bm?2(m?2)!???b2?2!?b1?1!???am?1(m?1)!?am?2(m?2)!???a2?2!?a1?1!?所以，

?(bj?aj)j!?(bj?1?aj?1)(j?1)!???(b2?a2)?2!?(b1?a1)?1!?j!??bj?1?aj?1?(j?1)!???b2?a2?2!?b1?a1?1!????j!??(j?1)?(j?1)!???2?2!?1?1!??j!?(j!?1)?1

产生矛盾，所以f必是单射函数。

由于M?N?m!，所以f必然也是满射函数，

故对任意的n?N，都存在(am?1,am?2,?,a2,a1)?M，使得

n?am?1(m?1)!?am?2(m?2)!???a2?2!?a1?1!

第5页（共93页）

组合数学（其次版）

（1）0出现偶数次的字符串有

3?12n个；

?，其中q?2?。?2???n

n?n?n?n?n?2?n?n?q3?1（2）??2???2?????2?2?0??2??q?证明：（1）采用数学归纳法

当n?1时，0出现偶数次（0次），长度为1的字符串为“1〞和“2〞两个字符串，而

3?121?2，故结论成立。

假设当n?k(k?1)时，结论成立，即0出现偶数次，长度为k的字符串有

3?12k个，

当n?k?1时，0出现偶数次，长度为k?1的字符串包括两部分：①在0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，这样的字符串有2?3?12k?3?1个。

k②给0出现奇数次，长度为k的字符串后面再增加一个0，

?k3k?1?3k?1因此，这样的字符串有：?3?。??2?2?根据加法法则，0出现偶数次，长度为k?1的字符串共有：

3?1?k3?12k?3k+1?12，即n?k?1时，结论也成立。

所以，根据数学归纳法，结论成立。（2）由（1）知，右端表示0出现偶数次的字符串数。而左端代表的组合问题是：

长度为n的字符串中，有0个0

?n?n的字符串数有：??2，

?0??n??2?有2个0的字符串数有：??2n?2，?，有q个0

?n?n?q的字符串数有：??2?q?，

第16页（共93页）

组合数学（其次版）

根据加法法则，可知，左端代表的是长度为n的字符串中0出现偶数次的字符串数，因此

n?n?n?n?n?2?n?n?q3?1?????2???2???22?0??2??q?

31．5台教学仪器供m个学生使用，要求使用第1台和第2台的人数相等，

有多少种分派方案？解：?方法一：

先从m个学生中选取k个使用第1台机器，再从剩下的m?k个学生中选取k个使用第2台机器，其余m?2k个学生可以任意使用剩下的3台机器，

按乘法原理，其组合数为??m??m?k?m?2k?3????k??k?q，这里k?0,1,2,?q(q???)，

?2?种使用方案。

?m?于是，按加法原理，共有???方法二：

?m??m?k?m?2k????3k?k?0?k??先从m个学生种选出2k个，再将选出2k个学生平均分到1、2台机器上，其余的m?2k个学生可以任意使用剩下的3台机器，按乘法法则，其组合数为??m??2k?m?2k????3?2k??k?q，这里k?0,1,2,?q(q???)

?2?种使用方案。

?m??m??2k?于是，按加法原理，共有??????3m?2kk?0?2k??k?

32．由n个0及n个1组成的字符串，其任意前k个字符中，0的个数不少于1

的个数的字符串有多少？

解：（参见P21，例1.8.8）转化为格路问题。即从点(0,0)到(n,n)，只能从对角

线上方走，但可以碰见对角线的所有最短路径数。显然，第一步必然要走到点(0,1)，因此可以转换为从点(0,1)到(n,n)的所有满足条件的路径数，进一步，可以转换为从(0,1)点到(n,n?1)，只能从对角线上方走，但不可以碰见对角线的所有路径数，由于从(0,1)点到(n,n?1)的所有经过对角线的路径数与从(1,0)点到(n,n?1)点的所有路径数是一一对应的，因此，所求的字符串有：

第17页（共93页）

组合数学（其次版）

?n?0?(n?1)?1??n?1?(n?1)?0???????C(2n,n)?C(2n,n?1)nn?1????（个）

?方法二：由n个1和n个0组成的2n位二进制数共有

异元素的全排列)，

(2n)!(n!)2个(2n个不尽相

设所求的二进制数共有bn个，不符合要求的数有rn个。而不合要求的数的特征是从左向右扫描时，必然在某一位首次出现0的个数小于1的个数，即从左向右累计到第2k＋1位时出现k个0和k?1个1。此时，后2(n?k)?1位上有n?k?1个1，n?k个0。将后部分的0改写为1，1改写为0。结果整个数变成由n?1个和n?1个0组成的2n位数z。即一个不合要求的数唯一对应于这样的一个数z。

反之，给定一个由n?1个1和n?1个0组成的2n位数z．由于1比0多2个，故一定在某一位首次出现0的累计数少于1的累计数。依同法将此位后的0与1互换，使z变成由n个1和n个0组成的2n位数。

所以，这两种二进制数一一对应。即rn??2n?!

?n?1?!?n?1?!1n?1C?2n,n?。

故bn??2n?!?rn2?n!???2n?!?2n?!??2?n!??n?1?!?n?1?!?2n?!?2n?1?n!?1习题二（母函数及其应用）

1．求以下数列的母函数(n?0,1,2,?)（1）?(?1)n???；

??n????a??（2）{n?5}；（3）{n(n?1)}；（4）{n(n?2)}；

?a?解：（1）母函数为：G(x)??(?1)??xn?n?0?n??n?a?na??n?(?x)?(1?x)n?0???；

51?x5?4x(1?x)2??n?n（2）母函数为：G(x)??方法二：

?(n?5)xn?0??nxn?0?5?x?n?0nx(1?x)2??；

第18页（共93页）

组合数学（其次版）

??n?nG(x)??(n?5)xn?0??4??n?1?xn?0??4xn?0n????x?n?1n?0??4?1?????1??1?x?1?x?1?x41?x?5?4x(1?x)2

1?1?x?2?（3）母函数为：

??n?nG(x)??n(n?1)xn?0???n(n?1)xn?0?2?nx?n?0n2x(1?x)3?2x(1?x)2?2x23(1?x)；

?方法二：

?nG(x)??n(n?1)xn?0?2?0?0?xn2?n?n?1?xn?2?2n?2?x?n?0?n?2??n?1?x?x??n?0?xn?2???2?n?2?2?x?x??x?x???1?x?n?0????2x23?2?

?1?x?（4）母函数为：

??n?nG(x)??n(n?2)xn?0???n(n?1)xn?0???nxn?0n?2x(1?x)3?x(1?x)2?3x?x(1?x)23。

?方法二：

?n?nG(x)??n(n?2)xn?0?n???n?1??n?2?xn?0n?1???n?1?xn?0??xn?0n???xn?02n?2?????x?n?0????1??n?2???n?1?????x?x?????1?x?n?0??n?0?1?x1?x?1211?x???????????32?1?x?1?x?1?x??1?x?1?x?1?x??3x?x23??

?1?x?

2．证明序列C(n,n),C(n?1,n),C(n?2,n),?的母函数为证明：由于C(n?k,n)?C(n?k?1,n)?C(n?k?1,n?1)

1(1?x)n?1。

第19页（共93页）

组合数学（其次版）

令Gn(x)???C(n?k,n)xk?0k?C(n,n)?C(n?1,n)x?C(n?2,n)x?C(n?3,n)x??23，

则x?Gn(x)?C(n,n)x?C(n?1,n)x2?C(n?2,n)x3??，

Gn?1(x)?C(n?1,n?1)?C(n,n?1)x?C(n?1,n?1)x?C(n?2,n?1)x??23

而(1?x)Gn(x)?Gn?1(x)?0故Gn?x??11?x?Gn?1?x??1?Gn?2?x?????????231?1?x?2?1?x?n?G0?x?

G0(x)?C(0,0)?C(1,0)x?C(2,0)x?C(3,0)x??又?1?x?x?x???11?x123

所以

Gn?x???1?x?n?1

?方法二：

?，??en?的k-组合数为C(n?k?1,k)，已知S????e1，??e2，?n?k?1?k???其母函数为：A(x)?(1?x?x?x??)??xnk(1?x)k?0??23n1?

序列C(n,n),C(n?1,n),C(n?2,n),?的母函数为

G(x)?C(n,n)?C(n?1,n)x?C(n?2,n)x?C(n?3,n)x????k23??C(n?k,n)xk?0?k?0??C(n?k,k)xk?0kk

???C(n?1?k?1,k)x1(1?x)n?1

3．设S?{??e1,??e2,??e3,??e4}，求序列{an}的母函数。其中，an是S的满足以下条件的n组合数。（1）S的每个元素都出现奇数次；（2）S的每个元素都出现3的倍数次；（3）e1不出现，e2至多出现一次；

（4）e1只出现1、3或11次，e2只出现2、4或5次；（5）S的每个元素至少出现10次。

第20页（共93页）

组合数学（其次版）

G1(x)??1?x??1?x2??1?x??1?x??1?x??1?x??34564

??1?x11?x21?x??1?x1?x132?1?x1?x1536?1?x1?x84?1?x1?x105?1?x1?x12??6

1?x?1?x??将n分拆为奇数之和的分拆数的母函数为：

??i???3i???5i?G2(x)???x???x???x???i?0??i?0??i?0?111??????G1(x)351?x1?x1?x所以，两种分拆的方案数一致。

17．求自然数50的分拆总数，要求分拆的每个分项不超过3。解：其母函数为：

G(x)?(1?x?x??)(1?x?x??)(1?x?x??)?(1?x?x??)(1?x?x??)(1?x?x??)?1(1?x)(1?x)22243622436(1?x?x??)?36?(1?x?x??)?36?111111???????2?41?x41?x2(1?x)?1???4?1??i?0?x?i14??i?0i(?1)x?ii12i??i?0i?36(i?1)x?(1?x?x??)?36??1?(?1)4i?0?2(i?1)?x?(1?x?x??)

?1(i?2)i为偶数??236?(1?x?x??)???1(i?1)i为奇数??2

则所求的分拆数为x50的系数，即

1212?(2?3?0?2)?(2?3?1?1)?(2?3?2?2)?(2?3?3?1)???(2?3?15?1)?(2?3?16?2)?

?[2?17?3?16?172?2?9?1?8]?234第31页（共93页）

组合数学（其次版）

习题三（递推关系）

1．解以下递推关系：

?an?7an?1?10an?2?0（1）?

a?0,a?11?0?an?6an?1?9an?2?0（2）?

a?0,a?11?0?an?an?2?0（3）?

a?0,a?21?0（4）??an?2an?1?an?2?a0?a1?1

?an?an?1?9an?2?9an?3（5）?

a?0,a?1,a?212?0解：（1）对应的特征方程为：x2?7x?10?0，解得x1?2,x2?5。所以齐次递推方程的通解为：an?A?2n?B?5n，代入初始条件，得：a0?A?B?0，a1?2A?5B?1，解得：A??13,B?13，故an??13?2?n13?5n。

（2）对应的特征方程为：x2?6x?9?0，解得：x1?x2??3，所以，齐次递推方程的通解为：an?(A?Bn)?(?3)n，代入初始条件，a0?A?0，a1?(A?B)?(?3)?1，解得：A?0,B??，故an??n?(?3)n。

3311（3）对应的特征方程为：x2?1?0，解得：x1?i,x2??i，所以，齐次递推方程的通解为：an?A?(i)n?B?(?i)n，代入初始条件，a0?A?B?0，a1?A?i?B?i?2，解得：A??i,B?i，故an?(i)n?1?(?i)n?1。

（4）对应的特征方程为：x2?2x?1?0，解得：x1?x2?1，所以，齐次递推方程的通解为：an?A?Bn，代入初始条件，a0?A?1，a1?A?B?1，解得：A?1,B?0，故an?1。

（5）对应的特征方程为：x3?x2?9x?9?0，解得：x1?1,x2?3,x3??3，所以，齐次递推方程的通解为：an?A?B?3n?C?(?3)n，

第32页（共93页）

组合数学（其次版）

代入初始条件，a0?A?B?C?0，a1?A?3B?3C?1，

a2?A?9B?9C?2，

解得，A??,B?4113,C??112，故an??14?3n?1?112?(?3)n

2．求由A，B，C，D组成的允许重复的排列中AB至少出现一次的排列数。解：?方法一：

我们只要求出n位排列中不出现AB的排列个数an，则至少出现一次AB的排列个数为bn?4n?an。

an可以分成两部分：

(1)an：在n位排列中不出现AB且在第n位出现A的排列数目。

：在n位排列中不出现AB且在第n位出现B或C或D的排列的数目。

an(2)因此，an?an(1)?an(2)，

显然，若在n位排列中不出现AB，则在前n?1位中也不会出现AB，考虑第n位：

（1）若第n位为A，则第n?1位可以是A、B、C、D中的任何一位；（2）若第n位为B，则第n?1位只能是B、C、D中任何一位；（3）若第n位为C或D，则第n?1为可以是A、B、C、D中任一位；故可得递推关系：

(1)(1)(2)?an?an?1?an?1?(2)(1)(2)?an?2an?1?3an?1?(1)(2)a?1,a?311???(1)ii令A?x???i?1a，B?x??x?ai?1(2)ixi，

(2)n?an?1两边同乘于x(n?2)，即方程an(1)?an(1)?1x:x:x:?432a2?a1?a1(1)(1)(1)4(1)3(1)(1)(2)a3?a2?a2a?a?a(2)(2)3

?(1)ii?(1)ii?1?将上面的式子进行累加，可得：?ax??axi?2i?1??ai?1(2)ixi?1，

第33页（共93页）

组合数学（其次版）

故A(x)?x?xA(x)?xB(x)，即(1?x)A(x)?xB(x)?x

(2)方程an(2)?2an(1)两边同乘于xn(n?2)，即?3a?1n?1x:x:x:?432a2a3a(2)?2a1?3a1(1)(1)3(1)(2)(2)?2a2?3a2?2a?3a(2)(2)4(2)3

?(2)ii?(1)ii?1?同样，将上面的式子进行累加，可得?ax?2?axi?2i?1?3?aixi?1(2)i?1

故B(x)?3x?2xA(x)?3xB(x)，即?2xA(x)?(1?3x)B(x)?3x故可得关