国家公务员行测考试之错位排列——全错位排列问题

国家公务员行测考试之错位排列——全错位排列问题

　　一、问题导入

　　【引例1】唐僧、孙悟空、猪八戒、沙和尚4人在某公司不同岗位任职，现在需要调换岗位，要求每个人都不能在自己原来的岗位，则共有 种不同的安排方法。

　　【引例2】有4名同学各写了一张贺卡，先全部收集起来，然后每人从中拿出一张贺卡，要求每个人都不拿自己的贺卡，则四张贺卡的不同分配方式共有 种。

　　【引例3】将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同(即1不放1，2不放2，3不放3，4不放4，也就是说4个全部放错)，则共有 种不同的放法。

　　不难发现，以上三个引例都是同一类问题，答案是多少呢?下面用枚举法给大家答案：

　　假设原来顺序：A、B、C、D

　　枚举的时候注意按照一定规律进行，如果看成1、2、3、4号位置，那么第一步A可以放2、3、4号位置中的任意一个，第二步把B的位置确定，第三步确定C和D的位置：

　　第1种错位排列：B、A、D、C(A在2位，B在1位，C、D位置就唯一确定了);

　　第2种错位排列：D、A、B、C(A在2位，B在3位，C、D位置就唯一确定了);

　　第3种错位排列：C、A、D、B(A在2位，B在4位，C、D位置就唯一确定了);

　　第4种错位排列：B、D、A、C(A在3位，B在1位，C、D位置就唯一确定了);

　　第5种错位排列：C、D、A、B(A在3位，B在4位，C、D位置可以是1、2);

　　第6种错位排列：D、C、A、B(A在3位，B在4位，C、D位置也可以是2、1);

　　第7种错位排列：B、C、D、A(A在4位，B在1位，C、D位置就唯一确定了);

　　第8种错位排列：C、D、B、A(A在4位，B在3位，C、D位置可以是1、2);

　　第9种错位排列：D、C、B、A(A在4位，B在3位，C、D位置也可以是2、1)。

　　可见，4个元素的错位排列一共有9种。即以上三道引例的答案都是9种。

　　二、理论推导

　　其实，上面引例涉及的三个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把带这种限制条件的排列问题叫做全错位排列问题。

　　它是一个非常古老的数学问题，贝努利、欧拉等数学家都曾经研究过。这类问题虽然有难度，但我们解题是有快速破解的“窍门”的。且看下面详细解读：

　　我们将n个元素的全错位排列数记做Dn。

　　由于1个元素没有错位排列，因此D1=0。

　　2个元素时可以相互交换一下位置，即有1种错位排列，则D2=1。

　　当n≥3时，在n个不同元素中任取一个元素ai不排在与其编号相对应的i位，必排在剩下n-1个位置之一，所以ai有n-1种排法。

　　即第一步排ai，有n-1种。

　　第二步：排ai所占位置对应的元素。

　　对ai每一种排法，如ai排在j位，对应j位的元素aj的排位共有两类情况：

　　第一类情况：aj恰好排在i位上，此时，ai排在j位，aj排在i位，元素ai、aj排位已定，还剩n-2个元素，它们的排位问题就转化为n-2个元素全错位排列数，应有Dn-2种;

以上就是【国家公务员行测考试之错位排列——全错位排列问题】的相关介绍，如果要了解更多热门资讯，欢迎关注吉林华图教育。