不错-排列组合问题之全错位排列问题_第1页
不错-排列组合问题之全错位排列问题_第2页
不错-排列组合问题之全错位排列问题_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

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

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

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

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论