错排问题的多种解法

错排问题有许多表述

有 $n$ 个元素进行排列，要求没有任何一个元素出现在原来的位置上，有多少排列方法？

有 $n$ 封信和对应的 $n$ 个信封，把所有信随机装入信封，要求每封信都不能装进自己的信封。问有多少种装法？

有 $n$ 对夫妻参加一次聚会，现将所有参会人员任意分成一男一女 $n$ 组，没有任何丈夫匹配到自己的妻子，有多少种匹配？

01 用递推关系推出通项

记错排数为 $D (n)$ ， $n$ 个元素记为 ${1, 2, \dots, n}$ 。

不妨先考虑元素 $1$ ，它可以放在 $2, 3, \dots, n$ 共 $n - 1$ 个位置。不妨设其放在位置 $k$ 。则：

(1) 元素 $k$ 放在位置 $1$ ，剩下的元素排列的方法数为 $D (n - 2)$ 。

(2) 元素 $k$ 不放在位置 $1$ ，则现有的 ${2, 3, \dots, k, \dots, n}$ 共 $n - 1$ 个元素需要放在 ${1, 2, \dots, n} ∖ {k}$ 共 $n - 1$ 个位置，且其中任意一个元素均有且只有一个位置不允许放入： $k$ 不能放入位置 $1$ ，其余元素不能放入原位置。

这与 $n - 1$ 个元素的错排问题完全相同，因此有 $D (n - 1)$ 种方法。

综上，

D (n) = (n - 1) [D (n - 1) + D (n - 2)] .

接下来推出通项。

两边同时除以 $n!$ ，令

a_{n} = \frac{D (n)}{n!},

则

n a_{n} = (n - 1) a_{n - 1} + a_{n - 2},

即

n (a_{n} - a_{n - 1}) = - (a_{n - 1} - a_{n - 2}) .

又

a_{2} - a_{1} = \frac{1}{2},

故

a_{n} - a_{n - 1} = \frac{(- 1)^{n}}{n!} .

于是

a_{n} = \frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!} .

综上，

D (n) = n! (\frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!}) .

02 容斥原理

什么是容斥原理？

| ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k + 1} \sum_{1 \leq i_{1} < \dots < i_{k} \leq n} | A_{i_{1}} \cap \dots \cap A_{i_{k}} | .

从 $1$ 到 $n$ ，奇加偶减。

题解

设

A_{i} = {第 i 个元素仍然在原来的位置} .

则

D (n) = n! - | ⋃_{i = 1}^{n} A_{i} | .

根据容斥原理，

D (n) = n! - ((\binom{n}{1}) (n - 1)! - (\binom{n}{2}) (n - 2)! + \dots + (- 1)^{n - 1} (\binom{n}{n}) 0!) .

因此

D (n) = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!}) .

由于

1 - \frac{1}{1!} = 0,

所以

D (n) = n! (\frac{1}{2!} - \frac{1}{3!} + \dots + (- 1)^{n} \frac{1}{n!}) .