部分 错位排列

Question

如何计算部分错位排序

比如 1 2 3 4 5 6 7 8
1, 2, 3, 4不在指定位置.
请告诉我答案和原因
还有 5 6 7 8 不在指定位置.
两个答案好像不一样. 不知道为什么.
第一个答案是d4*d4 = 81.
第二个是4!*4! = 576.
急求. 感谢!

Answer 1

按理说第一问和第二问的答案是一样的
如果你的意思是这样的：12345678全排列，1不在首位，2不在第二位，3不在第三位，4不在第四位，其他数字无要求
那下面我来解答
我想说是用容斥原理：A1∪A2∪A3∪A4|=|A1|+|A2|+|A3|+|A4|
-|A1∪A2|-|A1∪A3|-|A1∪A4|-|A2∪A3|-|A2∪A4|-|A3∪A4|
+|A1∪A2∪A3|+|A1∪A2∪A4|+|A1∪A3∪A4|+|A2∪A3∪A4|-|A1∪A2∪A3∪A4|

n个集合的容斥原理
|A1∪A2∪A3∪…∪An|
=∑|Ai1|-∑|Ai1∪Ai2|+…+（-1)^(k+1)∑|Ai1∪Ai2∪…∪Aik|
+…+（-1)^(n+1)∑|A1∪A2∪…∪An|
其中1≤i1＜i2＜…i(k-1)＜ik≤n

这是通式
我们来说第一问
用排除法
8个元素其中4个元素为特殊元素
共8！-（4*7！（四个特殊位置 容斥第一步）+6*6！（容斥原理第二步）-4*5！+1*4！）=24024
第二问也应是这个希望能解决你的问题

Answer 2

错位排列问题是一个古老的问题，最先由贝努利（Bernoulli）提出，其通常提法是：n个有序元素，全部改变其位置的排列数是多少？所以称之为“错位”问题。大数学家欧拉（Euler）等都有所研究。下面先给出一道错位排列题目，让考友有直观感觉。

例1．五个编号为1、2、3、4、5的小球放进5个编号为1、2、3、4、5的小盒里面，全错位排列（即1不放1，2不放2，3不放3，4不放4，5不放5，也就是说5个全部放错）一共有多少种放法？

【解析】：直接求5个小球的全错位排列不容易，我们先从简单的开始。

小球数/小盒数 全错位排列

1 0

2 1（即2、1）

3 2（即3、1、2和2、3、1）

4 9

5 44

6 265

当小球数/小盒数为1~3时，比较简单，而当为4~6时，略显复杂，考友只需要记下这几个数字即可（其实0，1，2，9，44，265是一个有规律的数字推理题，请各位想想是什么？）由上述分析可得，5个小球的全错位排列为44种。

上述是最原始的全错位排列，但在实际公务员考题中，会有一些“变异”。