在线学习
重点科目
初中数学
高中数学
高等数学
线性代数
概率统计
高中物理
数学公式
主要科目
复变函数
离散数学
数学分析
实变函数
群论
数论
未整理科目
近世代数
数值分析
常微分方程
偏微分方程
大学物理
射影几何
微分几何
泛函分析
拓扑学
数学物理
趣味数学
科数网
首页
教材
高考区
考研区
VIP
科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
高中物理
复变函数
离散数学
你好
游客，
登录
注册
在线学习
概率论与数理统计
第一篇 随机事件与概率
古典模型6：错位排列
最后
更新:
2025-01-10 07:43
查看:
127
次
反馈
刷题
古典模型6：错位排列
## 错位排列 错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于 $1 \sim n$ 的排列 $P$ ，如果满足 $P_i \neq i$ ，则称 $P$ 是 $n$ 的错位排列。 $n$ 封不同的信，编号分别是 $1,2,3,4,5$ ，现在要把这五封信放在编号 $1,2,3,4,5$ 的信封中，要求信封的编号与信的编号不一样。问有多少种不同的放置方法? 假设考虑到第 $n$ 个信封，初始时暂时把第 $n$ 封信放在第 $n$ 个信封中，然后考虑两种情况的递推： - 前面 $n-1$ 个信封全部装错； - 前面 $n-1$ 个信封有一个没有装错其余全部装错。 对于第一种情况，前面 $n-1$ 个信封全部装错：因为前面 $n-1$ 个已经全部装错了，所以第 $n$ 封只需要与前面任一一个位置交换即可，总共有 $D_{n-1} \times(n-1)$ 种情况。 对于第二种情况，前面 $n-1$ 个信封有一个没有装错其余全部装错：考虑这种情况的目的在于，若 $n-1$ 个信封中如果有一个没装错，那么把那个没装错的与 $n$ 交换，即可得到一个全错位排列情况。 其他情况，不可能通过一次操作来把它变成一个长度为 $n$ 的错排。 于是可得，错位排列数满足递推关系： $$ D_n=(n-1)\left(D_{n-1}+D_{n-2}\right) $$ 这里也给出另一个递推关系： $$ D_n=n D_{n-1}+(-1)^n $$ ## 其他关系 错位排列数有一个简单的取整表达式，增长速度与阶乘仅相差常数： $$ D_n= \begin{cases}\left\lceil\frac{n!}{e}\right], & \text { if } n \text { is even, } \\ \left\lfloor\frac{n!}{e}\right\rfloor, & \text { if } n \text { is odd. }\end{cases} $$ 随着元素数量的增加，形成错位排列的概率 P 接近: $$ P=\lim _{n \rightarrow \infty} \frac{D_n}{n!}=\frac{1}{e} $$
其他版本
【高中数学】古典概率
开VIP会员
非会员每天6篇，会员每天16篇，VIP会员无限制访问
题库训练
自我测评
投稿
上一篇：
古典模型5：抽屉原理
下一篇：
古典模型7：抽奖与配对模型
本文对您是否有用？
有用
(
0
)
无用
(
0
)
纠错
高考
考研
关于
赞助
公式
科数网是专业专业的数学网站。