[关闭]
@zzzc18 2018-01-25T11:07:48.000000Z 字数 369 阅读 571

错位排列

数学


问题:

一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多少种?
就是hdu2048

Solution:

采用递推的方法
个数的错排的方案为
如果我们已经求出来前 ,现在考虑将第一个元素放在第 个元素的位置上,那么会有以下两种情况

  1. 个元素恰好到了第一个位置,那么对于 内的 个元素可以与 不相关地进行错排,即 种。
  2. 个元素不在第一个位置,可以将第一个位置看成第 个元素的“归宿”,那么“第 个元素不在第一个位置”就又是一个错排,这样一来,对于 内的元素满足错排的方案为 种。

由于 ,所以最后的递推式为

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注