首页 > 其他 > 详细

容斥法解决错排问题

时间:2019-10-23 22:11:49      阅读:87      评论:0      收藏:0      [点我收藏+]

错排问题

简单来说,错排问题就是问有多少个长度为\(n\)的排列\(p\),使得对于所有的\(i\in [1,n]\)都有\(i \neq p_i\)

递推式

错排的一个递推式就是\(f(n)=n(f(n-1)+f(n-2))\)

这个递推式复杂度显然是线性的。

关于这个递推式的推导请自行百度。这里不再赘述。

容斥法解错排问题

第一次看到错排问题的时候,并没有推导出上面的递推式。而是用了一种容斥的方法。自认为更加简单易懂吧。

既然是每个数字都不能放在对应的位置。那么按照容斥的一般套路,我们强制有\(i\)个数字放在了对应位置。其他数字不管他。显然这\(i\)个数字有\(C(_n^i)\)种方案。其他数字有\((n-i)!\)种排列方式。

所以式子就很显然了:

\[f(n)=\sum\limits_{i=0}^n(-1)^iC(_n^i)(n-i)! \\ =\sum\limits_{i=0}^n(-1)^i\frac{n!}{i!}\]

复杂度同样也是线性的。

其实可以发现,用容斥继续推下去的话,依然可以推出上面的递推式。所以这两种解法本质上是等价的。

容斥法解决错排问题

原文:https://www.cnblogs.com/wxyww/p/cuopai.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!