错排问题及其递推式和通项公式

Prologue

  在组合数学中, 一个 错排 是一个集合中的元素都不出现在自己原来的位置的序列。换言之,一个错排是一个没有定点的序列。这样的序列的个数称为 错排数,记作 DnD_n

这个问题可以转化为:有 nn 个箱子,编号为分别为 1,2,,n1,2,\cdots ,n;有 nn 个球,编号分别为 1,2,,n1,2,\cdots ,n。每个箱子里只放一个球。试求有多少种方案使得每个箱子的编号都和它里面的球编号不同。此外,错问题的常见变体还有写信时将 nn 封信装到 nn 个不同的信封里,有多少种全部装错信封的情况?以及四人各写一张贺年卡互相赠送,有多少种赠送方法?

连接 xx 号球和 yy 号箱子,表示该球 不能 放入该箱子中,记作 xyx\nrightarrow y。所以原问题可以用下图表示,也可以写作试求有多少方案使得:11,22,,nn1\nrightarrow 1,2\nrightarrow 2,\cdots ,n\nrightarrow n

下面我们对原问题稍做变换,得到以下情形:

由图易知只要每个球都有唯一确定的,不与其它球相同的不能放入的箱子,该状态就与原问题等价。如果有球或箱子与箱子或球没有对应或有多个对应,则与原问题不等价。

递推式

枚举可知:D1=0,D2=1,D3=2D_1=0,D_2=1,D_3=2。对于 n3n\geq 3 的情况,考虑对第 nn 号球进行分类。即把第 nn 号球放入第 1,2,,n11,2,\cdots ,n-1 号箱子。列举出所以情况:

nn 号球放入:

  • 11 号箱子
  • 22 号箱子
  • \vdots
  • k1k-1 号箱子
  • kk 号箱子
  • k+1k+1 号箱子
  • \vdots
  • n2n-2 号箱子
  • n1n-1 号箱子

n1n-1 种情况显然是等价的,所以下面考虑把 nn 号球放进 kk 号箱子的情况。

在当前状态下,kk 号球放在 nn 号以外的箱子是等价的,所以考虑分为 kk 号球放在 nn 号箱和 kk 号球放在 nn 号箱之外的箱子这两种情况:

nn 号球放入:

  • 11 号箱子
  • 22 号箱子
  • \vdots
  • k1k-1 号箱子
  • kk 号箱子,kk 号球放入:
    • nn 号箱子
    • nn 号外的箱子
  • k+1k+1 号箱子
  • \vdots
  • n2n-2 号箱子
  • n1n-1 号箱子

kk 号球放入 nn 号箱子,则剩余箱子和球的错排数为 Dn2D_{n-2};当 kk 号球放入 nn 号外的箱子,则可认为 knk\nrightarrow n,因此剩余箱子和球的错排数为 Dn1D_{n-1}kk 号球放入 nn 号箱子后的错排数为 Dn1+Dn2D_{n-1}+D_{n-2}。又「n1n-1 种情况显然是等价的」,所以

Dn={0n=11n=2(n1)(Dn1+Dn2)n3D_n=
\begin{cases}
0&n=1 \
1&n=2 \
(n-1)(D_{n-1}+D_{n-2})&n\geq 3
\end{cases}

通项公式

首先,令 Dn=n!MnD_n=n!M_n(这是一个技巧性很强的 trick),则 Mn={0n=112n=2M_n=\begin{cases}0 & n=1 \ \dfrac{1}{2} & n=2 \end{cases};当 n3n\geq 3 时,因为 Dn=(n1)(Dn1+Dn2)D_n=(n-1)(D_{n-1}+D_{n-2}),所以

n!Mn=(n1)[(n1)!Mn1+(n2)!Mn2]=n!Mn1(n1)!Mn1+(n1)!Mn2\begin{aligned}
n!M_n & =(n-1)\Big[(n-1)!M_{n-1}+(n-2)!M_{n-2}\Big] \
& =n!M_{n-1}-(n-1)!M_{n-1}+(n-1)!M_{n-2}
\end{aligned}

n!Mn=n!Mn1(n1)!Mn1+(n1)!Mn2(MnMn1)=Mn1+Mn2MnMn1=1n(Mn1Mn2)\begin{gathered}
n!M_n =n!M_{n-1}-(n-1)!M_{n-1}+(n-1)!M_{n-2} \
\Leftrightarrow (M_n-M_{n-1})=-M_{n-1}+M_{n-2} \
\Leftrightarrow M_n-M_{n-1}=-\frac{1}{n}(M_{n-1}-M_{n-2})
\end{gathered}

(构造出 邻项相减 方便迭代)

MnMn1=1n(Mn1Mn2)=(1n)(1n1)(13)(M2M1)11=(1)n1n1n1××13×12×11=(1)nn!\begin{aligned}
M_n-M_{n-1} & =-\frac{1}{n}(M_{n-1}-M_{n-2}) \
& =\Big(-\frac{1}{n}\Big)\Big(-\frac{1}{n-1}\Big)\cdots \Big(-\frac{1}{3}\Big)(M_2-M_1)\cdot \frac{1}{1} \
& = (-1)^n\cdot \frac{1}{n}\cdot \frac{1}{n-1}\times \cdots \times \frac{1}{3}\times \frac{1}{2}\times \frac{1}{1} \
& = \frac{(-1)^n}{n!}
\end{aligned}

(对左边进行迭代)

MnMn1=(1)nn!Mn1Mn2=(1)n1(n1)!=M3M2=(1)33!M2M1=(1)22!\begin{aligned}
M_n-M_{n-1} & = \frac{(-1)^n}{n!} \
M_{n-1}-M_{n-2} & = \frac{(-1)^{n-1}}{(n-1)!} \
\vdots & = \vdots \
M_3-M_2 & = \frac{(-1)^3}{3!} \
M_2-M_1 & = \frac{(-1)^2}{2!}
\end{aligned}

将以上各式左右分别累加得

Mn=(1)22!+(1)33!++(1)n1(n1)!+(1)nn!Dn=n!(12!13!++1n1(n1)!+1nn!)\begin{gathered}
M_n=\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\cdots +\frac{(-1)^{n-1}}{(n-1)!}+\frac{(-1)^n}{n!} \
\Leftrightarrow D_n=n!\Big(\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{-1^{n-1}}{(n-1)!}+\frac{-1^n}{n!}\Big)
\end{gathered}

经检验,当 n=1,2n=1,2 时上式成立,所以错排数的通项公式是

Dn=n!i=2n(1)ii!D_n=n! \sum\limits_{i=2}^{n}\frac{(-1)^i}{i!}

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 数学

评论

您需要成为穿墙的邪仙以加载 Disqus。