![Richard_A[1].Brualdi_组合数学习题解答](https://img.doczj.com/img5a/02pru4osfnpjjibj1ss2-a1.webp)
![Richard_A[1].Brualdi_组合数学习题解答](https://img.doczj.com/img5a/02pru4osfnpjjibj1ss2-82.webp)
特别说明
此资料来自豆丁网(https://www.doczj.com/doc/5712675139.html,/)
您现在所看到的文档是使用下载器所生成的文档
此文档的原件位于
https://www.doczj.com/doc/5712675139.html,/p-48705515.html
感谢您的支持
抱米花
https://www.doczj.com/doc/5712675139.html,/lotusbaob
《组合数学》试题 姓名 学号 评分 一、填空题（每小题3分，共18分） 1、 红、黄、蓝、白4个球在桌上排种排法。成一圈，有 2、设P 、Q 为集合，则|P ∪Q| |P| + |Q|. 3、0max i n n i ≤≤????=?? ????? 。 4. 366个人中必有 个人生日相同。 5.的系数为的展开式中，342326 41x x x x i i ?? ? ??∑= 。 6.解常系数线性齐次递推关系的常用方法称为 法 。 二、单项选择题（每小题2分，共12分） 1、数值函数f = (1,1,1,...)的生成函数F(x) =（ ） A 、(1+x)n B 、1－x C 、(1－x)－1 D 、(1+x)－n 2、递推关系f(n) = 4f(n －1)－4f(n －2)的特征方程有重根2，则（ ）是它的一般解 。 A 、C 12n －1+C 22n B 、( C 1+C 2n)2n C 、C(1+n)2n D 、C 12n +C 22n . 3、由6颗不同颜色的珠子可以做成 （ ）种手链。 A 、720 B 、120 C 、60 D 、6
4、=??? ??-∑=n k k k n 0 )1(（ ）。 A 、2n B 、0 C 、n2n －1 D 、1 5、设F(x),G(x)分别是f 和g 的生成函数，则以下不成立的是（ ） 。 A 、F(x)+G(x) 是f+g 的生成函数 B 、F(x)G(x) 是fg 的生成函数 C 、x r F(x) 是S r (f)的生成函数 D 、F(x)－xF(x) 是?f 的生成函数. 6、在无柄茶杯的四周画上四种不同的图案，共有（ ）种画法。 A 、24 B 、12 C 、6 D 、3 三、 解答题（每小题10分，共70分） 1. 有4个相同的红球，5个相同的白球，那么这9个球有多少种不同的排列方 式？ 2. 公司有5台电视机，4台洗衣机，7台冰箱，现要把其中3台电视机，2台洗 衣机，4台冰箱选送到展销会，试问有多少种选法？ 3. 设S = {1, 3?2, 3?3, 2?4, 5}是一个多重集，那么由集合S 的元素能组成多少个 不同的四位数。 4.试求在1到300之间那些不能被3, 5和7中任何一个整除的整数个数。 5. 解非齐次递推关系 1201 693,20,1n n n a a a n a a --++=≥??==? 6. 将字母a,b,c,d,e,f,g 排成一行，使得模式beg 和cad 都不出现的排列总数是多少？ 7. 某次会议有10个代表参加，每一位代表至少认识其余9位中的一位，则10位代表中至少有两位代表认识的人数相等。
习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。
任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。
一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。
排列组合知识点总结+典型例题及答案解析 一．基本原理 1．加法原理：做一件事有n 类办法，则完成这件事的方法数等于各类方法数相加。 2．乘法原理：做一件事分n 步完成，则完成这件事的方法数等于各步方法数相乘。 注：做一件事时，元素或位置允许重复使用，求方法数时常用基本原理求解。 二．排列：从n 个不同元素中，任取m （m ≤n ）个元素，按照一定的顺序排成一 .m n m n A 有排列的个数记为个元素的一个排列，所个不同元素中取出列，叫做从 1.公式：1.()()()()! ! 121m n n m n n n n A m n -=+---=…… 2. 规定：0!1= (1)!(1)!,(1)!(1)!n n n n n n =?-+?=+ (2) ![(1)1]!(1)!!(1)!!n n n n n n n n n ?=+-?=+?-=+-； (3) 111111 (1)!(1)!(1)!(1)!!(1)! n n n n n n n n n +-+==-=- +++++ 三．组合：从n 个不同元素中任取m （m ≤n ）个元素并组成一组，叫做从n 个不同的m 元素中任取 m 个元素的组合数，记作 Cn 。 1. 公式： ()()()C A A n n n m m n m n m n m n m m m ==--+= -11……!! !! 10 =n C 规定： 组合数性质： .2 n n n n n m n m n m n m n n m n C C C C C C C C 21011 =+++=+=+--…… ，， ①；②；③；④ 111 12111212211 r r r r r r r r r r r r r r r r r r n n r r r n n r r n n n C C C C C C C C C C C C C C C +++++-+++-++-++++ +=+++ +=++ +=注： 若1 2 m m 1212m =m m +m n n n C C ==则或 四．处理排列组合应用题 1.①明确要完成的是一件什么事（审题） ②有序还是无序 ③分步还是分类。
组合数学试题集 一.简单题目 可以根据需要改成选择题或者填空题 1．在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（参见课本21页） 解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数； （1）选1个，即构成1位数，共有15P 个； （2）选2个，即构成两位数，共有25P 个； （3）选3个，即构成3位数，共有35P 个； （4）选4个，即构成4位数，共有4 5P 个； 由加法法则可知，所求的整数共有：12345555205P P P P +++=个。 2．一教室有两排，每排8个座位，今有14名学生，问按下列不同的方式入座，各有多少种做法？（参见课本21页） （1）规定某5人总坐在前排，某4人总坐在后排，但每人具体座位不指定； （2）要求前排至少坐5人，后排至少坐4人。 解：（1）因为就坐是有次序的，所有是排列问题。 5人坐前排，其坐法数为(8,5)P ，4人坐后排，其坐法数为(8,4)P ， 剩下的5个人在其余座位的就坐方式有(7,5)P 种， 根据乘法原理，就座方式总共有： (8,5)(8,4)(7,5)28449792000P P P =（种） （2）因前排至少需坐6人，最多坐8人，后排也是如此。 可分成三种情况分别讨论： ① 前排恰好坐6人，入座方式有(14,6)(8,6)(8,8)C P P ； ② 前排恰好坐7人，入座方式有(14,7)(8,7)(8,7)C P P ； ③ 前排恰好坐8人，入座方式有(14,8)(8,8)(8,6)C P P ；
各类入座方式互相不同，由加法法则，总的入座方式总数为： (14,6)(8,6)(8,8)(14,7)(8,7)(8,7)(14,8)(8,8)(8,6)10461394944000 C P P C P P C P P ++= 3．一位学者要在一周安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？（参见课本21页） 解：用i x 表示第i 天的工作时间，1,2,,7i =，则问题转化为求不定方程 123456750x x x x x x x ++++++=的整数解的组数，且5i x ≥，于是又可以转化为求不定方程123456715y y y y y y y ++++++=的整数解的组数。 该问题等价于：将15个没有区别的球，放入7个不同的盒子中，每盒球数不限，即相异元素允许重复的组合问题。 故安排方案共有：(,15)(1571,15)54264RC C ∞=+-= （种） ? 另解： 因为允许0i y =，所以问题转化为长度为1的15条线段中间有14个空，再加上前后两个空，共16个空，在这16个空中放入6个“＋”号，每个空放置的“＋”号数不限，未放“＋”号的线段合成一条线段，求放法的总数。从而不定方程的整数解共有： 212019181716(,6)(1661,6)54264654321 RC C ?????∞=+-= =?????（组） 即共有54 264种安排方案。 4.求下列函数的母函数: {(1)}n n -；（参见课本51页） 母函数为： 2 323000222()(1)(1)2(1)(1)(1)n n n n n n x x x G x n n x n n x nx x x x ∞∞∞====-=+-=-=---∑∑∑； ? 方法二： ()()()()()220 22220 02222023 ()(1)00121121n n n n n n n n n n G x n n x x n n x x n n x x x x x x x x x x ∞∞-==∞∞ +==∞+==-=++-"=++=""????== ? ?-???? =-∑∑∑∑∑
作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明：
概念形成 1、元素：我们把问题中被取的对象叫做元素 2、排列：从n 个不同元素中，任取m （m n ≤）个元素（这里的被取元素各不相同）按照一定的顺．．．． 序．排成一列，叫做从n 个不同元素中取出m 个元素的一个排列．．．． 。 说明：（1）排列的定义包括两个方面：①取出元素，②按一定的顺序排列（与位置有关） （2）两个排列相同的条件：①元素完全相同，②元素的排列顺序也相同 合作探究二 排列数的定义及公式 3、排列数：从n 个不同元素中，任取m （m n ≤）个元素的所有排列的个数叫做从n 个元素中取出 m 元素的排列数，用符号m n A 表示 议一议：“排列”和“排列数”有什么区别和联系？ 4、排列数公式推导 探究：从n 个不同元素中取出2个元素的排列数2n A 是多少？3n A 呢？m A n 呢？ )1()2)(1(+-?--=m n n n n A m n （,,m n N m n *∈≤） 说明：公式特征：（1）第一个因数是n ，后面每一个因数比它前面一个少1，最后一个 因数是1n m -+，共有m 个因数； （2）,,m n N m n *∈≤ 即学即练: 1.计算 (1）410A ； (2）25A ；(3)3355A A ÷ 2.已知101095m A =???，那么m = 3．,k N +∈且40,k ≤则(50)(51)(52)(79)k k k k ----用排列数符号表示为( ) A ．5079k k A -- B ．2979k A - C ．3079k A - D ．3050k A - 例1． 计算从c b a ,,这三个元素中，取出3个元素的排列数，并写出所有的排列。 5 、全排列：n 个不同元素全部取出的一个排列，叫做n 个不同元素的全排列。 此时在排列数公式中， m = n 全排列数：(1)(2)21!n n A n n n n =--?=（叫做n 的阶乘）. 即学即练:口答（用阶乘表示）：（1）334A （2）44A （3）)!1(-?n n 排列数公式的另一种形式： )! (!m n n A m n -= 另外，我们规定 0! =1 .
《组合数学》期末试题（A ）姓名班级学号成绩 一，把m 个负号和n 个正号排在一条直线上，使得没有两个负 号相邻，问有多少种不同的排法。 二，在1和100之间既不是某个整数的平方，也不是某个整数的 立方的数有多少个？ 三，边长为1的等边三角形内任意放10个点，证明一定存在两 个点，其距离不大于1/3。 四，凸10边形的任意三条对角线不共点，试求(1)这凸10边形的 对角线交于多少个点？(2)又把所有对角线分割成多少段？五，求和=?? ???∑k－（－）k+1111n k n k 六，求解递推关系--++=??==?12016930,1 n n n a a a a a 七，用红白蓝三种颜色对1×n 的方格涂色，每个方格只能涂一种颜色，如果要求偶数个方格涂成红色，问有多少种方法？ 八，用红、蓝二种颜色对1×n 的方格涂色，每个方格只能涂一种颜色，如果要求涂成红色的两个方格不能相邻，问有多少种方法？注，1-4、6题各15分，第5题10分，第7题8分，第八题7分。
北京邮电大学2005 ——2006 学年第1 学期 《组合数学》期末试题答案 一， (15) 解： 由于正负号不能相连，故先将正号排好，产生n+1个空档。 --------5分 则负号只能排在两个正号之间，这相当于从n+1个数中取m 个数的组合，故有---------10分 1n m +????? ?种方式。----15 备注：若写出m>n+1时为0，m=n+1时为1，给5分 二， （19分） 解：设A 表示是1-100内某个数的平方的集合，则 |A|=10, -----4分 设B 表示是1-100内某个数的立方的集合，则|B|=4, --8分 |A ∩B|=2, -----12分 由容斥原理得 100|||||| 100104288A B A B A ∩=??+∩=??+=B --------19分 三， （15分） 证明：将此三角形剖分成9个小的边长为1/3的等边三角形。 - ------5分 由鸽巢原理，必有两点在某一个小三角形内，----12分 此时，这两点的距离不超过小三角形边长1/3。从而得证。 -------15分 四， （15分） 解：（1）由于没有三条对角线共点，所以这凸多边形任取4点，组成的多边形内唯一的一个四边形，确定唯一一个交点，--5分 从而总的交点数为C(10,4)=210-------------10分 （2）如图，不妨取顶点1，考察由1出发的对角线被其他对角线 剖分的总数。不妨设顶点标号按顺时针排列，取定对角线1 i
?1.证：对n 用归纳法。先证可表示性： 当n=0,1时，命题成立。 假设对小于n 的非负整数，命题成立。对于n,设k!≤n ＜(k+1)!,即0≤n-k!＜k·k!由假设对n-k!,命题成立， 设n-k!=∑a i ·i!，其中a k ≤k-1,n=∑a i ·i!+k!，命题成立。i=1 k i=1 k 再证表示的唯一性： 设n=∑a i ·i!=∑b i ·i!, 不妨设a j ＞b j ,令j=max{i|a i ≠b i }a j ·j!+a j-1·(j-1)!+…+a 1·1! =b j ·j!+b j-1·(j-1)!+…+b 1·1!,(a j -b j )·j!=∑(b i -a i )·i!≥j!＞∑i·i!≥∑|b i -a i |·i!≥∑(b i -a i )·i! 另一种证法：令j=min{i|a i ≠b i }∑a i ·i!=∑b i ·i!,两边被(j+1)!除,得余数a j ·j!=b j ·j!,矛盾. i=1 k i=1k i=1 j-1i=1 j-1 i=1j-1i=1 j-1 i ≥j i ≥j ?2.证： 组合意义： 等式左边：n 个不同的球，先任取出1个，再从余下的n-1个中取r 个； 等式右边：n 个不同球中任意取出r+1个，并指定其中任意一个为第一个。显然两种方案数相同。 nC(n-1,r) = n ————= ——————— (n-1)! (r+1)·n! r!·(n-r-1)! (r+1)·r!·(n-r-1)! = ——————= (r+1)C(n,r+1).(r+1)·n! (r+1)!·(n-r-1)! ?3.证： 设有n 个不同的小球，A 、B 两个盒子,A 盒中恰好放1个球,B 盒中可放任意个球。有两种方法放球： ①先从n 个球中取k 个球(k ≥1),再从中挑 一个放入A 盒,方案数共为∑kC(n,k),其余球放入B 盒。 ②先从n 个球中任取一球放入A 盒，剩下n-1个球每个有两种可能，要么放入B 盒， 要么不放，故方案数为n2 . 显然两种方法方案数应该一样。 k=1n n-1 ?4.解：设取的第一组数有a 个,第二组有b 个,而 要求第一组数中最小数大于第二组中最大的，即只要取出一组m 个数(设m=a+b),从大到小取a 个作为第一组,剩余的为第二组。此时方案数为C(n,m)。从m 个数中取第一组数共有m-1中取法。总的方案数为∑(m-1)C(n,m)=n ·2 +1. ?5.解：第1步从特定引擎对面的3个中取1个有 C(3,1)种取法，第2步从特定引擎一边的2个中 取1个有C(2,1)种取法，第3步从特定引擎对面的2个中取1个有C(2,1)中取法，剩下的每边1个取法固定。 所以共有C(3,1)·C(2,1)·C(2,1)=12种方案。 m=2 n n-1 ?6.解：首先所有数都用6位表示，从000000到 999999中在每位上0出现了10 次,所以0共出现 了6·10 次,0出现在最前面的次数应该从中去掉， 000000到999999中最左1位的0出现了10 次， 000000到099999中左数第2位的0出现了10 次， 000000到009999左数第3位的0出现了10 次, 000000到000999左数第4位的0出现了10 次, 000000到000099左数第5位的0出现了10 次, 000000到000009左数第6位的0出现了10 次。另外1000000的6个0应该被加上。所以0共出现了 6·10 –10 –10 –10 –10 –10 –10 +6 = 488895次。 5 5 5 4 3 2 1 5543210 ?7.解：把n 个男、n 个女分别进行全排列，然后 按乘法法则放到一起，而男女分别在前面,应该 再乘2,即方案数为2·(n!) 个. 围成一个圆桌坐下， 根据圆排列法则，方案数为2 ·(n!) /(2n)个. ?8.证：每个盒子不空，即每个盒子里至少放一 个球，因为球完全一样，问题转化为将n-r 个小球放入r 个不同的盒子，每个盒子可以放任意个球，可以有空盒，根据可重组合定理可得共有C(n-r+r-1,n-r) = C(n-1,n-r)中方案。根据C(n,r)=C(n,n-r),可得 C(n-1,n-r)=C(n-1,n-1-(n-r))=C(n-1,r-1)个方案。证毕。 2 2 ?9.解：每个能整除尽数n 的正整数都可以选取每个素数p i 从0到a i 次，即每个素数有a i +1种选择，所以能整除n 的正整数数目为(a 1+1)·(a 2+1)·…·(a l +1)个。 ?10.解：相当于把n 个小球放入6个不同的盒子里，为可重组合，即共有C(n+6-1,n)中方案，即C(n+5,n)中方案。 ?11.解：根据题意,每4个点可得到两条对角线,1个对角线交点,从10个顶点任取4个的方案有C(10,4)中,即交于210个点。
组合数学课后标准答案
————————————————————————————————作者：————————————————————————————————日期：
习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。
任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。
一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。
排列组合典型例题 排列组合问题联系实际生动有趣，但题型多样，思路灵活，因此解决排列组合问题，首先要认真审题，弄清楚是排列问题、组合问题还是排列与组合综合问题；其次要抓住问题的本质特征，采用合理恰当的方法来处理。 教学目标 1.进一步理解和应用分步计数原理和分类计数原理。 2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力 3.学会应用数学思想和方法解决排列组合问题. 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1m 种不同的方法，在第2类办法中有2m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有： 12n N m m m =+++ 种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有1m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有： 12n N m m m =??? 种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合要求的元素占了这两个位置.
组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k
高中数学排列与组合 （一）典型分类讲解 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 先排末位共有1 3C 然后排首位共有1 4C 最后排其它位置共有 34A 由分步计数原理得1 1 3 434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元 素内部进行自排。由分步计数原理可得共有 522522480A A A =种不同的排法 练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？ 解:分两步进行第一步排2个相声和3个独唱共有55A 种， 第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种 46 A 不同的方法,由分步计数原理,节目的不同顺序共有54 56A A 种 练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30 四.定序问题倍缩空位插入策略 例4. 7人排队,其中甲乙丙3人顺序一定共有多少不同的排法 解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素 之间的全排列数,则共有不同排法种数是： 73 73/A A (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有 47 A 种方法，其余的三个位置甲乙丙共有 1种坐法，则共有4 7A 种方法。 思考:可以先让甲乙丙就坐吗? （插入法)先排甲乙丙三个人,共有1种排法,再把其余4四人依次插入共有 方法 练习题:10人身高各不相等,排成前后排，每排5人,要求从左至右身高逐渐增加，共有多少排法？ 5 10C 五.重排问题求幂策略 例5.把6名实习生分配到7个车间实习,共有多少种不同的分法 解:完成此事共分六步:把第一名实习生分配到车间有 7 种分法.把第二名实习生分配到车间也有7种分依此类推,由分步计数原 理共有6 7种不同的排法 练习题： 1． 某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插 法的种数为 42 4 4 3 允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以逐一安排各个元素的位置，一般地n 不同的元素没有限制地安排在m 个位置上的排列数为n m 种
排例组合专题训练 1． 将3个不同的小球放入4个盒子中，则不同放法种数有A ．81 B ．64 C ．12 D ．14 2．5个人排成一排,其中甲、乙两人至少有一人在两端的排法种数有 A ．33A B ．334A C ．523533A A A - D ．23113 23233A A A A A + 3．,,,,a b c d e 共5个人，从中选1名组长1名副组长，但a 不能当副组长，不同的选法总数是 A.20 B ．16 C ．10 D ．6 4．现有男、女学生共8人，从男生中选2人，从女生中选1人分别参加数学、物理、化学三科竞赛，共有90种不同方案，那么男、女生人数分别是 A ．男生2人女生6人 B ．男生3人女生5人 C ．男生5人女生3人 D ．男生6人女生2人. 5．在8 2 x ? ?的展开式中的常数项是A.7 B ．7- C ．28 D ．28- 6．5 (12)(2)x x -+的展开式中3 x 的项的系数是A.120 B ．120- C ．100 D ．100- 7．22n x ???展开式中只有第六项二项式系数最大,则展开式中的常数项是 A ．180 B ．90 C ．45 D ．360 8．由数字1、2、3、4、5组成没有重复数字的五位数，其中小于50000的偶数共有 A ．60个 B ．48个 C ．36个 D ． 24个 9．3张不同的电影票全部分给10个人,每人至多一张,则有不同分法的种数是 A ．1260 B ．120 C ．240 D ．720 10．n N ∈且55n <,则乘积(55)(56) (69)n n n ---等于 A ．5569n n A -- B ．15 69n A - C ．15 55n A - D ．14 69n A - 11．从不同号码的5双鞋中任取4只，其中恰好有1双的取法种数为 A ．120 B ．240 C ．280 D ．60 12．把10 )x -把二项式定理展开，展开式的第8项的系数是 A ．135 B ．135- C ．- D ． 13．2122n x x ??+ ?? ?的展开式中，2 x 的系数是224，则2 1x 的系数是A.14 B ．28C ．56 D ．112 14．不共面的四个定点到面α的距离都相等，这样的面α共有几个A ．3 B ．4 C ．6 D ．7
李凡长版-组合数学课后习题答案-习题3
第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17
排列组合 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1 m 种不同的方法，在第2类办法中有2 m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有：12n N m m m =+++种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有1 m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有：12n N m m m =???种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合 要求的元素占了这两个位置. 先排末位共有13 C C 1 4 A 3 4 C 1 3 然后排首位共有14 C 最后排其它位置共有34 A 由分步计数原理得113434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花
不种在中间，也不种在两端的花盆里，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素， 同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有5225 2 2 480A A A 种不同的排法 乙 甲丁 丙 练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈 节目不能连续出场,则节目的出场顺序有多少种？ 解:分两步进行第一步排2个相声和3个独唱共有55 A 种，第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种46 A 不同的方法,由分步计数原理,节目的不同顺序共有5456 A A 种 练习题：某班新年联欢会原定的5个节目已排成节目单， 要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素 一起作排列 ,同时要注意合并元素内部也必须排列. 元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端
第一部分：填空题。 题目1:求n 元布尔函数f (x1，x2，…，xn ）的数目，其中布尔函数是指含有与（∧）、或（∨）、非（－）等基本布尔运算的函数。 解答：设有n 个布尔变元x 1，x 2，…，x n ，其中x i ∈{0，1}，i =1，2，…，n ，根据乘法原理(x 1，x 2，…，x n )共有2n 种不同指派，对每个指派，布尔函数取值为{0，1}，故不同的布尔函数的数目为：22n 。 （考试中会给定n 的具体数值，带入公式直接计算即可。） 题目2：n 对夫妻围一圆桌而坐，求每对夫妻相邻而坐的方案数。 解答：夫妻相邻而坐，可以将一对夫妻看成一个整体，其圆排列数为(n -1)!，由于每对夫妻可以交换位置，故所求方案数为(n -1)!×2n 。 题目3：求多重集合M = {∞·a 1, ∞·a 2, …, ∞·a n }的r 排列数。 解答：在构造的M 的一个r 排列时，第一项有n 种选择，第二项有n 种选择，……， 第r 项有n 种选择，故M 的r 排列数为n r 。 (一般地，n 元多重集合表示为：M = {k 1·a 1, k 2·a 2, …, k n ·a n }其中：a i （i = 1, 2, …, n ）表示元素的种类，k i （i = 1, 2, …, n ）表示元素a i 的个数。) 题目4：求多重集合M = { k 1·a 1, k 2·a 2, …, k n ·a n }的全排列数。 解答：先把M 中的所有的k 1 + k 2 + … + k n 个元素看成是互不相同的，则它的全排列数为(k 1 + k 2 + … + k n )!。但是这里k i !个a i 是相同的，所以k i !个a i 的位置相同并且同其他元素排列也相同的排列是同一个，故M 的全排列数为： ! !!)! (2121n n k k k k k k +++。 题目5：确定1054321)(x x x x x ++++的展开式中x 13 x 2 x 34 x 52的系数。 解答：??? ? ??=???? ?????? ?????? ?????? ??2,4,1,310224617310 ! 2!4!1!3!10! 0!2!2! 2!4!6! 6!1! 7!7!3! 10= ? ? ? = （? ?? ? ??r n 表示从n 中取r 个的组合，与r n C 的意义完全相同。试题中可能会改变具体的数值，例如求15 54321)(x x x x x ++++的展开式中x 15x 24 x 34 x 52的系数，只需按上述过程计算即可。） 题目6： 求正整数n 的有序k 分拆的个数，要求第i 个分部量大于等于p i 。 解答：分拆的个数为：?? ? ? ? ??---+∑=111k p k n k i i ，其中（1≤i ≤k ）。 例如：9的有序3分拆，要求所有分部量都大于等于2，其个数为：
组合数学及其图论 1、一个图G 是指一个有序三元组（V （G ），E （G ），G ?），其中G ?是：________________. 关联函数 2、 是有40个点的简单图且 中任两个点之间有且只有1条路，则 。 39 3、只有一个顶点所构成的图称为：________________ 平凡图 4、如果H 是G 的子图，其中V （H ）=V （G ）和E （G ）=E （H ）至少有一个不成立，就称H 是G 的：_____________. 真子图 5、设G 是p 阶简单图，则__________________等号成立当且仅当G 是完全图。 q(G)≤p(p-1)/2 6、如果一条途径的_________与___________相同，就称这条途径为闭途径。 起点 终点 7、如果对图G=（V ，E ）的任何两个顶点u 与v ，G 中存在一条（u-v ）路，则称G 是___________否则称为是______________ 连通图、 非连通图 8、设G 是P 阶连通图，则__________________. q(G)≥p-1 9、若二分图 有Hamilton 回路，则 与 满足 。 10、若G 是2-边连通图，则G 有强连通的________________. 定向图 11、边数最少的连通图是 。
树 12、没有回路的连通图称为_______________. 树 13、的图是图或图。 平凡图，不连通图 14、树T的每一个非悬挂点都是T的 __________. 割点 15、二分图中若与满足，则必有完美对集。 16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个_______________. 生成树 17、设G是无环图，e是G的一条边，则 τ(G)=___________________________. τ （G－e）+τ (G·e) 18、是阶简单图，则，等号成立当且仅当是图。 ，完全图 2、 19、___________________________的生成树称为最优生成树。 连通赋权图中具有最小权 20、的一个对集是最大对集的充要条件是。 中无可扩路 21、一个有向图D，如果略去每条弧的方向时所得无向图是一棵树，就称D为_____________________. 有向树 22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹为G的 ________________. Euler环游 23、是简单图且，则。