1、2.4 非线性常系数 递推关系举例1. 错排问题2. Stirling数3. Catalan数1. 错排问题定义 ： n个不同的元素进行排列，使得每个元素都不在原来的位置上，这样的排列称为 错排 。从比较小的 n开始讨论，试图找出规律。1 2的错排是唯一的，即 2 1。1 2 3的错排有 3 1 2， 2 3 1。可以看作是 1 2错排， 3分别与 1， 2换位而得的。1 2 3 4的错排有：第二列可以看成是 4与 3 1 2中每一个互换位置得到。第三列则是 4与 2 3 1(1 2 3的另一个错排 )中的每一个互换位置得到。4 3 2 1， 4 1 2 3， 4 3 1 2，3 4 1 2，
2、 3 4 2 1， 2 4 1 3，2 1 4 3， 3 1 4 2， 2 3 4 1。这些错排中，第一列的可以看成是 4与 1， 2， 3互换位置，剩下的两个数字错排。注意 3 1 2是 1 2 3的一个错排。似乎可以看出得到 n个元素错排有两种途径：(1) n与某个元素互换，剩下的 n-2个元素错排；(2) 前 n-1个元素错排，然后对每一个错排， n与某个元素互换。问题在于这两种途径是否 无重复 、 无遗漏 的给出了所有 n个元素的错排？答案是 肯定的。若设 n个元素的错排数为 Dn，则第一种途径得到的错排数为 (n-1)Dn-2；第二种途径的错排数为 (n-1)Dn-1。因此我们可以得
3、到递推关系：Dn=(n-1)(Dn-1+Dn-2)， D1=0, D2=1。然后说明 无遗漏 ：对于某一个给定的错排， n一定不会落在最后一个位置，不妨假设 n在第一个位置，即 1原来所在的位置，接下来看 1所在的位置：(1) 若 1在第 n个位置，则这个错排是通过第一种途径得到的。首先说明 无重复 ：(2) 若 1不在第 n个位置，不妨假设在第 n个位置的数字是 2，交换 2和 n，则前 n-1个数字仍是错排。这表明这个错排是通过第二种途径得到的。第一种途径得到的错排的特点是若 n在位置 k，则 k必在位置 n，而第二种途径的错排必没有这个性质。因此对于错排问题，我们有如下的递推关系：这是一
4、个 线性非常系数 递推关系。令 En=Dn/n!，则Dn=(n-1)(Dn-1+Dn-2)， D1=0, D2=1。即注意到 E1=D1/1!=0， E0=D0/0!=1，因此有D0=1因此有所以例 1 数 1,2,9 的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。这相当于 1,3,5,7,9这 5个元素的错排问题，因此例 2 求 8个字母 ABCDEFGH的全排列中，只有 4个元素不在原位置上的排列数。4个元素的错排数为因此答案为 C(8,4)D4=630。2. Stirling数定义 ： n个 有区别的球 放到 k个 相同的盒子 中，要求 无一空盒 ，其不同的方案数用 S(n,k)表示，称为第二类 Stirling数 。例如红、黄、蓝、白四种颜色的球 ,放到两个无区别的盒子里，不允许有空盒，其方案有：其中 rybw分别表示红、黄、蓝、白球，因此有S(4,2) = 7。定理 1：第二类 Stirling数有如下性质：性质 (a) (b) (e)显然，只证 (c)(d)。(c) n个球中球 1放在某个盒子中，那么对于其他 n-1个球，每个球都有 2种选择：与球 1同盒或不同盒。但要排除掉所有球都与球 1同盒的情形 (出现空盒 )。因此有： S(n,2) = 2n-1-1。
