千针坊丶
设有N个元素作排列 记ai(i=0,1,...,N)为恰好有i个元素错位的排列数,则有 A(N,N)=C(N,0)a0+C(N,1)a1+...+C(N,N)aN 其中A(N,N)是N个元素的全排列,C(N,i)是N个元素里选i个的组合数 上面的公式可以理解为 N个元素的全排列可以看作是:先从N个元素里选出i个,其他元素位置不变,但是这i个元素全错位排列,当i从0取到N以后,刚好就是N个元素的全排列数 现在我们可由上面的公式得到全错位排列的递推公式,即 aN=A(N,N)-[C(N,0)a0+C(N,1)a1+...+C(N,N-1)a(N-1)]
吃尸体的秃鹰
设1，2，...，n的全排列b1，b2，...，bn的集合为A,而使bi=i的全排列的集合记为Ai(1<=i<=n)，则Dn=|A|-|A1∪A2∪...∪An|。
所以Dn=n!-|A1∪A2∪...∪An|。
注意到|Ai|=(n-1)!，|Ai∩Aj|=(n-2)!，...，|A1∩A2∩...∩An|=0!=1。
错位排列问题就是指一种比较难理解的复杂数学模型，是伯努利和欧拉在错装信封时发现的，因此又称伯努利-欧拉装错信封问题。
表述为：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法？
对这类问题有个固定的递推公式，记n封信的错位重排数为Dn。
则D1=0，D2=1，Dn=（n-1）（Dn-2+Dn-1） 此处n-2、n-1为下标。n>2
只需记住Dn的前几项：D1=0，D2=1，D3=2，D4=9，D5=44。只需要记住结论，进行计算就可以。
优质公务员考试问答知识库
