【组合数学】错排问题 ( 递推公式 | 通项公式 | 推导过程 ) ★

2023-03-28 18:43:52 浏览数 (1)

文章目录

  • 一、错排问题
  • 二、错排问题递推公式推导
  • 三、推导错排公式

一、错排问题

n

封不同的信 与

n

个不同的信封 , 将

n

封信都装错信封的方案个数 ;

错排 ( Derangement ) , 因此错排公式中使用

D(n)

表示

n

个元素的错排 ;

假如有

1

封信 ,

n= 1

, 此时不能错排 ,

D(1) = 0

;

假如有

2

封信 ,

n= 2

, 此时交换一下即可完成错排, 有

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

信封中 ,

1,2,3
2,3,1
  • ​
D(3) = 2

如果有

4

封信 , 此时就不好计算 ,

9

种方法 ,

D(4) = 9

如果有

5

封信

cdots

,

D(5) = 44
vdots

如果有

n

封信

cdots

,

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!}

二、错排问题递推公式推导

观察上述规律 , 推导出递推公式 ;

假如有

n

封信 , 任何一封信都需要错位 , 错排方案数是

D(n)

;

1 . 分步计数原理 : 使用 分步计数原理 , 先统计 第一封信的排列方法 , 然后再讨论 其余信的排列方法数 ;

( 1 ) 第一步 : 首先找出一封信

a

出来 , 这封信不能排在其本身位置 , 只能放在其余

n-1

个位置上 , 因此有

n-1

种排法 ;

( 2 ) 第二步 : 现在讨论其余除

a

之外的其余信的位置的错排问题 ;

2 . 分类计数原理

假设第一封信

a

占据了

b

的位置 , 那么此时

b

放在哪个信封分两种情况 ,

b

放在

a

位置 , 或

b

不放在

a

位置 ;

( 1 ) 第一类 : 第一种情况是放在

a

位置 , 此时

b

放在

a

位置 , 剩下

n-2

封信进行错排 , 方案数是

D(n-2)

( 2 ) 第二类 : 第二种情况是

b

没有去

a

的位置 , 那么

b

可能出现在除

a

之外的任何位置 ,

b

有

n-2

个位置可以去 , 不能去

a,b

位置 , 其余所有元素都有

n-2

个位置可以去 (

a,b

位置不能去 ) , 这种情况下 相当于除

a

之外的其它元素的错排问题 , 即

n-1

个元素的错排问题 , 方案数是

D(n-1)

; ★ ( 核心推导逻辑 ) ★

( 3 ) 加法法则 : 汇总上述分类计数原理 , 使用 加法法则 , 计算结果是

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(1) = 0 , D(2) = 1

使用 递推方程 , 生成函数求解递推方程 , 容斥原理 , 可以推导出如下公式 :

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!}

参考 :

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

0 人点赞