Java教程

一些对于错排问题的简单思考

本文主要是介绍一些对于错排问题的简单思考,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

概述

错排问题是一个古老有趣的数学问题,最早由 Bernouli 和 Euler 开始研究,也被称为 Bernouli-Euler 问题。问题十分简单,即五个标数了的不同物品分别放入五个标数了的不同盒子,每个盒子对应且仅对应一个物品,有多少种使物品和盒子标号不同的方法。

探讨

首先对于错排问题的第一想法是枚举。不妨设 \(f(n)\) 为 \(n\) 个盒子的错排最终结果。则:

\[f(1)=0,f(2)=1,f(3)=2,f(4)=9,f(5)=44,... \]

但是枚举的复杂度是 \(\Theta(n!)\),运算量十分大,不利于计算,我们需要一些更加优秀的做法。

Solution 1 递推

我们不妨认为标号为 \(1\) 的物品放在了位置 \(k\),那么 \(k\) 有 \(n-1\) 种选择。接下来考虑标号为 \(k\) 的物品的放置:

  • 放置在了标号为 \(1\) 的物品处,那么剩下的物品就变为了一个规模为 \(n-2\) 的子问题。
  • 没有放置在标号为 \(1\) 的物品处。此时可以将第 \(k\) 个物品视为第一个物品,并将第一个物品删去,此时对剩下每个物品的限制与原问题相同,又变为了一个规模为 \(n-1\) 的子问题。
    那么递推式即为:

\[f(n)=\begin{cases}(n-1)(f(n-1)+f(n-2)) & \forall n\geq 3\\0 & n=1\\1 & n=2\end{cases} \]

至此我们已经将复杂度降到了 \(\Theta(n)\),但对 \(f(n)\) 仍依赖于前两项。继续推导。

由于在式中 \(n-1\) 并非常数,无法直接用特征根法,非常遗憾。

观察原式,我们发现 \(f(n)\) 的数量级与 \(n!\) 十分相似(原因是可以观察到与 \(F(n)=n!=nF(n-1)\) 有些类似,区别只是多了前一项与系数不同)。不妨令 \(g(n)=\frac{f(n)}{n!}\),那么:

\[n!g(n)=(n-1)((n-1)!g(n-1)+(n-2)!g(n-2)),\forall n\geq 3 \]

对右半边的括号进行展开并提取公因式即:

\[ng(n)=(n-1)g(n-1)+g(n-2),\forall n\geq 3 \]

相邻项相减,并循环代入:

\[g(n)-g(n-1)=-\frac{1}{n}(g(n-1)-g(n-2))=(-\frac{1}{n})(-\frac{1}{n-1})(g(n-2)-g(n-3))=...=\prod\limits_{k=1}^n(-\frac{1}{k})=\frac{(-1)^n}{n!},\forall n\geq 4 \]

代入验证发现对于 \(n=3,2\) 同样成立。那么:

\[\begin{cases}g(n)-g(n-1)&=\frac{(-1)^n}{n!}\\g(n-1)-g(n-2)&=\frac{(-1)^{n-1}}{(n-1)!}\\&...\\&...\\&...\\g(2)-g(1)&=\frac{(-1)^2}{2!}\end{cases} \]

套路地通加:

\[g(n)-g(1)\overset{g(1)=0}{=}g(n)=\sum_{k=2}^n\frac{(-1)^k}{k!},\forall n\in \mathbb{N}^* \]

回到最初 \(g(n)=\frac{f(n)}{n!}\),那么:

\[f(n)=n!\sum_{k=2}^n\frac{(-1)^k}{k!} \]

至此得出了最终的结论,相较于递推式,这个式子更加直接,不依赖于 \(f(n-1)\) 和 \(f(n-2)\),不过复杂度与递推式相同。

Solution 2 容斥

直接对原问题大力容斥。首先对于 \(n\) 个物品的全排列为 \(n!\) 个,我们需要舍掉那些满足第 \(k\) 个物品放在标号为 \(k\) 位置的排列,也即 \(n\cdot(n-1)!=n!\) 个;接下来需要加上上一轮多减去的放对两个位置的排列,共 \(\binom{n}{2}(n-2)!\) 种;……以此类推,可以得出最后的结果是:

\[\sum_{k=2}^n (-1)^k\binom{n}{k}(n-k)!=\sum_{k=2}^n\frac{(-1)^kn!}{k!}=n!\sum_{k=2}^n\frac{(-1)^k}{n!} \]

注意这里为了避免 \(0!\) 的出现直接抵消了初始状态和容斥一轮的 \(n!\)。可以发现得出了和 Solution 1 完全相同的结论。

Solution 3 二项式反演

这个方法相较于 Sol1 和 Sol2 而言,速度较快。

定义 \(g(n)\) 为 \(n\) 个物品任意放的排列数。枚举有几个物品放在了自己的位置上,那么容易得到:

\[g(n)=\sum_{k=0}^n\binom{n}{k}f(k) \]

直接对其进行二项式反演,得到:

\[f(n)=\sum_{k=0}^n(-1)^{k}\binom{n}{k}g(k) \]

由于 \(g(n)=n!\),直接代入即得:

\[f(n)=\sum_{k=2}^n\frac{(-1)^n}{n!} \]

这里同样直接约去了 \(k=1,2\)。

结语

错排问题仅是组合计数中的一个经典问题。看到这里,相信您对错排问题有了一些了解。但至此,计数领域的宏伟仅露冰山一角,海平面下的风景仍需各位探寻。
那么,旅途愉快。

这篇关于一些对于错排问题的简单思考的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!