组合数学
★★★第一章：★★★
1、用六种方法求839647521之后的第999个排列。提示：先把999换算成递增或递减进位制数，加到中介数上，就不用计算序号了。 解： 839647521的中介数 999的中介数 839647521后999的中介数 839647521后999个的排列 842196537 859713426 389547216 → ←→ → → → ← ← 5 7 6 9 2 1 3 8 4 73104210↑ 67504110↑ 12230366↓ 10123362↓ 字典序法 72642321↑ 121211↑ 递增进位制法 67342221↑ 121211↑ 递减进位制法 12224376↓ 1670↓ 10121372↓ 1670↓ 邻位对换法
★★★第二章★★★
例5：10个数字（0到9）和4个四则运算符(+,-,×,÷) 组成的14个元素。求由其中的n个元素的排列构成一算术表达式的个数。
因所求的n个元素的排列是算术表达式，故从左向右的最后一个符号必然是数字。而第n-1位有两种可能，一是数字，一是运算符。如若第n-1位是十个数字之一，则前n-1位必然构成一算术表达式。 10an-1
如若不然，即第n-1位是4个运算符之一，则前n-2位必然是算术表达式。40an-2,根据以上分析，令an 表示n个元素排列成算术表达式的个数。则
...
a2=120指的是从0到99的100个数，以及±0,±1,,±9, 利用递推关系(2-8-1)，得a0=1/2 特征多项式x2-10x-40 。它的根是
解方程
得
1
组合数学
...
例7：平面上有一点P，它是n个域D1,D2,,Dn 的共同交界点，见图2-8-4现 取k种颜色对这n个域进行着色， 要求相邻两个域着的颜色不同。 试求着色的方案数。
（1）D1和Dn-1有相同的颜色； （2）D1 和Dn-1所着颜色不同。
令an 表示这n个域的着色 方案数。无非有两种情况
第一种情形，域有k-1种颜色可用，即D1Dn-1域所用颜色除外；而且从D1到Dn-2的着色方案，和n-2个域的着色方案一一对应。后一种Dn域有k-2种颜色可供使用；而且从D1 到Dn-1的每一个着色方案和n-1个域的着色方案一一对应。
利用(2-8-3)得a1=0,a0=k ，(2-8-3)的特征方程为
习题：
4.求由A,B,C,D组成的允许重复的排列中 AB至少出现一次的排列数目。 解 设an为所求个数，bn为不出现AB的串的个数
an+bn=4n,
bn=4bn-1-bn-2, // bn-2：前n-2个组成的串中不出现AB的串的个数，最后两位是AB.
2
组合数学
an=4an-1+bn-2, // bn-2：前n-2个组成的串中不出现AB的串的个数，最后两位是AB. b1=4,b2=15,b0=1,b3=56. x2-4x+1=0 解得 x=2?nn
bn=S(2+3)+t(2-3)
3。
???2?S?t?13S?2?33???3t?4?
S=
2?2,t=?12n32?233
3bn???2???123??n?1?2??3?n?1?
??an?4??2????3?n?1?2??3?n?1?
??
6.试求由a,b,c三个文字组成的n位符号串 中不出现aa图像的符号串的数目。 解 设不出现aa的字符串的排列数为an
在所有符合要求的n位串中，最后一位是a,则n-1位是b或c，有2an-2;最后一位不是a，则是b或c, 有2an-1.故有
an=2an-1+2an-2，a1=3，a2=8，a0=1.
x2-2x-2=0,解得 x=1?3。
an=A(1+3)n+B(1-3)n
???1?A?B?13A?1?33???3B?333?
A=
?1?4?214,B=??1????1?4?2
?1?an??3?3?n?2?3?n?2?
??
13. 相邻位不同为0的n位2进制数中一共出现了多少个0？
解 设相邻位不同为0的n位2进制数的个数为hn 个，这些数中一共有an个0， 当n位二进制数最高位为1时,符合条件的n位二进制数的个数为hn-1 最高位为0时，次高位必为1符合条件的n位二进制数的个数为hn-2 hn?hn?1?hn?2，h1=2,h2=3,h0=1. 即hn是F数列
3
组合数学
特征方程为：
解得a、b为2重根。 设
分析上式结构可得：
把n=2代入可解得： 代入an 可得方程组
解得
19. 求n位二进制数相邻两位不出现11的数的个数。
解 设所求个数为an,第n位为0或1，是0，有an-1；是1，则n-1位为0,有an-2. an?an?1?an?2, a0?1,a1?2,a2?3,a3?5
4
组合数学
特征方程为 x2?x?1?0,?x1?an?Ax1?Bx2
A?B?1?? 1?3?1?3A?B?2?2?2nn1?25, x2?1?25
代入得
2?1?1?5???A????2??5?? ?2??11?5???B?????2?5???所以an?1?1?5n?21?5n?2???()?()?
225??20. 在n个文字，长度为k的允许重复的排列中，不允许一个文字连续出现三次，求这样的排列的数目。
解 设所求为ak则
特征方程为 解得 可设
代入初值可解出A、B
31. 求下图中从A点出发到n点的路径数。
a a a a a a a a n 0123n-3n-2n-1 n
A b b b b b b b
1
2
3
n-3
n-2
n-1
n
解 把上方的点序列设为an 把下方的点序列设为bn 可得递推关系
5
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库组合数学习题解答在线全文阅读。
相关推荐：