组合数学第二章母函数与递推关系习题解答.pdf

《组合数学第二章母函数与递推关系习题解答.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.证明等式22222nnnn2n.012nn解：...48100202.求(1xx)中x项的系数.解：...3.有红、黄、蓝、白球各两个，绿、紫、黑的球各3个，问从中取出10个球，试问有多少种不同的取法？解：...4.求由A,B,C,D组成的允许重复的排列中AB至少出现一次的排列数目。解：...5.求n位四进制数中2和3必须出现偶次的数目。解：...6.试求由a,b,c三个文字组成的n位符号串中不出现aa图像的符号串的数目。解：...7.证明

2、序列C(n,n),C(n1,n),C(n2,n),的母函数为1.n1(1x)解：...8.证明C(n,n)C(n1,n)C(nm,n)C(nm1,n1)解：...21119.利用，2221236改善§4(2)的pn估计式。解：...10.8台计算机分给3个单位，第1单位的分配量不超过3台，第2单位的分配量不超过4台，第3个单位不超过5台，问共有几种分配方案？解：...11.证明正整数n都可以唯一地表示成不同的且不相邻的Fibonacci数之和。即naiFi,aiai1

3、0,ai0,1i2注意FF1是相同的Fibonacci数。12解：...12.设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点。这样的n个平面把空间分割成多少个不重叠的域？解：...13.相邻位不同为0的n位2进制数中一共出现了多少个0？解：...14.在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规则仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？解：...15.一书框中有m格，每格

4、各放n册同类的书，不同格放的书类型不同。现取出整理后重新放回，但不打乱相同类。试问无一本放在原来位置的方案数应多少？解：...16.设一矩形ABCD,其中1AB:AD(15)2作C1B1使得AB1C1D是一正方形。试证矩形B1C1CD和ABCD相似。试证继续这过程可得一和原矩形相似的矩形序列。B1解：...ABDCC117.平面上有两两相交，无三线共点的n条直线，试求这n条直线把平面分成多少个域？解：...18.在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象，求弦把圆分割成几部分？解：...19.求n

5、位二进制数相邻两位不出现11的数的个数。解：...20.从n个文字中取k个文字作允许重复的排列，但不允许一个文字连续出现三次，求这样的排列的数目。解：...444421.求123n的和。解：...10022.求矩阵31.02解：...23.求nnSnk(k1),Snk(k2),k0k0nSnk(k1)(k2).k0解：...24.在一个平面上画一个圆，然后一条一条地画n条与圆相交的直线。当r是大于1的奇数时，第r条直线只与前r-1条直线之一在圆内相交。当r是偶数时，第r

6、条直线与前r-1条直线在圆内部相交。如果无3条直线在圆内共点，这n条直线把圆分割成多少个不重叠的部分？解：...25.用an记具有整数边长周长为n的三角形的个数。（a）证明an3,当n是偶数，n2ann(1)2a,当n是奇数n34（b）求序列an的普通形母函数。解：...26.（a）证明边长为整数、最大边长为l的三角形的个数是12(l1)当l是奇数，4l(l2)当l是偶数。4（b）设fn记边长不超过2n的三角形的个数，而gn记边长不超过2n+1的三角形的个数，求fn和gn的表达式。解：.

7、..27.设nnkn1nkn0,an,bnk02kk02k1（a）证明aab,bab.n1nn1n1nn（b）求序列a与b的母函数。nn（c）用Fibonacci数来表示a与b。nn解：...28.设FF1,FFF121n1n2（a）证明FFFFF,nk1nknk1k1nk（b）证明FF的充要条件是nm。nm（c）证明FFFFFmnmn2mn6mn10Fmn1当n是奇数，Fmn2当n是偶

8、数。mn2.（d）证明(F,F)F,(m,n)为m,nmn(m,n)的最大公约数。解：...29.从1到n的自然数中选取k个不同且不相邻的数，设此选取的方案为f(n,k)。（a）求f(n,k)的递推关系。（b）用归纳法求f(n,k)。（c）若设1与n算是相邻的数，并设在此假定下从1到n的自然数中选取k个不同且不相邻的k个数的