#let date = datetime(
  year: 2022,
  month: 3,
  day: 14,
)
#metadata((
  title: "错排问题",
  subtitle: [错排问题,欧拉信封问题],
  author: "dashuai009",
  abstract: "",
  description: "考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。",
  pubDate: "'Jul 08 2022'",
))<frontmatter>

#import "../__template/style.typ": conf
#show: conf


== 定义
<定义>
考虑一个有$n$个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。
$n$个元素的错排数记为$D_n$或$! n$。

== 例子
<例子>
伯努利-欧拉的装错信封的问题。

== 形式化定义
<形式化定义>
记$D_n$为${ 1 , 2 , dots.h , n }$上没有不动点的排列(即$phi.alt : { 1 , 2 , dots.h , n } arrow.r { 1 , 2 , dots.h , n } , med phi.alt (i) eq.not i , med forall 1 lt.eq i lt.eq n$的个数，$D_n$的值如下：（由$n = 1$起）
$0 , 1 , 2 , 9 , 44 , 265 , 1854 , 14833 , 133496 , 1334961 , 14684570 , 176214841 , 2290792932 . . .$

== 规律
<规律>
$D_n = n D_(n - 1) + (- 1)^n$

== 递推数列法
<递推数列法>
显然$D_1 = 0 , D_2 = 1$。

当$n gt.eq 3$时，不妨设n排在了第k位，其中$k eq.not n$，也就是$1 lt.eq k lt.eq n - 1$。那么我们现在考虑$k$的情况。

- 当k排在第$n$位时，除了$n$和$k$以外还有$n - 2$个数，其错排数为$D_(n - 2)$。
- 当$k$不排在第$n$位时，那么将第$n$位重新考虑成一个新的“第$k$位”，这时的包括$k$在内的剩下$n - 1$个数的每一种错排，都等价于只有$n - 1$个数时的错排（只是其中的第k位会换成第n位）。其错排数为$D_(n - 1)$。
  所以当n排在第$k$位时共有$D_(n - 2) + D_(n - 1)$种错排方法，又$k$有从$1$到$n - 1$共$n - 1$种取法，我们可以得到：

$D_n = (n - 1) (D_(n - 1) + D_(n - 2))$

== 生成函数

=== 一
<一>
根据规律 $D_n = n D_(n - 1) + (- 1)^n$可以得到如下：

$
  D (x) & = x D (x) + e^(- x)\
  & = frac(e^(- x), 1 - x)\
  & = frac(1 - x + frac(x^2, 2 !) + . . . + (- 1)^n frac(x^n, n !) + . . ., 1 - x)
$

=== 二
<二>
从置换环的角度考虑，错排就是指置换环中不存在自环的排列。也就是说不存在长度为
$1$ 的置换环。后者的指数生成函数是

$ sum_(n gt.eq 2) x^n / n = - ln (1 - x) - x $

因此错排数的指数生成函数就是 $exp (- ln (1 - x) - x)$。

== 减掉非错排的情况
<减掉非错排的情况>
非错排：存在$p_i = i$的排列

只存在一个：$C_n^1 D_(n - 1)$,

只存在二个：$C_n^2 D_(n - 2)$,

只存在三个：$C_n^3 D_(n - 3)$,

…

只存在n个：$C_n^n D_(n - n)$,

所以，
$
  D_n & = n ! - (C_n^1 D_(n - 1) + C_n^2 D_(n - 2) + C_n^3 D_(n - 3) + . . . + C_n^n D_(n - n))\
  & = sum_(k = 0)^n binom(n, k) (n - k) !
$

#strike[那一定是你程序写错了]

== 通向公式
<通向公式>
令$D_n = n ! M_n$

$M_n - M_(n - 1) = (- 1)^n frac(1, n !)$

$D_n = n ! (frac(1, 2 !) - frac(1, 3 !) + frac(1, 4 !) - . . . + (- 1)^n frac(1, n !))$

== #link("https://zh.wikipedia.org/wiki/%E9%94%99%E6%8E%92%E9%97%AE%E9%A2%98#%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%A8%A1%E6%8B%9F")[多项式模拟]
<多项式模拟>
== $D_n$最接近 $frac(n !, e)$ 的整数
<d_n最接近-displaystyle-frac-ne-的整数>
考虑指数函数在 0 处的泰勒展开：

$
  e^(- 1) & = 1 + frac((- 1)^1, 1 !) + frac((- 1)^2, 2 !) + frac((- 1)^3, 3 !) + . . . + frac((- 1)^n, n !) + frac(e^(- c), (n + 1) !) (
    c - 1
  )^n\
  & = frac(D_n, n !) + R_n
$ 其中
$ lr(|R_n|) lt.eq frac(e^0, (n + 1) !) = frac(1, (n + 1) !) $ 所以
$ lr(|frac(n !, e) - D_n|) lt.eq frac(n !, (n + 1) !) = frac(1, n + 1) $
得 $ D_n = ⌊frac(n !, e) + 0.5⌋ $