错排问题

✍ dations ◷ 2025-10-18 12:08:30 #组合数学

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

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

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

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

所以当n排在第k位时共有Dn-2+Dn-1种错排方法,又k有从1到n-1共n-1种取法,我们可以得到:

在上面我们得到

Dn=(n-1)(Dn-1+Dn-2)

从这个公式中我们可以推出Dn的通项公式,方法如下:

为书写方便,记Dn = n!Mn,则M1 = 0, M2 = 1 2 {\displaystyle {\frac {1}{2}}} 的最大整数)。

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

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

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

相关

  • 伊尼亚士埃涅阿斯(希腊文:Αινείας,Aineías),也译作“伊尼亚斯”,特洛伊英雄,宙斯7世孙,达达诺斯6世孙,厄里克托尼俄斯2世5世孙,特洛斯玄孙,阿萨剌科斯曾孙,卡皮斯孙,安基塞斯王子与爱神
  • 好莱坞标志好莱坞标志(英语:Hollywood Sign),曾名好莱坞兰标志(英语:Hollywoodland Sign),位于美国加利福尼亚州洛杉矶,是当地地标,也是美国的重要文化象征。它位于圣莫尼卡山脉好莱坞山的李山(英
  • 上诉法院上诉法院或上诉法庭(appellate court:appeals court;court of appeals (American English;appeal court (British English);court of second instance;second instance court),是审
  • 伯曼猫伯曼猫(Birman),又称波曼猫、巴曼猫、缅甸圣猫(法语:Sacré de Birmanie),是一种拥有长毛和重点色的家猫品种。其名来自于法语“Birmanie”,意思即缅甸。1925年在法国首次得到确认。
  • 榕属榕属(学名:),又名无花果属,是桑科内的其中一属也是无花果族(学名:)的唯一属,内里包含近八百种的树木、灌木及藤本植物等。它们原为热带雨林的原生品种,但也有部分延伸至暖温带,常被统称
  • 罗尔德·阿蒙森罗尔德·恩格尔布雷希特·格拉范林·阿蒙森(挪威语:Roald Engelbregt Gravning Amundsen,1872年7月16日-1928年6月18日)是一位挪威极地探险家,于1911年至1912年,他领导的探险队为第
  • 孙燧 (弘治进士)清代修《浙江余姚孙氏宗谱》之忠烈公像孙燧(1460年-1519年),字德成,号一川,浙江余姚县人。家族出于横河孙氏,明朝忠臣。官至江西巡抚,宁王朱宸濠谋反时将其杀害。身后追赠礼部尚书,谥
  • 岸田今日子岸田今日子(日语:岸田 今日子,1930年4月29日-2006年12月17日),日本女演员、配音员、童话作家。身高156cm。A型血。1930年4月29日出生于东京府豊多摩郡(今东京都杉并区),父亲是剧作家
  • Prima donnaprima donna,是意大利文中“首席女性”的意思,通常用于歌剧剧团之中。这个专有名词通常会用在指涉歌剧剧团中的首席女歌手,也是在演出时会赋予重要角色的演出工作的人物。“pri
  • 波罗的海会议波罗的海会议 (Baltic Assembly,BA)是一个区域政府间组织,促进爱沙尼亚、拉脱维亚、立陶宛三国之间的合作,试图令三国在众多国际议题上有共同立场,但会议的决定只具有建议地位。波