首页 >

错排问题

✍ dations ◷ 2025-11-25 18:38:29 #组合数学

错排问题是组合数学中的问题之一。考虑一个有 $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}}$ 的整数，可以写成

相关

负回授负反馈（英语：negative feedback），是反馈的一种。是指系统的输出会影响系统的输入，在输出变动时，所造成的影响恰和原来变动的趋势相反；反之，就称为正反馈。另一种说法是系统在一个条
逆合成分析逆合成分析，也称作逆合成法、反合成分析，是解决有机合成路线的重要方法，也是有机合成路线设计的最简单、最基本的方法。其实质是目标分子的分拆，通过分析目标分子结构，逐步将其拆
二级上将上将（英语：general）是军衔之一种，通常为高级军事将领，对应北约军衔等级为OF-9。最初，上将指善于作战的将领。《史记·孙子吴起列传》：“（孙膑语）百里而趣利者蹶上将，五十里而趣利者军
吴越春秋《吴越春秋》是东汉时期的著作，为稗官杂记体之别史。东汉赵晔撰，共有十卷。叙述春秋时期吴、越二国之间的战事。文辞丰蔚富饶，颇似小说家言。在四库全书中为史部记载类。现今较
山岸一雄山岸一雄（1934年4月28日－2015年4月1日），生于日本长野县中野市（山之内），厨师，在东京都丰岛区东池袋创立拉面店大胜轩。对于拉面料理有极大贡献，他创造了沾面（つけ麺），被人称为拉面之神。
何塞·马里亚·佩拉尔塔何塞·马里亚·佩拉尔塔（西班牙语：José María Peralta，1807年12月－1883年12月6日），生于圣萨尔瓦多，1859年2月15日至3月12日任萨尔瓦多总统。佩拉尔塔卒于圣萨尔瓦多。
吉娜·戴维斯弗吉尼亚·伊丽莎白·"吉娜"·戴维斯（Virginia Elizabeth "Geena" Davis，1956年1月21日－）是一位美国女演员、电影制片人、剧作家，前时尚模特，她还曾以射箭运动员的身份打入悉尼奥
白屈氨酸白屈氨酸（英语：Chelidamic acid，又名白屈菜氨酸）是一种分子式为C7H5NO5的杂环氨基酸，分子中含有一个吡啶环。第一步是丙酮与草酸二乙酯在强碱（一般常用乙醇钠）的作用下发生克莱森缩
英令奈英令奈（日语：えれな，1982年3月12日－），本名能濑英令奈（日语：能瀬英令奈／のせえれな），是出身于日本爱知县名古屋市昭和区的模特儿，隶属的经纪公司是十克拉（テンカラット；Ten Carat）所
小岩羚属小岩羚属（学名：）也作石羚属，是偶蹄目牛科的一属，分布于非洲的热带草原，包括以下三种：