为什么容斥原理可以推导全错位排列？？？记Ai表示数字i恰好排在第i个位置的排列集合，|Ai|=card(Ai)表示集合中元素个数；€Ai表示Ai的余集（补集）现在求的是∩€Ai，即任意i都不会出现

Question

为什么容斥原理可以推导 全错位排列 ？？？
记Ai表示数字i恰好排在第i个位置的排列集合，|Ai|=card(Ai)表示集合中元素个数；€Ai表示Ai的余集（补集）
现在求的是∩€Ai，即任意i都不会出现在第i个位置的排列集合；
根据容斥原理得
|∩€Ai|=|€∪Ai|=n!-|∪Ai|
而
|∪Ai|=∑C(n,k)(-1)^(k+1)(n-k)! （这里k从1到n）
从而
|∩€Ai|=n!-|∪Ai|=n!+∑(-1)^k*C(n,k)(n-k)!
发现k=0恰好(-1)^k*C(n,k)(n-k)!=n!所以结果可以改写为
∑(-1)^k*C(n,k)(n-k)! （这里k从0到n）
C(n,k)(n-k)! 的意义表示其中指定某k个数字排在它对应的位置，其他的n-k个数字可以任意排列的个数为(n-k)!个，而指定k个可以有C(n,k)种指定方式。
我问题是！！！这个推导方法怎么理解？我觉得不对啊！觉得很没道理啊！！

Answer 1

Ai表示数字i恰好排在第i个位置的排列集，n!-C(n,1)(n-1)!代表全排列减去1在第一个位置、或者2在第二个位置、或者……、或者n在第n个位置的情况；但是减多了，因为1在第一个位置且2在第二个位置这种情况被减了两次，应该加回来一次，同理i在第i个位置且j在第j个位置被减了两次，应该加回来一次，所以总共要再加上C(n,2)(n-2)!中（C(n,2)代表n个数中选出i和j）；但是又加多了，因为多加了i在第i个位置且j在第j个位置且k在第k个位置的情况，又要减掉C(n,3)(n-3)!；……；加加减减一直进行下去。。建议仔细看看容斥原理的推导。