组合数学 1 ★★★第一章：★★★ 1、用六种方法求839647521 之后的第999 个排列。提示：先把999 换算成递增或递减进位制数，加到中介数上，就不用计算序号了。 解： 字典序法 递增进位制法 递减进位制法 邻位对换法 839647521的中介数 72642321↑ 67342221↑ 12224376↓ 10121372↓ 999 的中介数 121211↑ 121211↑ 1670↓ 1670↓ 839647521后999 的中介数 73104210↑ 67504110↑ 12230366↓ 10123362↓ 839647521后999 个的排列 842196537 859713426 389547216 → 3 ←8 → 4 → 5 → 7 → 6 ← 9 ← 2 1 ★★★第二章★★★ 例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 。它的根是 解方程 得 组合数学 2 例7：平面上有一点P，它是n 个域D1,D2,...,Dn 的共同交界点，见图2-8-4 现 取k 种颜色对这n 个域进行着色， 要求相邻两个域着的颜色不同。 试求着色的方案数。 令 an 表示这n 个域的着色 方案数。无非有两种情况 （1）D1 和 Dn-1 有相同的颜色； （2）D1 和 Dn-1 所着颜色不同。 第一种情形，域有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. 组合数学 3 an=4an-1+bn-2, // bn-2：前n-2 个组成的串中不出现...
