组合数学第二章习题

1.证明等式.221022222nnnnnnn解：...2.求中项的系数.10084)1(xx20x解：...3.有红、黄、蓝、白球各两个，绿、紫、黑的球各3个，问从中取出10个球，试问有多少种不同的取法？解：...4.求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目。解：...5.求n位四进制数中2和3必须出现偶次的数目。解：...6.试求由a,b,c三个文字组成的n位符号串中不出现aa图像的符号串的数目。解：...7.证明序列的母函数为.)1(11nx),,2(),,1(),,(nnCnnCnnC解：...8.证明)1,1(),(),1(),(nmnCnmnCnnCnnC解：...9.利用，改善§4(2)的估计式。63121112222np解：...10.8台计算机分给3个单位，第1单位的分配量不超过3台，第2单位的分配量不超过4台，第3个单位不超过5台，问共有几种分配方案？解：...11.证明正整数n都可以唯一地表示成不同的且不相邻的Fibonacci数之和。即1,0,0,12iiiiiiaaaFan注意是相同的Fibonacci数。121FF解：...12.设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点。这样的n个平面把空间分割成多少个不重叠的域？解：...13.相邻位不同为0的n位2进制数中一共出现了多少个0？解：...14.在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规则仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？解：...15.一书框中有m格，每格各放n册同类的书，不同格放的书类型不同。现取出整理后重新放回，但不打乱相同类。试问无一本放在原来位置的方案数应多少？解：...16.设一矩形,其中作使得是一正方形。试证矩形和相似。试证继续这过程可得一和原矩形相似的矩形序列。)51(21:ADAB11BCDCAB11CDCB11ABCDABCD解：...ABCD1B1C17.平面上有两两相交，无三线共点的n条直线，试求这n条直线把平面分成多少个域？解：...18.在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象，求弦把圆分割成几部分？解：...19.求n位二进制数相邻两位不出现11的数的个数。解：...20.从n个文字中取k个文字作允许重复的排列，但不允许一个文字连续出现三次，求这样的排列的数目。解：...21.求的和。4444321n解：...22.求矩阵.2013100解：...23.求nknnknnknkkkSkkSkkS000).2)(1(),2(),1(解：...24.在一个平面上画一个圆，然后一条一条地画n条与圆相交的直线。当r是大于1的奇数时，第r条直线只与前r-1条直线之一在圆内相交。当r是偶数时，第r条直线与前r-1条直线在圆内部相交。如果无3条直线在圆内共点，这n条直线把圆分割成多少个不重叠的部分？解：...25.用记具有整数边长周长为n的三角形的个数。（a）证明是奇数当是偶数，当nnanaannnn,4)1(,2233（b）求序列的普通形母函数。nana解：...26.（a）证明边长为整数、最大边长为l的三角形的个数是（b）设记边长不超过2n的三角形的个数，而记边长不超过2n+1的三角形的个数，求和的表达式。是偶数。当是奇数，当lllll)2(4)1(412nfnfngng解：...27.设（a）证明（b）求序列与的母函数。（c）用Fibonacci数来表示与。10012,2,0nknnknkknbkknan.,111nnnnnnbabbaananbnanb解：...28.设（a）证明（b）证明的充要条件是。21121,1nnFFFFF1,11knFFFFFknkknknmnFFmn（c）证明.2211062nmnFnFFFFFFnmnmnmnmnmnm是偶数。当是奇数，当（d）证明为m,n的最大公约数。),(,),(),(nmFFFnmnm解：...29.从1到n的自然数中选取k个不同且不相邻的数，设此选取的方案为。（a）求的递推关系。（b）用归纳法求。（c）若设1与n算是相邻的数，并设在此假定下从1到n的自然数中选取k个不同且不相邻的k个数的方案数为，利用求。),(knf),(knf),(knf),(knf),(kng),(kng解：...30.设是第二类Stirling数。证明),(2knS).1,(),1(212mkSknmnSnmk解：...31.求下图中从A点出发到n点的路径数。A1234n解：...32.n位0,1符号串，求从左向右只在最后两位才出现0，0的符号串的数目。解：...33.试证.011111nnnnnFFFF解：...