IDEA激活码
文章目录
- 一、错排问题
- 二、错排问题递推公式推导
- 三、推导错排公式
一、错排问题
n
n
n 封不同的信 与
n
n
n 个不同的信封 , 将
n
n
n 封信都装错信封的方案个数 ;
错排 ( Derangement ) , 因此错排公式中使用
D
(
n
)
D(n)
D(n) 表示
n
n
n 个元素的错排 ;
假如有
1
1
1 封信 ,
n
=
1
n= 1
n=1 , 此时不能错排 ,
D
(
1
)
=
0
D(1) = 0
D(1)=0 ;
假如有
2
2
2 封信 ,
n
=
2
n= 2
n=2 , 此时交换一下即可完成错排, 有
1
1
1 种方案 ,
D
(
2
)
=
1
D(2) = 1
D(2)=1 ;
假如有
3
3
3 封信 ,
1
,
2
,
3
1,2,3
1,2,3 三封信与三个信封 ,
- 如果
1
1
1 放到3
3
3 信封中 , 此时将2
2
2 放到1
1
1 信封中 , 将3
3
3 放到2
2
2 信封中 ,
1
,
2
,
3
1,2,3
1,2,3
3
,
1
,
2
3,1,2
3,1,2 - 如果
1
1
1 放到2
2
2 信封中 , 此时将2
2
2 放到3
3
3 信封中 , 将3
3
3 放到1
1
1 信封中 ,
1
,
2
,
3
1,2,3
1,2,3
2
,
3
,
1
2,3,1
2,3,1 -
D
(
3
)
=
2
D(3) = 2
D(3)=2
如果有
4
4
4 封信 , 此时就不好计算 ,
9
9
9 种方法 ,
D
(
4
)
=
9
D(4) = 9
D(4)=9
如果有
5
5
5 封信
⋯
\cdots
⋯ ,
D
(
5
)
=
44
D(5) = 44
D(5)=44
⋮
\vdots
⋮
如果有
n
n
n 封信
⋯
\cdots
⋯ ,
D
(
n
)
=
n
!
(
(
−
1
)
0
0
!
+
(
−
1
)
1
1
!
+
(
−
1
)
2
2
!
+
(
−
1
)
3
3
!
+
⋯
+
(
−
1
)
n
n
!
)
=
n
!
∑
k
=
0
n
(
−
1
)
k
k
!
D(n) = n! ( \cfrac{(-1)^0}{0!} + \cfrac{(-1)^1}{1!} + \cfrac{(-1)^2}{2!} + \cfrac{(-1)^3}{3!} + \cdots + \cfrac{(-1)^n}{n!} ) = n! \sum\limits_{k=0}^{n}\cfrac{(-1)^k}{k!}
D(n)=n!(0!(−1)0+1!(−1)1+2!(−1)2+3!(−1)3+⋯+n!(−1)n)=n!k=0∑nk!(−1)k
二、错排问题递推公式推导
观察上述规律 , 推导出递推公式 ;
假如有
n
n
n 封信 , 任何一封信都需要错位 , 错排方案数是
D
(
n
)
D(n)
D(n) ;
1 . 分步计数原理 : 使用 分步计数原理 , 先统计 第一封信的排列方法 , 然后再讨论 其余信的排列方法数 ;
( 1 ) 第一步 : 首先找出一封信
a
a
a 出来 , 这封信不能排在其本身位置 , 只能放在其余
n
−
1
n-1
n−1 个位置上 , 因此有
n
−
1
n-1
n−1 种排法 ;
( 2 ) 第二步 : 现在讨论其余除
a
a
a 之外的其余信的位置的错排问题 ;
2 . 分类计数原理
假设第一封信
a
a
a 占据了
b
b
b 的位置 , 那么此时
b
b
b 放在哪个信封分两种情况 ,
b
b
b 放在
a
a
a 位置 , 或
b
b
b 不放在
a
a
a 位置 ;
( 1 ) 第一类 : 第一种情况是放在
a
a
a 位置 , 此时
b
b
b 放在
a
a
a 位置 , 剩下
n
−
2
n-2
n−2 封信进行错排 , 方案数是
D
(
n
−
2
)
D(n-2)
D(n−2)
( 2 ) 第二类 : 第二种情况是
b
b
b 没有去
a
a
a 的位置 , 那么
b
b
b 可能出现在除
a
a
a 之外的任何位置 ,
b
b
b 有
n
−
2
n-2
n−2 个位置可以去 , 不能去
a
,
b
a,b
a,b 位置 , 其余所有元素都有
n
−
2
n-2
n−2 个位置可以去 (
a
,
b
a,b
a,b 位置不能去 ) , 这种情况下 相当于除
a
a
a 之外的其它元素的错排问题 , 即
n
−
1
n-1
n−1 个元素的错排问题 , 方案数是
D
(
n
−
1
)
D(n-1)
D(n−1) ; ★ ( 核心推导逻辑 ) ★
( 3 ) 加法法则 : 汇总上述分类计数原理 , 使用 加法法则 , 计算结果是
D
(
n
−
1
)
+
D
(
n
−
2
)
D(n -1) + D(n-2)
D(n−1)+D(n−2)
3 . 乘法法则 : 汇总上述分步计数原理 , 使用 乘法法则 , 计算结果是
D
(
n
)
=
(
n
−
1
)
(
D
(
n
−
1
)
+
D
(
n
−
2
)
)
D(n) = (n-1) (D(n -1) + D(n-2))
D(n)=(n−1)(D(n−1)+D(n−2))
三、推导错排公式
递推公式 :
D
(
n
)
=
(
n
−
1
)
(
D
(
n
−
1
)
+
D
(
n
−
2
)
)
D(n) = (n-1) (D(n -1) + D(n-2))
D(n)=(n−1)(D(n−1)+D(n−2))
初值 :
D
(
1
)
=
0
,
D
(
2
)
=
1
D(1) = 0 , D(2) = 1
D(1)=0,D(2)=1
使用 递推方程 , 生成函数求解递推方程 , 容斥原理 , 可以推导出如下公式 :
D
(
n
)
=
n
!
(
(
−
1
)
0
0
!
+
(
−
1
)
1
1
!
+
(
−
1
)
2
2
!
+
(
−
1
)
3
3
!
+
⋯
+
(
−
1
)
n
n
!
)
=
n
!
∑
k
=
0
n
(
−
1
)
k
k
!
D(n) = n! ( \cfrac{(-1)^0}{0!} + \cfrac{(-1)^1}{1!} + \cfrac{(-1)^2}{2!} + \cfrac{(-1)^3}{3!} + \cdots + \cfrac{(-1)^n}{n!} ) = n! \sum\limits_{k=0}^{n}\cfrac{(-1)^k}{k!}
D(n)=n!(0!(−1)0+1!(−1)1+2!(−1)2+3!(−1)3+⋯+n!(−1)n)=n!k=0∑nk!(−1)k
参考 :
- 百度百科-错排公式
- 【组合数学】递推方程 ( 递推方程求解过程总结 | 齐次 | 重根 | 非齐次 | 特征根为 1 | 指数形式 | 底为特征根的指数形式 ) ★★
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【集合论】容斥原理 ( 包含排斥原理 | 示例 )
