错排问题

✍ dations ◷ 2025-10-19 11:52:58 #组合数学

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

相关

  • 主族金属主族金属是指周期表中s区及p区的金属元素,包括碱金属、碱土金属及铝、镓、铟、铊、锡、铅及铋等元素。主族金属容易参加化学反应,其氧化态较低。反应后大都形成离子键化合物。
  • 朗布依埃城堡朗布依埃城堡(法语:Château de Rambouillet) 是法国法兰西岛大区城市朗布依埃的一座法式城堡,位于巴黎东南50公里处。朗布依埃城堡是法国总统的别邸之一。
  • .iq.iq为伊拉克国家及地区顶级域(ccTLD)的域名。A .ac .ad .ae .af .ag .ai .al .am .ao .aq .ar .as .at .au .aw .ax .az  B .ba .bb .bd .be .bf .bg .bh .bi .bj .bm .bn
  • 炭河里遗址炭河里遗址坐落在湖南省长沙市宁乡市黄材镇,是南方著名的青铜器出土地。年代约为商朝到西周时期。宁乡位于长江以南,却有大量珍贵的青铜器出土。这是中国历史界的一个还没有解
  • 塞尔达·塔什彻塞尔达·塔什彻(土耳其语:Serdar Taşçı,英语发音:/səˈdaː ˈtæʃtʃi/,1987年4月24日-),是一名土耳其裔的德国足球运动员,现时效力土超俱乐部巴萨克赛尔,司职中后卫。2006年,塔
  • 亚历山大·吉尔芒费利克斯-亚历山大·吉尔芒(法语:Félix-Alexandre Guilmant,1837年3月12日-1911年3月29日),法国作曲家,管风琴家。生于滨海布洛涅,1871年到巴黎担任管风琴师,后到欧美各地巡回演出。
  • 汤尼潘帝汤尼潘帝是在小说《时间的女儿》当中出现的名词,泛指任何出于政治或其他因素而被过度夸大或炒作的历史事件,特别是指那些成为传奇而知道真相的人全都袖手旁观的事件(P.112)汤
  • 灯盏糕灯盏糕是浙江温州的特色名点,一种油炸食品。外形酷似古代扁圆形的菜油灯盏,故得名“灯盏糕”。外皮原料为大米与黄豆浸泡后磨成的米浆,内以萝卜刨成的细丝作主料再加上猪腿肉和
  • 坂田站 (深圳地铁)† 路线图不按真实比例,仅供参考.坂田站是深圳地铁5号线一个使用中的车站,于2011年6月22日随5号线开通投入使用。坂田站位于龙岗区坂田街道布龙路、坂雪岗大道交界地下,沿东西
  • 陈泇彤陈泇彤(英文:Lizzchloe,Chloe Tan Jia Tong,1993年4月10日-),艺名彤彤,祖籍广东,马来西亚华人YouTuber、电台主持人,来自吉隆坡,其妹妹陈泇惠(白冰沙)也是YouTuber。2011年,加入广告公司,以