组合数学北大教材习题 - answer

第一章习题

1.证任一正整数n可唯一地表成如下形式:

2.证 nC(n-1,r)=(r+1)C(n,r+1).并给出组合意义。

,0≤ai≤i,i＝1,2,…。

3.证。

4.有n个不同的整数，从中取出两组来，要求第一组数里的最小数大于第二组的最大数。问有多少种方案？ .

5.六个引擎分列两排，要求引擎的点火的次序两排交错开来，试求从一特定引擎开始点火有多少种方案。

6.试求从1到1000000的整数中，0出现了多少次？

7.n个男n个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？

8.n个完全一样的球，放到r个有标志的盒子,n≥r,要求无一空盒，试证其方案数为 9.设

.

,p1、p2、…、pl是L个不同的素数，试求能整除尽数n的正整数数目.

10.试求n个完全一样的骰子掷出多少种不同的方案？

11.凸10边形的任意三个对角线不共点，试求这凸10边形的对角线交于多少个点？又把所有对角线分割成多少段？

12.试证一整数是另一个整数的平方的必要条件是除尽它的数目为奇数。

13.统计力学需要计算r个质点放到n个盒子里去,并服从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的。

(a)Maxwell-Boltzmann假定：r个质点是不同的，任何盒子可以放任意数个. (b)Bose-Einstein假定：r个质点完全相同，每一个盒子可以放任意数个. (c)Fermi-Dirac假定：r个质点都完全相同，每盒不超过一个.

14.从26个英文字母中取出6个字母组成一字，若其中有2或3个母音，问分别可构成多少个字(不允许重复)？

15.给出

的组合意义.

16.给出

的组合意义。

17.证明:

18.从n个人中选r个围成一圆圈，问有多少种不同的方案？

19.分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法。

20.(a)按照第19题的要求，写出邻位对换法(排列的生成算法之二)的相应算法。 (b)写出按照邻位对换法由给定排列生成其下一个排列的算法。

21.对于给定的正整数n,证明当

22.(a)用组合方法证明

和

时，C(n,k)是最大值。

(n2)!

都是整数. (b)证明是整数. n?1

(n!)

23.(a)在2n个球中,有n个相同,求从这2n个球中选取n个的方案数。

24.证明在由字母表{0,1,2}生成的长度为n的字符串中.

(a)0出现偶数次的字符串有个；

(b)，其中.

25. 5台教学机器m个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？

26.在由n个0及n个1构成的字符串中，任意前k个字符中，0的个数不少于1的个数的字符串有多少？

27.在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？

28.(a)在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个? (b)在m个0，n个1组成的字符串中,出现01或10的总次数为k的，有多少个？

第二章习题

?n??n??n??n??2n????????????...??1.证明等式??0??1??2??n??n?? ??????????2.求(1+x4+x8)100中x20项的系数.

3.有红、黄、蓝、白球各两个，绿、紫、 黑的球各3个，问从中取出10个球，试问 有多少种不同的取法？

4.求由A,B,C,D组成的允许重复的排列中 AB至少出现一次的排列数目。 5.求n位四进制数中2和3必须出现偶次的数目。

6.试求由a,b,c三个文字组成的n位符号串 中不出现aa图像的符号串的数目。

7.证明序列 C(n,n),C(n+1,n),C(n+2,n),的母函数为

...

22221?1?x?n?1。

8.证明C(n,n)+C(n+1,n)+ … + C(n+m,n)=C(n+m+1,n+1).

111?29.利用2?2?2??? ，改善 §4(2) 的pn估计式。

6123

10. 8台计算机分给3个单位，第1单位的分配量不超过3台，第2单位的分配量不超过4台，第3个单位不超过5台，问共有几种分配方案？

11. 证明正整数n都可以唯一地表示成不同的且不相邻的Fibonacci数之和。即

n??aiFi, aiai?1?0, ai?0,1.

i?2注意F1=F2=1是相同的Fibonacci数。

12. 设空间的n个平面两两相交，每3个平面有且仅有一个公共点，任意4个平面都不共点。这样的n个平面把空间分割成多少个不重叠的域？

13. 相邻位不同为0的n位2进制数中一共出现了多少个0？

14. 在Hanoi塔问题中，在柱A上从上到下套着n个圆盘，其编号依次从1到n。现要将奇数编号与偶数编号的圆盘分别转移到柱B和柱C上。转移规则仍然是每次移动一个，始终保持上面的比下面的小。一共要移动多少次？

15. 一书框中有m格，每格各放n册同类的书，不同格放的书类型不同。现取出整理后重新放回，但不打乱相同类。试问无一本放在原来位置的方案数应多少？

16. 设一矩形ABCD,其中

作C1B1使得AB1C1D是一正方形。试证矩形B1C1CD和ABCD相似。试证继续这过程可得一和原矩形相似的矩形序列。

17. 平面上有两两相交，无三线共点的n条直线，试求这n条直线最多把平面分成多少个域？

18. 在一圆周上取n个点，过一对顶点可作一弦，不存在三弦共点的现象，求弦把圆分割成几部分？

19. 求n位二进制数相邻两位不出现11的数的个数。

20. 在n个文字，长度为k的允许重复的排列中，不允许一个文字连续出现三次，求这样的排列的数目。

444...4

21. 求1+2+3++n的和。

?3?1?22. 求矩阵??02????

23. 求

100。

Sn??k(k?1),Sn??k(k?2),

k?0nk?0nn

Sn??k(k?1)(K?2)k?0

24. 在一个平面上画一个圆，然后一条一条地画n条与圆相交的直线。当r是大于1的奇数时，第r条直线只与前r-1条直线之一在圆内相交。当r是偶数时，第r条直线与前r-1条直线在圆内部相交。如果无3条直线在圆内共点，这n条直线把圆分割成多少个不重叠的部分？

25. 用an记具有整数边长周长为n的三角形的个数。

当n是偶数，?an?3,?n?1（a）证明 an?? n???1?2an?3?，当n是奇数?4?（b）求序列{an}的普通形母函数。

26.

（a）证明边长为整数、最大边长为L的三角形的个数是

1(L?1)2 当L是奇数， 41(L?2)L 当L是偶数 4

（b）设fn记边长不超过2n的三角形的个数，而gn记边长不超过2n+1的三角形的个数，求fn和gn 的表达式。

n?1n?kn?k27. 设 n?0,an??(),bn??()

2kk?0k?02k?1n

（a）证明 an+1=an+bn+1, bn+1=an+bn （b）求序列{an}与{bn}的母函数。 （c）用Fibonacci数来表示an与bn。

28. 设 F1=F2=1, Fn=Fn-1+Fn-2

（a）证明 Fn?FkFn?k?1?Fk?1Fn?k,n?k?1。 （b）证明Fm|Fn的充要条件是m|n。 [m被n整除] （c）证明 FmFn?Fn?m?2?Fm?n?6?Fm?n?10?Fm?n?1，当n是奇数?...??,m?n?2。

F，当n是偶数?m?n?2（d）证明(Fm,Fn)=F(m,n), (m,n)为m,n的最大公约数。

29. 从1到n的自然数中选取k个不同且不相邻的数，设此选取的方案为f(n,k)。 （a）求f(n,k)的递推关系。 （b）用归纳法求f(n,k)。

（c）若设1与n算是相邻的数，并设在此假定下从1到n的自然数中选取k个不同且不相邻的k个数的方案数为g(n,k)，利用f(n,k)求g(n,k)。

31. 求下图中从A点出发到n点的路径数。

a0 a1 a2 a3 an-3 an-2 an-1 an n

A b1 b2 b3 bn-3 bn-2 bn-1 bn

32. n位0,1符号串，求从左向右只在最后两位才出现0，0的符号串的数目。 33. 试证

?Fn?1?11? ??10?????F???nnFn?? Fn?1??34．用腰的长度分别为1与2的直角等腰三角形的砖及边长为1的正方形的砖给宽度为1长度为n的路铺面，有多少方案？在所有的方案中，小三角形的砖、大三角形的砖及正方形的砖各一共用了多少块？

本文来源：https://www.bwwdw.com/article/hqt2.html