原题
11．从分别写有 $1, 2, 3, \ldots, m\left(m \in \mathbb{N}^{*}\right)$ 的 $m$ 张卡片中不放回随机抽取 $n(n \leq m) $ 次, 每次取 1 张卡片, 记第 $i(i=1,2,3, \cdots, n)$ 次取出卡片的数字为 $a_{i}$, 定义 $F_{m}^{n}$ 为满足 $\forall i \leq n, a_{i} \neq i$ 的不同情况数, 则 ______
- A． $F_{m}^{1}=m-1$
- B． $\sum\limits_{i=1}^{3} F_{3}^{i}=7 $
- C． $F_{n}^{n} \leq m n $
- D． $F_{n+1}^{n}=(n+1) F_{n}^{n}+n F_{n-1}^{n-1}(n \geq 2)$
答案
本题选 ABD.
解析
A 选项
想象有 $m$ 个球, 编号 $1, 2, \ldots, m$, 那没有挑到 $1$ 号球的的情况显然就是 $m-1$ 咯
$A$ 显然正确.
B 选项
数字不大, 直接枚举就可以了
- 先求 $F_3^1$
- 套用 $A$ 选项结论, $F_3^1 = 2$
- 再求 $F_3^2$
- 由于第一个不能为 1, 分类讨论
- 第一位是 $2$: 有 $(2,1) (2,3)$ 2种
- 第一位是 $3$: 有 $(3,1)$ 1种
- 因此 $F_3^2 = 3$
- 由于第一个不能为 1, 分类讨论
- 最后求 $F_3^3$
- 由于第一位不能为 1, 分类讨论
- 第一位是 $2$: 有 $(2,3,1)$ 1种
- 第一位是 $3$: 有 $(3,1,2)$ 1种
- 因此 $F_3^3 = 2$
- 由于第一位不能为 1, 分类讨论
所以 $\sum\limits_{k=1}^{3} F_3^k = 2 + 3 + 2 = 7$, $B$ 选项正确.
C 选项
显然 $F_n^m$ 应该小于 $A_n^m$ 才对, 尝试找一个反例
试一下 $F_5^3$, 看看是不是小于 15
数字不大, 列举一下
- 第一位是 2:
- $(2,1,4) (2,1,5)$
- $(2,3,1) (2,3,4) (2,3,5)$
- $(2,4,1) (2,4,5)$
- $(2,5,1) (2,5,4)$ 共 9 种.
- 第一位是 3:
- $(3,1,2) (3,1,4) (3,1,5)$
- $(3,4,1) (3,4,2) (3,4,5)$
- $(3,5,1) (3,5,2) (3,5,4)$ 共 9 种.
- 第一位是 4:
- $(4,1,2)(4,1,5)$
- $(4,3,1)(4,3,2)(4,3,5)$
- $(4,5,1)(4,5,2)$ 共 7 种.
- 第一位是 5:
- $(5,1,2)(5,1,4)$
- $(5,3,1)(5,3,2)(5,3,4)$
- $(5,4,1)(5,4,2)$ 共 7 种.
求得
$$ F_5^3 = 9+9+7+7=32 > 15 $$所以 C 选项错误.
当然也可以参考全错排公式的推导用容斥原理计算:
- 总数: 从 5 个元素中选 3 个的排列数 $A_5^3 = 60$.
- 减去至少 1 个位置固定: $\binom{3}{1} A_4^2 = 3 \times 12 = 36$.
- 加上至少 2 个位置固定: $\binom{3}{2} A_3^1 = 3 \times 3 = 9$.
- 减去 3 个位置全固定: $\binom{3}{3} A_2^0 = 1 \times 1 = 1$.
也可以得到 $F_5^3 = 32$.
D 选项
设 $D_k = F_k^k$ 为 $k$ 个元素的错位排列数. 我们需要证明:
$$ F_{n+1}^n = (n+1)D_n + n D_{n-1} $$步骤 1: 建立 $F_{n+1}^n$ 的基本递推关系
考虑从集合 ${1, 2, \dots, n+1}$ 中选取 $n$ 个数字排列在位置 $1, \dots, n$ 上, 且 $a_i \neq i$. 根据数值 $n+1$ 是否出现在数列中分类:
- $n+1$ 未出现: 数列由 ${1, \dots, n}$ 组成, 且 $a_i \neq i$. 方案数为 $D_n$.
- $n+1$ 出现: 设 $a_j = n+1$, 位置 $j$ 有 $n$ 种选择 ($j \in {1, \dots, n}$). 剩余 $n-1$ 个位置由 ${1, \dots, n} \setminus {k}$ 填充（其中 $k$ 是未被选中的那个 $1 \sim n$ 之间的数, 或者更准确地说, 剩余位置需从 ${1, \dots, n}$ 中选 $n-1$ 个排布）. 此部分的方案数等价于 $n F_n^{n-1}$.
因此有初步递推式:
$$ F_{n+1}^n = D_n + n F_n^{n-1} $$步骤 2: 推导 $F_n^{n-1}$ 与 $D_n$, $D_{n-1}$ 的关系
$F_n^{n-1}$ 表示从 ${1, \dots, n}$ 中选 $n-1$ 个排在位置 $1, \dots, n-1$ 上, 且 $a_i \neq i$.
根据“哪个数字没被选中”分类:
- 没选中的是 $n$: 剩余 ${1, \dots, n-1}$ 排在 $1, \dots, n-1$ 上, 即 $D_{n-1}$.
- 没选中的是 $k \in {1, \dots, n-1}$: 对于固定的 $k$, 剩余数字包含 $n$. 这相当于构造一个长度为 $n-1$ 的序列, 使用数字 ${1, \dots, n} \setminus {k}$. 通过组合双射可以证明, 所有 $k \in {1, \dots, n-1}$ 的情况之和恰好等于 $D_n$. (直观理解: $D_n$ 可以看作是在 $n$ 个位置的错位排列中, 去掉第 $n$ 位及其对应的值后形成的结构总和).
故有恒等式:
$$ F_n^{n-1} = D_n + D_{n-1} $$步骤 3: 代入并整理
将步骤 2 的结果代入步骤 1 的递推式:
$$ \begin{aligned} F_{n+1}^n &= D_n + n(D_n + D_{n-1}) \\ &= D_n + n D_n + n D_{n-1} \\ &= (n+1)D_n + n D_{n-1} \\ &= (n+1)F_n^n + n F_{n-1}^{n-1} \end{aligned} $$因此 $D$ 选项正确.
扩展
$F_m^n$ 叫做部分错排数, 是全错排的推广. 全错排 $D_n = F_n^n$ 可以视为一个特例.
$F_m^n$ 的通项公式
利用容斥原理.
总排列数为 $A_m^n$.
设性质 $P_i$ 为 $a_i = i$. 我们需要排除所有满足至少一个 $P_i$ 的情况.
若固定 $k$ 个位置满足 $a_i=i$, 则这 $k$ 个位置已确定, 剩余 $n-k$ 个位置从剩下的 $m-k$ 个元素中选取并排列, 方案数为 $A_{m-k}^{n-k}$. 选择哪 $k$ 个位置固定有 $\binom{n}{k}$ 种方式.
于是通项公式为:
$$ F_m^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} A_{m-k}^{n-k} $$展开排列数 $A_{m-k}^{n-k} = \frac{(m-k)!}{(m-n)!}$, 可得
$$ F_m^n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} \frac{(m-k)!}{(m-n)!} $$进一步化简为组合数形式:
$$ F_m^n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \binom{m-k}{n-k} $$结论: $F_{n+1}^n = D_n + D_{n+1}$
证明:
已知错位排列递推公式 $D_{n+1} = n(D_n + D_{n-1})$. 由命题 2 可知:
$$ F_{n+1}^n = (n+1)D_n + n D_{n-1} $$计算 $D_n + D_{n+1}$:
$$ \begin{aligned} D_n + D_{n+1} &= D_n + n(D_n + D_{n-1}) \\ &= D_n + n D_n + n D_{n-1} \\ &= (n+1)D_n + n D_{n-1} \end{aligned} $$两者相等, 故 $F_{n+1}^n = D_n + D_{n+1}$ 成立.