首页 > 代码库 > 理解错排公式
理解错排公式
n个信封n封信,全部装错,有多少种可能的错误方式?
在该例中,用数列F[n],表示n个信封时的错误方式数量,易得出F(1)=0,F(2)=1。所以应尝试用递推去解决。
当n个信封n封信全部装错的时候,假设第n号信封中装的是k号信,然后在剩下n-1封信中找到装有n号信封对应的n号信的m号信封,这里的m号信封有(n-1)种可能,将n号信封中的k号信和m号信封中的n号信交换,则n号信封中装的是n号信,m号信封装的是k号信,k号信有两种情况,一种是k等于m,即m号信封装的是m号信,这种情况下,m号信封和n号信封都装的是对应的信,所以此时有F(n-2)种错误可能(除了n和m别的都装错)。第二种情况是k不等于m,此时有F(n-1)种错误可能(除了n以外所有信封都装错)。
所以我们得出错排公式:F(n)=(n-1)(F(n-1)+F(n-2))。
理解错排公式
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。