不错-排列组合问题之全错位排列问题(共3页).doc

《不错-排列组合问题之全错位排列问题(共3页).doc》由会员分享，可在线阅读，更多相关《不错-排列组合问题之全错位排列问题(共3页).doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 排列组合问题之全错位排列问题 （一个通项公式和两个递推关系）一、问题引入： 问题、名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有多少种？ 问题、将编号为，的四个小球分别放入编号为，的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有多少种不同的放法？ 这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题。 问题、五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有多少种？ 解析：可以分类解决：第一类，所有同

2、学都不坐自己原来的位置； 第二类，恰有一位同学坐自己原来的位置； 第三类，恰有两位同学坐自己原来的位置。 对于第一类，就是全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题。 设个元素全错位排列的排列数为，则对于问题，第一类全错位排列的排列数为；第二类先确定一个排原来位置的同学有种可能，其余四个同学全错位排列，所以第二类的排列数为；第三类先确定两个排原位的同学，有种可能，其余三个同学全错位排列，所以第三类的排列数为，因此问题的答案为：。由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法。二

3、、 全错位排列数的递推关系式之一： 定义：一般地，设个编号为、 、的不同元素、，排成一排，且每个元素均不排在与其编号相同的位置，这样的全错位排列数为，则 ；，。 递推关系的确立： 显然当、时，有，。 当时，在个不同元素中任取一个元素不排在与其编号相对应的 位，必排在剩下个位置之一，所以有种排法。 对每一种排法，如排在位，对应位的元素的排位总有两种情况： 第一种情况：恰好排在位上。此时，排在位，排在位，元素，排位已定。还剩个元素，每个元素均有一个不能排的位置，它们的排位问题就转化为 个元素全错位排列数，应有种。第二种情况：不排在位上。此时，仍排在位，不排在位，则有个位置可排。除外，还有个元素，每

4、个元素均有一个不能排的位置，问题就转化为n个元素全错位排列数，应有种。由乘法原理和加法原理可得：，。利用此递推关系可以分别算出，。问题的答案为：。三、 全错位排列数的通项公式之一： 探索：规定，试计算以下各式的值： ； ； 。 很容易计算三式的值依次为，。而这与利用上面的递推关系式得到的，刚好吻合。即 ；。 猜想： 根据上面的探索，我们可以猜想个元素全错位排列数为 为了更容易看清其本质，我们对这个式子进行变形，得到： 。 证明（数学归纳法）： 当，时，式显然成立。 假设，时，式成立。 则当时，由上面的递推关系式可得： 所以，当时，式也成立。 由以上过程可知个元素全错位排列的排列数为： 四、 全错位排列数的递推关系式之二： 由，可得： ； 于是猜想： 证明：由上面已证明的全错位排列数通项公式可知：右边 左边 所以。专心-专注-专业