文章目录
一、错排问题
二、错排问题递推公式推导
三、推导错排公式
一、错排问题
----
n
封不同的信 与
n
个不同的信封 , 将
n
封信都装错信封的方案个数 ;
错排 ( Derangement..., 此时交换一下即可完成错排, 有
1
种方案 ,
D(2) = 1
;
假如有
3
封信 ,
1,2,3
三封信与三个信封 ,
如果
1
放到
3
信封中 , 此时将
2...放到
1
信封中 , 将
3
放到
2
信封中 ,
1,2,3
3,1,2
如果
1
放到
2
信封中 , 此时将
2
放到
3
信封中 , 将
3
放到
1...分类计数原理
假设第一封信
a
占据了
b
的位置 , 那么此时
b
放在哪个信封分两种情况 ,
b
放在
a
位置 , 或
b
不放在
a
位置 ;
( 1 ) 第一类 :...) , 这种情况下 相当于除
a
之外的其它元素的错排问题 , 即
n-1
个元素的错排问题 , 方案数是
D(n-1)
; ★ ( 核心推导逻辑 ) ★
( 3 ) 加法法则 : 汇总上述分类计数原理