数据结构递归关系

Question

我需要帮助和您的提示来回答这种问题，因为我迷路了...这是问题：有n个字母，每个字母都有其邮箱。f（n）=将每个字母放入错误的邮箱的方式的数量。我需要找到一个递归算法。

所以这是我到目前为止的想法：f（n = 1）= 0f（n = 2）= 1对于n个字母，您可以使用（n-1）个选项将其放入错误的邮箱中。所以也许应该是这样的：n-1 *（f（n-1））

我不知道我是否在朝着正确的方向思考，我应该多少思考。如果您有资源可以帮助我，我也会很高兴。这是选项：（第四个选项是所有答案都不正确）click here to see the answers

Answer 1

考虑n=4情况。首先我们有四个盒子。我们需要从n-1选择中选择字母1的框。为了说明起见，假设我们选择了方框2。

1  2  3  4
  /
1  2  3  4

现在有两种可能性。

1. 第2封信邮寄到第1栏中。然后，我们在第3栏和第4栏中分别留下字母和字母。因此，有f(2)种方式。

2. 第2封邮件被邮寄到除1之外的其他框中。然后，我们应该寻找一种安排字母1、3、4和2、3、4的方式，条件是字母1和2为没有配对。这与排列三个带有相同数字集的字母和盒子的情况相同。因此，有f(3)种这样的方式。

概括此逻辑，f(n) = (n-1) * (f(n-2) + f(n-1))。