首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

错排公式 详细解答

错排问题:有n个正整数1,2,3,……n,将这n个正整数重新排列,使其中的每一个数都不在原来的位置上,这种排列称为正整数1,2,3,……n的错排,问这n个正整数的排个数是多少? 设这n个正整数的错排个数为an,为了探求an的表达式,我们先从最特殊的情形入手。 当n=1时,由于只有一个数1,不可能有错排,所以a1=0. 当n=2时,两个数的错排是唯一的,所以a2=1. 当n=3时,三个数1、2、3只有2、3、1和3、1、2两种错排,所以a3=2. 当n=4时,四个数1、2、3、4的错排有:2、1、4、3;2、3、4、1;2、4、1、3;3、1、4、2;3、4、2、1;4、1、2、3;4、3、1、2;4、3、2、1,共有9种错排,所以a4=9. 上面使用的是枚举法,当n较大时,这种方法是很麻烦的、难以解决问题的,必须另辟蹊径,现在考虑用排除法求出1、2、3、4这四个正整数的错排的种数,从中摸索出规律。 对于四个正整数1、2、3、4,这四个数的全排列数为4!。 有一个数不错排的情况应排除,由于1排在第1位的有3!种,2排在第2位的有3!种,……4排在第4位的有3!种,所以共应排除4×3!种。 然而在排除有一个数不错排的情况时,把同时有两个数不错排的情况也排除了,应予以补上,由于1、2分别排在第1、第2位上的情况共有2!种,同理1、3分别排在第1、第3位上的情况也有2!种,……,这四个数中同时有两个数不错排的情况共有种,所以应补上 种。在补上同时有两个数不错排的情况时,把同时有三个数不错排的情况也补上了,应予以排除,四个数中有1、2、3不错排,1、2、4不错排,1、3、4不错排和2、3、4不错排共 种情况,所以应排除 种。 在排除同时有三个数不错排的情况时,把同时有四个数不错排的情况也排除了,所以应补上同时有四个数不错排的情况仅1、2、3、4这一种。

00
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到
    领券