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

韩曙亮

发布于 2023-03-28 18:43:52

8020

发布于 2023-03-28 18:43:52

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、错排问题

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! \sum\limits_{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! \sum\limits_{k=0}^{n}\cfrac{(-1)^k}{k!}

参考 :

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-11-02，如有侵权请联系 cloudcommunity@tencent.com 删除

百度