Question

数学高手请进，一道排列组合题：数1,2,3,……,n的一个排列，如果没有任何一个元素站对位置，即没

数学高手请进，一道排列组合题：数1,2,3,……,n的一个排列，如果没有任何一个元素站对位置，即没有任何一个元素i在第i个位置（从左往右数，i=1,2,……,n），就说该排列是一个“超赖排列”，用排列组合计算1,2,……,n
的所有“超赖排列”的个数。（用归纳法也可以）

Answer 1

排除法
A(n,n)-C(n,1)A(n-1,n-1)
+C(n,2)A(n-2,n-2)-C(n,3)A(n-3,n-3)+……+
(-1)^n·A(0,0)
=n！[1-1/1!+1/2!-1/3!+……+(-1)^n/n!]

追问

请问高手你那是怎么得出来的呢？有没有更简单的形式呢，如果已知这个表达式，用强归纳法很好证，可是在什么都不知道的平行下，怎么借助强归纳法呢，我的想法是5时候的超坏个数为5！-C（5,1）（4时候的超坏数）-C（5,2）（3时候的超坏数）-……这样的话子子孙孙无穷尽也，求高手过程

追答

我都说了，排除法
其实就是容斥原理

另外，可以用概率倒推

先不顾条件，
就用n!种，
其次，排除至少一个的，……

至于递推，递推公式为
a(n)=(n-1)[a(n-1)+a(n-2)]
这个，估计没有几个人讲的明白

追问

我现在看的是离散数学，我目前只学了个简单的容斥原理，高级计数部分好像有容斥原理，还没有学，我这个问题就是欧拉错位排序问题，只有一个递推公式呀，没看到一个具体的表达是呀

追答

这个问题的递推公式是我上面给出的吧

追问

我会了，谢谢你，百科有