(1/2)谁知道错位问体的推广N个元素至少M个元素错位公式证明，全错位我用递推公式找到了通项公式。可推...

(1/2)谁知道错位问体的推广N个元素至少M个元素错位公式证明，全错位我用递推公式找到了通项公式。可推...

设有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)]

　错位排列:n个相异元素中m(≤n)个元素ai1,ai2,…,aim，其中aik(k=1,2,…,m)不在第ik(k=1,2,…,m)个位置(以下简称其为aik的本位)，而其他n-m个元素中的任何一个都在原来的位置(本位)的排列.

　　禁位排列(本文只讨论一个元素禁止排在一个位置的情况):n个相异元素中的m个元素ai1,ai2,…,aim，其中aik(k=1,2,…,m)不能排在第jk(k=1,2,…,m)个位置的排列.

　　两者的区别在于：错位排列中除这m个元素之外的其他n-m个元素都在本位，即这m个元素只能在m个位置i1,i2,…,im中排列，且不出现aik(k=1,2,…,m)在ik位的情况；而禁位排列中只限制m个元素不在本位，因此aik(k=1,2,…,m)可以排在1,2,…,n中除ik之外的任何位置.参考资料：错位排列