非线性递推关系举例.pptVIP

* * 2.4 非线性常系数递推关系举例 错排问题 Stirling数 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，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。因此我们可以得到递推关系： 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，而第二种途径的错排必没有这个性质。 因此对于错排问题，我们有如下的递推关系： 这是一个线性非常系数递推关系。 令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。 (d) n个不同的球放到n-1个相同的盒子里，必定是某个盒子里有2个球，其他盒子各1个球。 由于盒子都相同，因此问题等价于从n个球中选出2个即可。所以有：S(n,n-1) = C(n,2)。 定理2：第二类Stirling数满足如下递推关系式： 选定球1，则无一空盒的方案可分为两类： (1) 球1独占一个盒子，这样的方案数为S(n-1,k-1)； (2) 球1不独占一个盒子，这相当于把其他n-1个球放到k个盒子里，要求无一空盒，然后再把球1放到每个盒子中。这样的方案数为kS(n-1,k)。 因此有定理2的结论成立。 上面定理的证明过程实际上也给出了一种构造所有方案的方法。 例如考虑把红、黄、蓝、白、绿五个球放到无区别的两个盒子里。 根据递推关系：S(5,2)=2S(4,2)+S(4,1)=2×7+1=15。 这15种方案可分为2类，如下表所示： 考虑n个球放入m个盒子中的问题。按照球是否有区别、盒子是否有区别、是否允许空盒分为8种情形： (1) n个球有区别，m个盒子有区别，允许空盒时方案数为：mn。 (2) n个球有区别，m个盒子有区别，不允许空盒时方案数为：m!S(m,n)。 (3) n个球有区别，m个盒子无区别，允许空盒时方案数为： (4) n个球有区别，m个盒子无区别，不允许空盒时方案数为：S(m,n)。 (5) n个球无区别，m个盒子有区别，允许空盒时