组合数学引论课后答案.doc
- 文档编号:95887
- 上传时间:2023-04-28
- 格式:DOC
- 页数:49
- 大小:908KB
组合数学引论课后答案.doc
《组合数学引论课后答案.doc》由会员分享,可在线阅读,更多相关《组合数学引论课后答案.doc(49页珍藏版)》请在冰点文库上搜索。
习题二
2.1证明:
在一个至少有2人的小组中,总存在两个人,他们在组内所认识的人数相同。
证明:
假设没有人谁都不认识:
那么每个人认识的人数都为[1,n-1],由鸽巢原理知,n个人认识的人数有n-1种,那么至少有2个人认识的人数相同。
假设有1人谁都不认识:
那么其他n-1人认识的人数都为[1,n-2],由鸽巢原理知,n-1个人认识的人数有n-2种,那么至少有2个人认识的人数相同。
假设至少有两人谁都不认识,则认识的人数为0的至少有两人。
2.2任取11个整数,求证其中至少有两个数的差是10的整数倍。
证明:
对于任意的一个整数,它除以10的余数只能有10种情况:
0,1,…,9。
现在有11个整数,由鸽巢原理知,至少有2个整数的余数相同,则这两个整数的差必是10的整数倍。
2.3证明:
平面上任取5个坐标为整数的点,则其中至少有两个点,由它们所连线段的中点的坐标也是整数。
2.3证明:
有5个坐标,每个坐标只有4种可能的情况:
(奇数,偶数);(奇数,奇数);(偶数,偶数);(偶数,奇数)。
由鸽巢原理知,至少有2个坐标的情况相同。
又要想使中点的坐标也是整数,则其两点连线的坐标之和为偶数。
因为奇数+奇数=偶数;偶数+偶数=偶数。
因此只需找以上2个情况相同的点。
而已证明:
存在至少2个坐标的情况相同。
证明成立。
2.4一次选秀活动,每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”,至少有多少人参加才能保证必有100个人得到相同的结果?
证明:
根据推论2.2.1,若将3*(100-1)+1=298个人得到3种结果,必有100人得到相同结果。
2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。
那么至少取出多少水果后能够保证已经拿出20个相同种类的水果?
证明:
根据推论2.2.1,若将4*(20-1)+1=77个水果取出,必有20个相同种类的水果。
2.6证明:
在任意选取的n+2个正整数中存在两个正整数,其差或和能被2n整除。
(书上例题2.1.3)
证明:
对于任意一个整数,它除以2n的余数显然只有2n种情况,即:
0,1,2,…,2n-2,2n-1。
而现在有任意给定的n+2个整数,我们需要构造n+1个盒子,即对上面2n个余数进行分组,共n+1组:
{0},{1,2n-1},{2,2n-2},{3,2n-3},…,{n-1,n+1},{n}。
根据鸽巢原理,n+2个整数,必有两个整数除以2n落入上面n+1个盒子里中的一个,若是{0}或{n}则说明它们的和及差都能被2n整除;若是剩下n-1组,因为一组有两个余数,余数相同则它们的差能被2n整除,不同则它们的和能被2n整除。
证明成立。
2.7一个网站在9天中被访问了1800次,证明:
存在连续的3天,这个网站的访问量超多600次。
证明:
设网站在9天中访问数分别为a1,a2,...,a9其中a1+a2+...+a9=1800,
令a1+a2+a3=b1,a4+a5+a6=b2,a7+a8+a9=b3
因为(b1+b2+b3)/3>=600由推论2.2.2知,b1,b2,b3中至少有一个数大于等于600。
所以存在有连续的三天,访问量大于等于600次。
2.8将一个矩形分成5行41列的网格,每个格子涂1种颜色,有4种颜色可以选择,证明:
无论怎样涂色,其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。
证明:
首先对一列而言,因为有5行,只有4只颜色选择,根据鸽巢原理,则必有两个单元格的颜色相同。
另外,每列中两个单元格的不同位置组合有=10种,这样一列中两个同色单元格的位置组合共有10*4=40种情况。
而现在共有41列,根据鸽巢原理,无论怎样涂色,则必有两列相同,也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。
2.9将一个矩形分成(m+1)行列的网格每个格子涂1种颜色,有m种颜色可以选择,证明:
无论怎么涂色,其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。
证明:
(1)对每一列而言,有(m+1)行,m种颜色,有鸽巢原理,则必有两个单元格颜色相同。
(2)每列中两个单元格的不同位置组合有种,这样一列中两个同色单元格的位置组合共有种情况
(3)现在有列,根据鸽巢原理,必有两列相同。
证明结论成立。
2.10一名实验员在50天里每天至少做一次实验,而实验总次数不超过75。
证明一定存在连续的若干天,她正好做了24次实验。
证明:
令b1,b2,...,b50分别为这50天中他每天的实验数,并做部分和
a1=b1,a2=b1+b2,。
。
a50=b1+b2+...+b50.
由题,bi>=1(1<=i<=50)且a50<=75
所以1<=a1 考虑数列a1,a2,...,a50,a1+24,a2+24,a50+24,它们都在1与75+24=99之间。 由鸽巢原理知,其中必有两项相等。 由(*)知,a1,a2,...,a50互不相等,从而a1+24,...a50+24也互不相等,所以一定存在1<=i 所以从第i+1天到第j天这连续j-i天中,她正好做了24次实验。 2.11证明: 从S={1,3,5,…,599}这300个奇数中任意选取101个数,在所选出的数中一定存在2个数,它们之间最多差4。 证明: 将S划分为{1,3,5},{7,9,11}……,{595,597,599}共100组,由鸽巢原理知任意选取101个数中必存在2个数来自同一组,即其差最多为4. 2.12证明: 从1~200中任意选取70个数,总有两个数的差是4,5或9。 证明: 设这70个数为 a1,a2,…,a70, a1+4,a2+4,…,a70+4, a1+9,a2+9,…,a70+9, 取值范围209,共210个数 2.13证明: 对于任意大于等于2的正整数n,都有R(2,n)=n。 2.13证明: 要证R(2,n)=n,用红蓝两色涂色Kn的边。 当n=2时,R(2,2)=2,因为不管用红还是蓝色都是完全二边形。 假设当n=k时成立,即存在R(2,k)=k(没有一条红边,只有蓝边), 当n=k+1时,R(2,k+1) 若无红边,要想有完全k+1边形,必得有k+1个点,即R(2,k+1)=k+1。 证明成立。 习题三 3.1有10名大学生被通知参加用人单位的面试,如果5个人被安排在上午面试,5个人被安排在下午面试,则有多少种不同的安排面试的顺序? 解: 上午的5个人全排列为5! 下午的5个人全排列为5! 所以有,共14400种不同的安排方法。 3.2某个单位内部的电话号码是4位数字,如果要求数字不能重复,那么最多可有多少个号码? 如果第一位数字不能是0,那么最多能有多少个电话号码? 解: 由于数字不能重复,0-9共10个数字,所以最多有10*9*8*7=5040种号码;若第一位不能是0,则最多有9*9*8*7=4536种号码。 3.318名排球运动员被分成A,B,C三个组,使得每组有6名运动员,那么有多少种分法? 如果是分成三个组(不可区别),使得每组仍有6名运动员,那么有多少种分法? 解: 1)种 2)/3! 3.4教室有两排,每排8个座位。 现有学生14人,其中的5个人总坐在前排,4个人总坐在后排,求有多少种方法将学生安排在座位上? 解: 前排8个座位,5人固定,共种方法;后排8个座位,4人固定,共种方法;前排和后排还剩7个座位,由剩下的5人挑选5个座位,共种方法;则一共有种安排方法。 3.5将英文字母表中的26个字母排序,要求任意两个元音字母不能相邻,则有多少种排序方法? 解: 先排21个辅音字母,共有21! 再将5个元音插入到22个空隙中, 故所求为 (插入法) 3.6有6名先生和6名女士围坐一个圆桌就餐,要求男女交替就坐,则有多少种不同的排坐方式? 解: 6男全排列6! ;6女全排列6! ;6女插入6男的前6个空或者后6个空,即女打头或男打头6! *6! *2;再除以围圈重复得(6! *6! *2)/12=6! *5! 或 男6的圆排列为5! ,对每个男的排列,女要在他们之间的6个位置,进行线性排列6! (而不是5! )。 (圆排列可以通过线性排列来解决) 3.715个人围坐一个圆桌开会,如果先生A拒绝和先生B和C相邻,那么有多少种排坐方式? 解: 15人圆排列14! ; A与B相邻有2*14! /14=2*13! ; A与C相邻有2*14! /14=2*13! ; A与BC同时相邻有2*13! /13=2*12! ; 于是A不与B、C相邻的坐法共14! -2*13! -2*13! +2*12! (用到了容斥原理) 3.8确定多重集的11-排列数? 解: M的11排列=[M-{a}]的11排列+[M-{b}]的11排列+[M-{c}]的11排列,即=27720 当然了,容斥原理,生成函数也可以做。 3.9求方程,满足的整数解的个数。 解: 令 则有,由定理3.3.3,解个数为: 3.10书架上有20卷百科全书,从中选出4卷使得任意两本的卷号都不相邻的选法有多少种? 解: n=20,r=4, 证明见38页。 若卷号差为2,3,。 。 。 。 。 ,公式为? 3.11确定(2x-3y)5展开式中x4y和x2y4的系数。 解: 1): ,系数为-240 2): 系数为0。 3.12确定(1+x)-5展开式中x4的系数。 解: ,n=5,r=4,则系数为 3.13确定(x+2y+3z)8展开式中x4y2x2的系数。 解: 3.14证明组合等式: ,其中n,k为正整数。 解: 右边是(n+k+1)元集合上k个元素子集的个数,这些子集可分为以下k+1类: 第1类: k元子集中不含a1的子集有个; 第2类: k元子集中含a1而不含a2的子集是个; 第3类: k元子集中含a1和a2,而不含a3的子集是 …… 第k+1类: k元子集中含a1,a2,……,ak,而不含ak+1的子集是 由加法原理得证。 根据组合意义进行证明 3.15利用,求。 解: 首先有: (p51的(3)) 根据已知条件代入以上等式得: 又由 得, 则原式 3.16在一局排球比赛中,双方最终的比分是25: 11,在比赛过程中没有出现5平的比分,求有多少种可能的比分记录? 解: 根据题意,相当于求从点(0,0)到点(25,11)且不经过(5,5)的非降路径数,即为: 3.17 在一局乒乓球比赛中,运动员甲以11: 7战胜运动员乙,若在比赛过程中甲从来没有落后过,求有多少种可能的比分记录? 解: 根据题意,相当于求从点(0,0)到点(11,7)且从下方不穿过y=x的非降路径数,见58页,即为: 3.18把20个苹果和20个橘子一次一个的分发给40个幼儿园的小朋友,如果要求分发过程中任意时刻篮子中余下的两种水果数目都不相同(开始和结束时除外),求有多少种分法方法? 解: 根据题意,相当于求从点(0,0)到点(20,20)且不接触y=x的非降路径数,即为: n=20,则方法数为: 3.18计算和。 解: 1) 一个递推公式, 2) 3.19 (1)证明S(n,3)= 方法一: 先考虑3个盒子不同,要保证每个盒子非空: 总数为3n,排除到一个盒子为空和两个盒子为空的情况,即: 一个盒子为空(放到两个盒子去),例如第一个盒子为空,第二和第三不空: 3(2n-2) 两个盒子为空,例如第一个和第二盒子为空: 3*1 (3n-3(2n-2)-3)/3! 还可以直接考虑盒子相同。 (2)证明: 相当于n个不同球放到相同的n-2个盒子,每个盒子非空,至少为1个,这样使得剩余的2个球要到n-2个盒子,即使得一个盒子有3个,或有二个盒子都装2个球: 使得一个盒子有3个球: C(n,3) 有二个盒子都装2个球: C(n,4)C(4,2)/2! 3.21 (1)会议室中有2n+1个座位,现摆成3排,要求任意两排的座位都占大多数,求有多少种摆法? 解: 如果没有附加限制则相当于把2n个相同的小球放到3个不同的盒子里,有种方案,而不符合题意的摆法是有一排至少有n+1个座位。 这相当于将n+1个座位先放到3排中的某一排,再将剩下的2n-(n+1)=n-1个座位任意分到3排中,这样的摆法共有种方案,所以符合题意的摆法有: 可以用代数法 (2)会议室中有2n个座位,现摆成3排,要求任意两排的座位都占大多数,求有多少种摆法? 习题四 4.1 在1到1000之间不能被2,5和11整除的整数有多少个? 解: 设S是这1000个数的集合,性质是可被2整除,性质是可被5整除,性质是可被11整除。 ,, ,,, 4.3 一项对于A,B,C三个频道的收视调查表明,有20%的用户收看A,16%的用户收看B,14%的用户收看C,8%的用户收看A和B,5%的用户收看A和C,4%的用户收看B和C,2%的用户都看。 求不收看A,B,C任何频道的用户百分比? 解 4.2 求1到1000之间的非完全平方,非完全立方,更不是非完全四次方的数有多少个? 解: 设S是1000个数的集合, 性质是某数的完全平方, 性质是某数的完全立方, 性质是某数的完全四次方。 ,, ,,, 4.4某杂志对100名大学新生的爱好进行调查,结果发现他们都喜欢看球赛和电影、戏剧。 其中58人喜欢看球赛,38人喜欢看戏剧,52人喜欢看电影,既喜欢看球赛又喜欢看戏剧的有18人,既喜欢看电影又喜欢看戏剧的有16人,三种都喜欢看的有12人,求有多少人只喜欢看电影? 解: 由题意可得,P1,P2,P3分别表示喜欢看球赛、电影和戏剧的学生,相应的学生集合分别为A1,A2,A3,依题意,这100名大学生中每人至少有三种兴趣中的一种,则 所以可得既喜欢看球赛有喜欢看电影的人有 因此只喜欢看电影的人有 =52-(26+16)+12=22人 4.5 某人有六位朋友,他跟这些朋友每一个都一起吃过晚餐12次,跟他们中任二位一起吃过6次晚餐,和任意三位一起吃过4次晚餐,和任意四位一起吃过3次晚餐,任意五位一起吃过2次晚餐,跟六位朋友全部一起吃过一次晚餐,另外,他自己在外吃过8次晚餐而没碰见任何一位朋友,问他共在外面吃过几次晚餐? 4.6 计算多重集S={4•a,3•b,4•c,6•d}的12-组合的个数? 解: 令 其中,, ,, ,,,,,, 4.7 计算多重集S={∞•a,4•b,5•c,6•d}的10-组合的个数? 解: 将,其他思想同上题。 其中,,,,,,,,,, 4.8 用容斥原理确定如下两个方程的整数解的个数。 1)x1+x2+x3=15,其中x1,x2,x3都是非负整数其都不大于7; 2)x1+x2+x3+x4=20,其中x1,x2,x3,x4都是正整数其都不大于9; 解: 1)与{7a,7b,7c}的15组合数相等,为28 2) ,因此用代替,代替,代替,代替有 与{8a,8b,8c,8d}的16组合数相等为489 4.9定义D0=1,证明: 证明: 考虑到n个数的全排列包含错位排列和非错排,其中表示在n个数中任选k个,这个k个数构成了一个错排,而剩余的n-k个数还在原来的位置。 ,显然 (另一种方法: 组合分析法) 4.10证明: Dn满足: n为整数且n3 证明: 由定理4.3.1得 4.11有10名女士参加一个宴会,每人都寄存了一顶帽子和一把雨伞,而且帽子、雨伞都是互不相同的,当宴会结束的离开的时候,如果帽子和雨伞都是随机的还回的,那么有多少种方法使得每位女士拿到的物品都不是自己的? 解: 由于帽子全部拿错和雨伞全部拿错是两个相互独立的事件,设帽子全错为 雨伞全错为解 4.13计算棋盘多项式R()。 解: R()=x*R()+R() =x*(1+3x+x2)+(1+x)*R() =x3+3x2+x+(1+x)[xR()+R()] =x3+3x2+x+(1+x)[x(1+x)+(1+4x+2x2)] =5x3+12x2+7x+1 4.14有A,B,C,D,E五种型号的轿车,用红、白、蓝、绿、黑五种颜色进行涂装。 要求A型车不能涂成黑色;B型车不能涂成红色和白色;C型车不能涂成白色和绿色;D型车不能涂绿色和蓝色;E型号车不能涂成蓝色,求有多少种涂装方案? 解: ABCDE 红 白 蓝 绿 黑 1.若未规定不同车型必须涂不同颜色,则: 涂装方案 2.若不同车型必须涂不同颜色,则: 禁区的棋盘多项式为: 1+8x+22x2+25x3+11x4+x5 所以: 5! -8*4! +22*3! -25*2! +11*1! -1=20 4.15计算 (舍) 4.16计算T={∞•1,∞•2,∞•3,∞•4}的长度为4的圆排列数。 (舍) 补: (1)在1~2000中能被7整除,但不能被6和10整除的个数。 证明: A1,A2,A3表示被6、7和10整除的数的子集,所求: =219 (2)在1~2000中至少被2、3和5两个数整除的数的个数? =534 习题五 5.1求如下数列的生成函数。 (1); (2); (3);(4); (5);(6); 解: (1)由已知得 故 (2)设则 又因为故 或者 (3) (4) (5) (6) 5.2求如下数列的指数生成函数。 (1); (2); (3); 解: (1) (2) (3) 则故 5.3已知数列的生成函数是,求. 解: 而 故 5.4求展开式中的系数是多少? (1)若取0,则取5个,这种情况有种; (2)若取1,则取3个,这种情况有或; (3)若取2,则取1个,这种情况有; 故系数为=91457520。 其他方法 5.5三个人每个人投一次骰子,有多少种方法使得总点数为9? 解: 这相当于有9个球,用隔板将其分成3组,共有种方法。 又因为这次点数小于等于6,即711,171和117三种情况不符,故共有25种方法。 5.6求在102和104之间的各位数字之和等于5? 解: (1)三位数时,相当于的非负整数解的个数。 故中为展开式的系数。 (2)四位数时,相当于的非负整数解的个数。 5.7一个1×n的方格图形用红、蓝、绿和橙四种颜色涂色,如果有偶数个方格被涂成红色,还有偶数个方格被涂成绿色,求有多少种方案? 解: 涂色方案数为则: 因此: ,所以有种方案。 5.8有4个红球,3个黄球,3个蓝球,每次从中取出5个排成一行,求排列的方案数? 解: 设每次取出的k个球的排列数为,数列的指数型生成函数为则有 而我们所求的是的系数。 故有。 5.9计算用3个A,3个G,2个C和1个U构成长度为2不同的RNA链的数量。 解: 中的系数,有=15. 5.10 计算和。 解: (1)构造多项式则即的系数,则,故。 (2),的非负整数解为(0,0,4),(1,2,3),(0,2,2),(0,3,1),(0,4,0),(1,0,3),(1,1,2),(1,2,1),(1,3,0),(2,0,2),(2,1,1),(2,2,0),(3,0,1),(3,1,0),(4,0,0) 5.11设表示把元集划分成非空子集的方法数,我们称为Bell数。 证明: 。 证明: 当有1个盒子时,方法数, 当有2个盒子时,方法数, 当有k个盒子时,方法数, 当有n个盒子时,方法数, 当有n+1个盒子时,至少有一个空盒,不符。 故 5.12有重为1g的砝码重为1g的3个,重为2g的4个,重为4g的2个,求能称出多少种重量? 解: 即求多项式中展开式有多少项 (除1外),原多项式 故共有19种重量。 5.13已知数列的指数生成函数是,求. 解: 设 ak=5,k不等于2 ak=7,k=2 补: 3个l,2个2,5个3这十个数字能构成多少个4位数偶数。 解问题是求多重集S={3个1,2个2,5个3}的4排列数,且要求排列的末尾为2(偶数)。 可以把问题转化成求多重集S={3个1,1个2,5个3}, 其指数生成函数为 展开后得的系数为20,所以能组成20个4位数的偶数。 习题六 6.1设,建立的递推关系并求解。 解: 6.2求解递推关系: (1) 解: (2) 解: (3) 解: (4) 解: 6.3求解递推关系: (1) 解: (2) 解: (3) 解: (4) 解: 6.4求解递推关系: (1) (2) (3) (4) 6.5平面上有n条直线,它们两两相交且沿有三线交于一点,设这n条直线把平面分成个区域,求的递推关系并求解. 解: 设n-1条直线把平面分成个区域,则第n条直线与前n-1条直线都有一个交点,即在第n条直线上有n-1个交点,并将其分成n段,这n段又把其所在的区域一分为二。 6.6一个的方格图形用红、蓝两色涂色每个方格,如果每个方格只能涂一种颜色,且不允许两个红格相邻,设有种涂色方案,求的递推关系并求解. 解: 6.7核反应堆中有和两种粒子,每秒钟内1个粒子可反应产生出3个粒子,而1个粒子又可反应产生出1个粒子和2个粒子.若在t=0s时刻反应堆中只有1个粒子,求t=100s时刻反应堆里将有多少个粒子和粒子,共有多少个粒子. 解: 设t时刻反应堆中粒子数为,粒子数为 在t-1时刻 在t时刻 补: 上有n个大圆,任意两个大圆皆相交,且没有三个大圆通过同一点,则这些大圆所形成的区域数f(n)满足的递推关系是 f(n+1)=f(n)+2n,n>1, f (1)=2 f(n)可以由f(n)来生成,当在f(n)个大圆的基础上,在球面上再加上第n+1个大圆时,它同前n个大圆共得到2n个交点(因无三个大圆相交于一点),而每增加一个交点就增加一个新的面,故共增加2n个面。 所以有f(n+1)=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 引论 课后 答案