第3章作业

练习3.13。学校为学生提供3门计算机硬件课程，4门计算机程序设计语言课程。问：（1）如果学生可以且只可以在这两类课程中选一门课程，学生有多少种选择方式？（2）如果学生可以且只可以在这两类课程中各选一门课程，学生有多少种选择方式？解：（1）3+4=7种方式。（2）3*4=12种方式。4．在1000-9999之间有多少个各位数字互不相同的奇数。解：四位数的奇数其末尾数有C(5,1)种可能。再考虑首位数，首位数不能与末尾数相同共有C(8,1)种可能，再考虑中间两位数分别有C(8,1)和C(7,1)种可能。据乘法原理，C(5,1)*C(8,1)*C(8,1)*C(7,1)=2240为所求。7．某学院语言学系有200学生，他们至少要选修德、英、法三种语言中的一种。已知这些学生中有90人学德语，130人学英语，84人学法语，30人学法德语，40人学法英语，50人学德英语。问同时学三种语言的学生有多少？仅学英语的人有多少？三种语言都不学的人有多少？解：假设学德语人的集合为A，学英语的人的集合为B,学法语的人的集合为C.由题意知|A∪B∪C|=200，|A|=90，|B|=130，|C|=84，|A∩C|=30，|B∩C|=40，|A∩B|=50。由容斥原理得：同时学三种语言的学生数为：|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|A∩C|+|B∩C|=16。由文氏图分析得到：仅学英语的人数为：56||||||||CBAABCBBCBA三种语言都不学的人数为0（因为每个人都至少要学一种语言）。练习3.23．某产品加工需要“甲乙丙丁戊”五道工序。（1）规定工序丁必须紧接着工序丙安排加工，五道工序的安排方法有多少种？（2）固定工序乙必须安排在工序戊的前面加工，五道工序的安排方法有多少种？解：（1）P（4，4）=24。（2）不加限制时，共有5！中安排方法，乙在戊之前和乙在戊之后的排法是相等的，所以满足条件的排法有5！/2=60种。4．今有12个人围着圆桌就座，如果其中两个人不愿座在相邻的位置上。问有多少种不同的坐法。解：不考虑限制时，n=12的圆排列数为11！。假如不愿坐在一起的人为A和B。当A和B坐在一起时，则相当于n=11的圆排列，其排列数为10！，当A和B坐在一起时分两种情况即AB和BA，那么A和B不坐在一起的排列数为11！-2*10！=9*10！6．一个俱乐部有10名男成员，12名女成员，现从中选出4人组成一个委员会，若（1）至少要有2名女成员。（2）除上述要求外，又指定M,N两女士不能同时入选。那么，有多少种不同的选法。解：（1）方法一：至少2名女成员，分以下三种情况：2男2女，1男3女，0男4女。C(12,2)*C(10,2)+C(12,3)*C(10,1)+C(12,4)=5665方法二：至少2名女成员，其对应的情况是“最多有1名女成员”：4男0女，3男1女。C(22,4)-（C(10,4)+C(10,3)*C(12,1)）=5665(2)方法一：从上述方案中去掉M,N两位女士同时入选的情况，若M和N同时入选，那么另外两名就从10名男士和10名女士中选出，选法数为C(20,2)(或者C(10,2)+C(10,1)*C(10,1)+C(10,2))=190.所以符合题目要求的选法数为5665-190=5475。方法二：M,N两女士不能同时入选，分两种情况：A:M和N都不选有C(10,2)C(10,2)+C(10,1)C(10,3)+C(10,4)=3435种选法。B：M和N中只选一个有2（C(10,2)C(10,1)+C(10,1)C(10,2)+C(10,3)）=2040种选法。所以满足条件的选法有3435+2040=5475种选法。练习3.32．r个有区别的球，放入n个有区别的盒子，盒子内球数不限，可以为0。问有多少种不同的放置方法。解：第一个球可以放到n个盒子中的任何一个，有n种方法。第二个球同样也有n种放法。。。。第r个球也有n种方法。由乘法原理，总共有nr种放置方法。3．n个有区别的球放入k个有区别的盒子B1,B2,…,Bk,要求在盒子Bi中放置ni个球，i=1，2，。。。，k，且n=n1+n2+…+nk.证明：放置的不同方式有n！/（n1！n2!...nk!）.证明：首先从n个球中取出n1个放入B1中，有C(n,n1)中方法，再从余下的n-n1中选n2个放入B2中，共有C(n-n1,n2)种方法，。。。。，最后从剩下的n-n1-n2-…-nk-1(=nk)中取出nk个放入Bk中，有C(n-n1-n2-…-nk-1,nk)种选法。由乘法原理得到放置的不同方式有!!!!)!(!)!()!(!)!()!(!!,,,21121121212111121211kkkkkkknnnnnnnnnnnnnnnnnnnnnnnnnnnnnCnnnCnnC4．某大楼要排成一行地悬挂15面彩旗，其中红黄蓝绿橙五色各3面。问（1）这些彩旗有多少种不同的排列方法。（2）如不允许有两面蓝旗相邻，又有多少种排列方法。解(1)多重集合的全排列问题，15！/（3！3！3!3！3！）(2)方法一：若两面蓝旗相邻，则可以把这两面蓝旗看作一面蓝旗，此一面蓝旗可以和其余任何一面相邻，那么其排列数为14！/（3！3！3！3！2！）。但是这样会把三面蓝旗相邻的情况多算了一次，三面蓝旗相邻的排列有13！/（3!3!3!3！）。所以满足题意要求的排列有15！/（3！3！3!3！3！）-(14！/（3！3！3！3！2！）+13！/（3!3!3!3！）)=（22*13！）/（6^4）方法二：先排除蓝旗之外的其他12面旗，共有12！/（3！3！3！3！）种排法。因为不允许两面蓝旗在一起，所以所有的蓝旗都不能连续排，只能在上述12面旗之间插空，也就是在13个空位中找三个空放三面蓝旗即可。据乘法原理，得到（12！/（3！3！3！3！））C（13，3）6．求方程x1+x2+…+x4=14的整数解。要求(1)0=x1,…,x4=6;(2)1=x1,….,x4=8.解：(1)问题相当于求集合S={6a,6b,6c,6d}的r=14的组合数。因为S的每个14组合都含有x1个a，x2个b，x3个c，x4个d，其中x1+x2+…+x4=14,而且满足0=x1,…,x4=6。类似于课本41页例3.12的做法，得到C(14+4-1,14)-4C(7+4-1,7)+6*1-4*0+0=206(2)令y1=x1-1,…,y4=x4-1.则原方程化为y1+y2+…+y4=10,其中0=y1,….,y4=7.所以，此问题相当于求集合{7a,7b,7c,7d}的r=10的组合数。类似于课本41页例3.12的做法，得到C(10+4-1,10)-4C(2+4-1,2)+6*0-4*0+0=2467．n个相同的球放入r个有标记的盒子中（r=n），使得没有一个盒子是空的。证明：放置方法数为C（n-1,r-1）证明：方法一：可以把这n个球排成一行，任两个相邻的球之间都有一个挡板隔开，总共有n-1个挡板。从这n-1个挡板中任取r-1个挡板，把这些球分成r段，且每段至少一个球。每段对应一个盒子，则满足题意的放置方法有C(n-1,r-1)方法二：因为盒子不能空，所以每个盒子先放一个球。然后把剩下的n-r个球任意的放到r个盒子中，因为此时每个盒子中的球数不限，这相当于求x1+x2+…+xr=n-r的自然数解的个数，即C(n-r+r-1,n-r)=C(n-1,n-r)=C(n-1,r-1)9。计算由数字1，1，2，3，3，4可以组成多少个四位数。解：问题相当于求重集S={1,1,2,3,3,4}的4排列数。这样的4位数有以下几种情况：（1）无重复数字。只能是1，2，3，4这四个数字的排列，有4！个。（2）有两个1，但是无两个3。因为已有2个1，所以剩下的两个数从2，3，4中选，共C(3,2)种选法。这样的四个数字的排列数为4！/（2!1!1!1!）=12。所以这种情况下的四位数有12C(3,2)=36个。（3）有两个3但是无两个1。类似上面的分析，这种情况下的四位数有36个。（4）有两个3又有两个1。这样四个数字都确定了，其排列数有4！/（2！2！）=6个。所以满足条件的四位数总共有4!+36+36+6=102个。11．解法一：（类似于课本41页例3.12）本题可以转化为计算重集S={6a,7b,3c}的12-组合数.T={∞a,∞b,∞c}的12组合数为C(3+12-1,12)=C(14,12)=91.令P1表示T的12组合中多于6个a的组合。|P1|=C(5+3-1,5)=C(7,5)=21.令P2表示T的12组合中多于7个b的组合。|P2|=C(4+3-1,4)=C(6,4)=15.令P3表示T的12组合中多于3个c的组合。|P3|=C(8+3-1,8)=C(10,8)=45.|P1∩P2|=0,|P1∩P3|=3,|P2∩P3|=1,|P1∩P2∩P3|=0.由容斥原理得到：321PPP=91-21-15-45+0+3+1-0=14.所以满足题目要求的选法有14种。解法二：（类似于课本41页例3.12）本题可以转化为计算重集S={6a,7b,3c}的4-组合数.T={∞a,∞b,∞c}的4组合数为C(3+4-1,4)=C(6,4)=15.令P1表示T的4组合中多于6个a的组合。|P1|=1.令P2表示T的4组合中多于7个b的组合。|P2|=0.令P3表示T的4组合中多于3个c的组合。|P3|=1.|P1∩P2|=|P1∩P3|=|P2∩P3|=|P1∩P2∩P3|=0.由容斥原理得到：321PPP=15-1=14.所以满足题目要求的选法有14种。练习3.41．用以下方式解下列递归关系式：先考虑前几个值，并推测解的公式，然后用数学归纳法证明你得到的公式。（1）H(0)=1,H(n)=3H(n-1)计算H(0)=1,H(1)=3,H(2)=9,H(3)=27推测：H(n)=3n证明：归纳基础。当n=0时，H(0)=30=1,成立。归纳推理。假设n=k时，H(k)=3k当n=k+1时，H(k+1)=3H(k)=3*3k=3k+1(3)H(0)=0,H(n)=-H(n-1)+1计算H(0)=0,H(1)=1,H(2)=0,H(3)=1,推测：H(n)=(1-(-1)n)/2.（或者H(n)=1(n为奇数)，H(n)=0(n为偶数)）证明H(n)=(1-(-1)n)/2：归纳基础：当n=0时，H(0)=(1-1)/2=0,成立。归纳推理：假设当n=k时，H(k)=(1-(-1)k)/2.当n=k+1时，H(k+1)=-H(k)+1=-(1-(-1)k)/2+1=(1-(-1)k+1)/2.证明H(n)=1(n为奇数)，H(n)=0(n为偶数)：归纳基础：当n=0时，H(0)=0,成立。归纳推理：假设当n=k时，命题成立.当n=k+1时，若k为奇数，则H(k+1)=-H(k)+1=-1+1=0（k+1为偶数）.若k为偶数，则H(k+1)=-H(k)+1=-0+1=1（k+1为奇数）.3.一楼梯有n级台阶，某人由下向上走。若每一步只能跨一级或两级楼梯，问：他从地面走到第n级楼梯有多少种走法？解：用h(n)表示从地面走到第n级楼梯的走法数。显然h(1)=1,h(2)=2,h(3)=3.为了从地面走到第n级楼梯，有以下两种走法。先走到第n-1级楼梯然后再走一级上来，或者先走到第n-2级楼梯，再走一个两级上来。所以递归关系式为h(n)=h(n-1)+h(n-2).求解此递归关系式。由其特征方程x2-x-1=0得到两个特征根251,251,从而得到通解为nnbbnh251251)(21，结合初值h(1)=1,h(2)=2，得到1055,105521bb，从而所求的解为nnnh