距离2020年春节还有多少天-经济类专业排名

浅谈容斥原理在概率论中的应用
李策
（1236303班 6120610306）
摘要：容斥原理是解决有限集合计数问题的重要原理之一。事实上我们在利用加法原理计数
时, 就是先将问题分划成若干个两两互不相交的子集(分类讨论),再求各个集合中元素的个
数。但是在许多 问题中, 将其划分为若干个两两互不相交的集合并非易事, 而容斥原理在一
定程度上解决了这个问题 。又因为古典概型和排列组合有着密不可分的关系，因此容斥原理
在概率论中也有着十分重要的地位。
关键词：容斥原理;古典概型;错位排列
一、 定理内容
如果A
1
，A
2
，A
3
，…，A
n
为n个事件，则有
< br>n

n
n1


P

A PAPAA

1PA
1

A
2

A
3



A
n
。



iiij

1ijn

i1

i 1

特别的，当n=2时，有
PA

BP

A

P

B

PA

B
， 即一般概率加法公
式。
[1]

由对偶定律可得如下概率公式：

n



n

n1

P< br>


A
i


1


P

A
i



P

A
i

A
j





1

PA
1

A
2

A
3


A
n

。
1i,jn


i1


i1



 

二、 错位排列
集合中的元素按照某种规定(比如字典序)排成一个序列 ,同时指定了每个元
素的位置,利用容斥原理可以讨论构造新的排列,使得所有元素不在原来指定的位置上;或者部分元素不在禁止摆放的位子上的排列计数问题。
[2]

2.1 绝对错位排列
例题：一名同学写了4封信，同时准备了4个信封，假设这名同学随机将这4封信
装入这4个信封，求任何一封信都未被装入相应信封的概率。
4
首先，将4封信随机装入4 个信封，共有
A
4
种情况。欲求任何一封信都未被
装入相应信封的概率，只需 要求得任何一封信都未被装入相应信封的所有情况出
现次数。概率为任何一封信都未被装入相应信封的所 有情况出现次数与4封信随

机装入4个信封所有情况出现次数的比值。
解法一：假设4封信为A，B，C，D，信封为a，b，c，d，进行分类讨论。
A装入某个 信封，有3种选择，不妨设A装入b信封，则B信有3种选择。若B
信装入a信封中，则C信只能装入d 信封且D信只能装入c信封。如果B信未装入a
信封，则可选择c或d信封，不妨设装入c信封中，则C 信只能装入d信封且D信只
能装入a信封。综上所述，任何一封信都未被装入相应信封的所有情况出现次 数
为
3

12

6
。
解法二：运用容斥原理
假设4封信为A，B，C，D，信封为a，b，c，d，记A =A信装入a信封，B=B
信装入b信封,C=C信装入c信封,D=D信装入d信封，S为4封信随机 装入信封的总
情况数。任何一封信都未被装入相应信封的所有情况出现次数为
A
B

C

DSA

B

C

D
。
4132231
经过计算，结果为
A
4
C
4
A
3
C
4
A
2
C
4
A
1
19
。
下面我们推导一般情况的错位排列公式。
由于元素性质与讨论不相干, 设n个元素的集合X={1,2,3,…,n}，n个元素依
次 给予标号1,2,…,n。在n个元素的全排列中, 求每个元素都不在自己原来位置上
的排列数。
首先每个错排都是原集合的一个全排列, 记为i
1
,i
2
,…i
n
，并且元素满足i
1
≠1，
i
2
≠2,… ,i
n
≠n, 用D
n
表示{1,2,3,…,n}的错位排列的个数。
[3]


111
n
1

对于
n1
，
D
n
n!

1



1


。
n!

1!2!3!
证明：设A
i
表示 在1,2,3,…,n的全排列中，i处在第i个位置，S为1,2,3,…,n的全排列
的个数。

D
n

nn

A
i1
i< br>S

A
i

i1
由容斥原理，
n 1n12n2n11n
D
n
A
n
C
n
 A
n
C
n
A
1


1
C
n
1

1
C
n
A
n2< br>

1

n1n
将上式左边提取因式n!，

111
n
1

即
D
n
n !

1



1



n!

1!2!3!
证毕!

2.2 相对的禁排位置问题
对于每个正整数n，令Q
n
表示集合{1, 2, 3, … , n}中没有12, 23, …, (n-1)n模式
的排列的个数，利用容斥原理求的Q
n
值。

1 2n1
对于n≥1，
Q
n
n!C
n
!C
n
!(1)
n1
C
n
!
。
[4]
1

n1

1

n2

11
证明：S为1,2,3,…,n的全排列的个数, 设A
i
表示在1,2,3 ,…,n的一个全排列中出现
i(i+1)，i=1,2,3, …,n-1。
因此
Q
n

n1
i1

A
i

A
1
中的排列必定出现12这样的子串, 即对{12,3,4,…,n}进行全排列,所以
有A
1
=(n-1)!。
1
即

A
i
C
n
!

1


n1

i1
n1
对A
i
中任意两个的交，即A
i
∩A
j
，不妨设i
（1） 若j=i+1，则排列中含有ij，j(j+1)，将ij(j+1)视为一个整体，
则有
A
i

A
j


n2

!

（2） 若j≠i+1，则将排列中i(i+1)，j(j+1)分别视为整体，
则有< br>A
i

A
j


n2

!

即
i
1ijn1

A

A< br>j
2
C
n
!

1


n2

用数学归纳法易证
A
i1

A
i2



A
ik


nk

!

12n1
综上所述，
Q
n
n!C
n
!C
n
!(1)
n1
C
n
!
成立。
1

n1

1

n2

1
1
三、 总结
概率问题是研究随机现象统计规律性的学科, 是近代数学的一 个重要组成部
分，生活中概率与统计知识应用非常普遍，科学家对实验统计的数据的分析，企
业 对产品质量检查，产品的市场分析，人口普查，有奖债券，国家彩票等等都
用到了概率与统计学的基本知 识；许多政治选举的结果，医疗上的决定也取
决于统计的数据，因此掌握基本的概率论与数理统计知识并 加以灵活运用非常必
要。

经过上述分析，容斥原理对于解决一些概率论问题是 十分有效的。同样的，
在学习概率论的过程中，对问题进行讨论，深入思考解决一类问题的通用方法，< br>对于提高对概率论的理解具有重要意义。

参考文献：
[1]王勇等.概率论与数理统计.北京：高等教育出版社
[2]廖虎.容斥原理在错位排列中的应用.西华师范大学学报(自然科学版)，2007.
[3]廖虎.容斥原理在错位排列中的应用.西华师范大学学报(自然科学版)，2007.
[4]马光思.组合数学[M].西安:西安电子科技大学出版社，2002.