首页 > 代码库 > 理解错排公式

理解错排公式

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))。

理解错排公式