文章目录
一、错排问题
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 | 指数形式 | 底为特征根的指数形式 ) ★★
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【集合论】容斥原理 ( 包含排斥原理 | 示例 )
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/226145.html原文链接：https://javaforall.net
