不动点与组合问题

不动点与组合问题 第一节 不对号入座与全错位排列 一、问题 把n个编号为的球放入n个编号为的盒子中，要求每个盒子中只放一个球，且球的号码与盒子的编号数均不相同，试求有多少种不同的放法种数？ 这个问题就相当于n个自然数的全错位排列问题.不妨设这种不同的放法种数有种，它可以分两步完成：第一步放编号为1的球，共有种放法，此时不妨把编号为1的球放在编号为的盒子里，再安排第i号球的位置，有两种情况： ①第i号球放在第1个盒子中，剩余的个球要放在个盒子中，依然要求是号码均不相同，故种放法； ②第i号球不放在第1个盒子中，此时如同个球要放在个盒子中，且号码均不相同，故有方法数为种. 所以，一般地，我们得到递推公式 ， ① 其中. 利用这个公式，我们可以解决这类错位排列问题. 二、探求通项公式 由递推公式①及，可得： ， 上式两边同乘以得： ② 于是可得： ， ， ， ， 将上述个式子累加，得： 所以，故. 评注 由递推公式①得到递推公式②是求解的关键，这也是处理复杂递推数列问题的难点所在. 例1 同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡不同的分配方式有（ ） A.6种. B.9种. C.11种. D.23种. 分析 此题是全错位排列问题，我们可以应用公式来进行解题. 解析 由递推公式①及，可得.故选B. 例2 五个瓶子都贴了标签，其中恰好贴错了三个，贴错的可能情况共有（ ）种. A.6 B.10 C.12 D.20 分析 此题也是错位重排但不是全部错位，我们可以部分应用错位重排来进行解题. 解析 分步进行：第一步，选出三个瓶子，这三个瓶子恰好贴错了，有种；第二步，这三个瓶子满足错位重排，所以对应的公式数据应该是2.最后根据乘法原理，共有种.故选D. 例3 某人给6个不同的人写了6封信，每人一份，并准备了6个写有收信人地址的信封，问有多少种投放信笺的方法，使得每份信笺和信封上的收信人都不相同？ 分析：此题是全错位排列问题，我们可以应用公式来进行解题. 解析 由递推公式①及，可得： ， ， . 故共有265种投放信笺的方法，使得每份信笺和信封上的收信人都不相同. 三、问题的推论与探究 引理 用表示n个不同元素全错位排列