第一章习题-组合数学课件.ppt

《第一章习题-组合数学课件.ppt》由会员分享，可在线阅读，更多相关《第一章习题-组合数学课件.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.证任一正整数n可唯一地表成如下形式：n=aii!,0aii,i1,2,。解2.证 nC(n-1,r)=(r+1)C(n,r+1).并给出组合意义。解3.证kC(n,k)=n2 。解4.有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组的最大数。问有多少种方案？解i1i1kn-15.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。解6.试求从1到1000000的整数中，0出现了多少次？解7.n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？解8.n个完全一样的球，放到r个有标志的盒子,n

2、r,要求无一空盒，试证其方案数为().解n-1r-19.设 n=p1 p2 pl,p1、p2、pl是l个不同的素数，试求能整除尽数n的正整数数目.解10.试求n个完全一样的骰子掷出多少种不同的方案？解11.凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少个点？又把所有对角线分割成多少段？解12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。解a1 a2 al13.统计力学需要计算r个质点放到n个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。(a)Maxwell-Boltzmann假定：r个质点是不同的，任何盒子可以放任意数个.(b)B

3、ose-Einstein假定：r个质点完全相同，每一个盒子可以放任意数个.(c)Fermi-Dirac假定：r个质点都完全相同，每盒不超过一个.解17.证明：解()()+()()+()()+()()=2()18.从n个人中选r个围成一圆圈，问有多少种不同的方案？解19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。(解略)20.(a)按照第19题的要求，写出邻位对换法(排列的生成算法之二)的相应算法。(b)写出按照邻位对换法由给定排列生成其下一个排列的算法。(解略)m0mnm1m2mnmnm-1n-1m-2n-2m-n 0n21.对于给定的正整数n,证明当2

4、2.(a)用组合方法证明 和 都是整数.(b)证明 是整数.解23.(a)在2n个球中,有n个相同,求从这2n个 球中选取n个的方案数。(b)在3n+1个球中，有n个相同，求从这3n+1个球中选取n个的方案数。解k=n-1 2n2,n+1 2时，C(n,k)是最大值。解若n是奇数若n是偶数(2n)!(3n)!2 2 3n n n(n)!(n!)n+1224.证明在由字母表0,1,2生成的长度为n的字符串中.(a)0出现偶数次的字符串有个；(b)()2+()2 +()2 =，其中q=2 .解25.5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？解n0n2nq3+1 23

5、+1 2nn-1n-qnnn2习题解答1.证：证：对n用归纳法。题先证可表示性：当n=0,1时，命题成立。假设对小于n的非负整数，命题成立。对于n,设k!n(k+1)!,即0n-k!kk!由假设对n-k!,命题成立，设n-k!=aii!，其中akk-1,n=aii!+k!，命题成立。i=1ki=1k再证表示的唯一性：设n=aii!=bii!,不妨设ajbj,令j=maxi|aibiajj!+aj-1(j-1)!+a11!=bjj!+bj-1(j-1)!+b11!,(aj-bj)j!=(bi-ai)i!j!ii!|bi-ai|i!(bi-ai)i!另一种证法：令j=mini|aibiaii!=b

6、ii!,两边被(j+1)!除,得余数ajj!=bjj!,矛盾.i=1ki=1ki=1j-1i=1j-1i=1j-1i=1j-1ijij3.证：证：题 设有n个不同的小球，A、B两个盒子,A盒中恰好放1个球,B盒中可放任意个球。有两种方法放球：先从n个球中取k个球(k1),再从中挑一个放入A盒,方案数共为kC(n,k),其余球放入B盒。先从n个球中任取一球放入A盒，剩下n-1个球每个有两种可能，要么放入B盒，要么不放，故方案数为n2 .显然两种方法方案数应该一样。k=1nn-16.解：解：首先所有数都用6位表示，从000000到999999中在每位上0出现了10 次,所以0共出现了610 次,0

7、出现在最前面的次数应该从中去掉，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共出现了 610 10 10 10 10 10 10+6=488895次。555432105543210题7.解：解：把n个男、n个女分别进行全排列，然后按乘法法则放到一起，而男女分别在

8、前面,应该再乘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)个方案。证毕。题2211.(续前页)根据图论知识，每个对角线交点有4个度，每个顶点去掉与相邻两个顶点的连线还有7个度，可以得到210 4+10

9、7 212.证：证：根据第9题的结论，n=p1 p2 pl ,能被(a1+1)(a2+1)(al+1)个数整除，而n=p1 p2 pl ,能被(2a1+1)(2a2+1)(2al+1)个数整除，2ai+1为奇数(0il)，所以乘积为奇数。证毕。题=455条边 题a1 a2 al22a1 2a2 2al13.解解：题(a)每个质点放入盒子都有n种选择，r个质点共有r 种不同的图案。(b)可重组合，共有C(n+r-1,r)种图案。(c)一般组合问题，共有C(n,r)种图案。14.解：解：题 其中有2个母音可构成C(21,4)C(5,2)6!个字。其中有2个母音可构成C(21,3)C(5,3)6!个

10、字。n15.解：题 如图：-r-1 -1 0 m-n xymA(-1,m)B(m-n,m)可看作是格路问题：左边第i项为从点C到点(-1,i)直接经过(0,i)的路径,再到点B的所有路径数。左边所有项的和就是从点C到B的所有路径数即为右边的意义。C(-r-1,0)16.解：解：C(n+1,r+1)是指从n+1个元素a1,a2,an+1中任取r+1个进行组合的方案数。左边：若一定要选an+1,则方案数为C(n,r).若不选an+1,一定要选an,则方案数为C(n-1,r).若不选an+1,an,ar+2,则方案数为C(r,r).题 所有这些可能性相加就得到了总方案数。17.证：证：组合意义,右边

11、：m个球,从中取n个,放入两个盒子,n个球中每个球都有两种放法,得到可能的方案数。左边：第i项的意义是一个盒子中放i个,另一个盒子放n-i个,所有的方案数相加应该等于右边。17.(续前页)数学证明：左边=C(m,k)C(m-k,n-k)=C(m,n)=2 C(m,n)=右边 证毕。题k=0n m!(m-k)!k!(m-k)!(n-k)!(m-n)!k=0nk=0n m!n!k!n!(n-k)!(m-n)!n!k!(n-k)!k=0nn22.证：证：(a)设有2n个不同球放入n个不同的盒子里，每盒两个，这个方案数应该是整数。对2n个球进行排列得到方案数为(2n)!。而把2个球放入同一个盒子里不计

12、顺序，应该把全排列数除掉这些重复计算的次数，n个盒子内部的排列共重复计算了2 次。得到2n个不同球放入n个不同的盒子里，每盒两个的方案数(2n)!/2 若有3n个不同的球,放入n个不同盒子,故同理得(3n)!/(3!)是整数。nnn22.(接上页)(b)有n 个不同的球，放入n个相同的盒子里，每盒n个，求方案数，方案数应该是一个整数。按前面(a)的方法，应该得到(n)!/(n!)是整数。另外由于n个盒子相同，放入不同的盒子是没有区别的，应该把n个盒子的排列数n!除去。因此得到(n)!/(n!)是整数。题2n2n+123.解解：题(a)相当于从n个不同的小球中分别取出m个小球(0mn)，再从n个

13、相同的小球中取出n-m个小球。共有方案：C(n,0)+C(n,1)+C(n,n)=2 种。(b)相当于从2n+1个不同的小球中分别取出m个小球(0mn)，再从n个相同的小球中取出n-m个小球。共有方案：C(2n+1,0)+C(2n+1,1)+C(2n+1,n)种。n 25.解：解：当使用第1台机器的学生为n个时，使用第2台机器的学生也为n,从m个学生中选出2n个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)(m-2n)。所以总的方案数为C(m,2n)C(2n,n)(m-2n)题26.解：解：转化为格路问题(弱领先条件),即从(0,0)到(n,n),只能从

14、对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1).题3n=0q327解：解：设从1 n中选取互不相邻的k个数的方案数为g(n,k),若选n，则方案数为g(n-2,k-1),若不选n则方案数为g(n-1,k)。显然，g(n,k)=g(n-2,k-1)+g(n-1,k).且只有当n2k-1时，g(n,k)0,否则g(n,k)=0.可给定初始值g(2k-1,k)=1,g(2k-2,k)=0。题28解：解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：