首页 >

错排问题

✍ dations ◷ 2025-11-21 04:06:44 #组合数学

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

相关

廖内省廖内省（印尼语：Riau）是印度尼西亚的一个省，位于苏门答腊东部，与马来西亚隔马六甲海峡相望。原属本省廖内群岛2004年分出，设廖内群岛省。面积83,232平方公里。首府北干巴鲁（省内另一
远洋带远洋带指在内陆水域和海域中远离岸的自由水域。它指从水域中心起向靠岸方向直至遇到第一个有根的水生植物的区域。当其深度为0－200m是称之为透光带，其下为不透光带。远洋带同
娄成后娄成后（1911年12月7日－2009年10月16日），天津人，祖籍浙江绍兴，中国植物生理学家。1932年获清华大学生物系理学士学位。1934年获岭南大学硕士学位。1939年获美国明尼苏达大学哲学博
杨门女将之军令如山《杨门女将之军令如山》（英文：Legendary Amazons），2011年11月18日上映于中国大陆的古装动作电影。由任贤齐、张柏芝、刘晓庆、郑佩佩、金巧巧等主演，主题曲《杨门女将》由汤灿演
黑客 (计算机安全)“黑客”（Hacker）是信息安全、电脑安全和网络安全领域的专业人士，有能力参与信息战，发动或阻止基于网络的攻击。除了民间知名黑客与组织，各国亦有军方资金招募和培养的黑客，这些黑
毓朗敏达贝勒毓朗（满语：ᠶᡡ ᠯᠠᠩ，穆麟德：，太清：；1864年8月27日－1922年12月14日），字月华，号余痴，别号余痴生，爱新觉罗氏。宗室，清末军机大臣。光绪三十三年（1907年）袭贝勒。历任巡警部（民政部）
陈淳 (画家)陈淳（1482年－1544年），中国明代画家。名道复，更字复父，号白阳山人，长洲（今江苏吴县）人。原是文徵明弟子，后不拘师法，自成一格，擅长写意花卉。中年好作山水，师法米友仁、高克恭，提材多为江南
齐泰齐泰（14世纪？－1402年），本名德，获明太祖赐名泰，字尚礼，号南塘，直隶溧水县（今江苏省南京市溧水区）人，明初政治人物。齐泰为洪武甲子解元，戊辰进士，历任礼、兵二部主事、兵部郎中、左侍郎。明
多轴加工多轴加工（Multiaxis machining）是指在机械加工时，有可以在四个（或是更多）方向上移动的工具或是刀具。以铣削、水刀或是镭射切割的方式去除过多的材料。这种加工方式最早是出现在
有机化学通讯《有机化学通讯》（，缩写或）是一本同行评审的科学期刊，1999年由美国化学会第一次发行。该期刊的影响因子为6.364（2014年）。《有机化学通讯》被以下的文献或机构的数据库收录：化学文