首页 >

错排问题

✍ dations ◷ 2025-12-05 08:28:58 #组合数学

错排问题是组合数学中的问题之一。考虑一个有 $n {\displaystyle n}$ ），并独立解决了这个问题。

对于情况较少的排列，可以使用枚举法。

对于排列数较多的情况，难以采用枚举法。这时可以用递归思想推导错排数的递回关系式。

显然D₁=0，D₂=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑k的情况。

所以当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的通项公式，方法如下：

为书写方便，记D_n = n!M_n，则M₁ = 0, M₂ = ${\frac {1}{2}}$ 的最大整数）。

这个简化公式可以由之前的错排公式推导出来。事实上，考虑指数函数在 0 处的泰勒展开：

所以， ${\frac {n!}{e}}-D_{n}=n!\,R_{n}$ 是泰勒展开的余项，是介于 0 和 1 之间的某个实数。的绝对值上限为

当 n≥2 时， ${\frac {1}{(n+1)}}$ ${\frac {1}{(n+1)}}$ 严格小于 0.5，所以 $D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)$ $D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)$ 是最接近 ${\frac {n!}{e}}$ ${\frac {n!}{e}}$ 的整数，可以写成

相关

电脑断层扫描计算机断层成像（Computed Tomography，简称CT），是一种影像诊断学的检查。这一技术曾被称为计算机轴向断层成像（Computed Axial Tomography）。X射线计算机断层成像（X-Ray Computed To
范德华力范德华力（范德华力）（Van der Waals force）在化学中指分子之间非定向的、无饱和性的、较弱的相互作用力，根据荷兰物理学家约翰内斯·范德瓦耳斯命名。范德华力是一种电性引力，但它
德塞夫勒省德塞夫勒省（法语：Deux-Sèvres）是法国新阿基坦大区所辖的省份。该省编号为79。省会为尼奥尔。省名的意思是“双塞夫尔”，指的是两条名为塞夫尔（Sèvre）的河流：南特塞夫尔河（Sèvre N
石长生石长生（学名：Adiantum monochlamys），又名单盖铁线蕨，为铁线蕨科铁线蕨属下的一个种。
爱慕情意、爱意、爱慕或喜爱之情是一种性情（英语：disposition）、精神或身体上较罕见的状态，常常会和情爱的感觉拉上关系。这种情感衍生出数个关于情绪、疾病、影响力和状态的哲学和
切斯特·A·阿瑟切斯特·艾伦·阿瑟（Chester Alan Arthur，1829年10月5日－1886年11月18日），美国律师及政治人物，第21任美国总统，共和党人。原为詹姆斯·加菲尔德的副总统，两人于1880年搭档参选。1881
清小舌擦音清小舌擦音是辅音之一，用于一些语言当中，但汉语普通话中无此音。国际音标以⟨χ⟩代表此音，X-SAMPA音标以⟨X⟩代表此音。另外，此音的符号不当与清软颚擦音的符号或字母x混淆。
阿波斯托洛斯安德列亚斯角阿波斯托洛斯安德列亚斯角（希腊语：Ακρωτήριο Αποστόλου Ανδρέα，土耳其语：Zafer Burnu）是位于地中海国家北塞浦路斯土耳其共和国东北部卡尔帕斯半岛的海
符宁符宁（高棉语：ហូ នឹម ；1932年7月25日－1977年7月6日），绰号波（ភាស់ ），是赤柬重要领导人之一。出身磅湛省，有一半的华人血统。家境贫困，后来加入赤柬，成为重要领导人之一。1970年柬
GATE 奇幻自卫队《GATE 奇幻自卫队》（日语：ゲート自衛隊彼の地にて、斯く戦えり，中文直译为：门：自卫队在彼之地如此战斗）是由日本小说家柳内巧编写的奇幻小说。续作《GATE第二季：自卫队在彼之海