知方号

知方号

组合数学错排问题 ( 递推公式 <推盒子计算器>

文章目录 一、错排问题二、错排问题递推公式推导三、推导错排公式

一、错排问题

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! sumlimits_{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∑n​k!(−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! sumlimits_{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∑n​k!(−1)k​

参考 :

百度百科-错排公式【组合数学】递推方程 ( 递推方程求解过程总结 | 齐次 | 重根 | 非齐次 | 特征根为 1 | 指数形式 | 底为特征根的指数形式 ) ★★【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )【集合论】容斥原理 ( 包含排斥原理 | 示例 )

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至lizi9903@foxmail.com举报,一经查实,本站将立刻删除。