容斥原理及其应用表现形式

摘要：容斥原理是组合数学中的重要计数原理.本文归纳总结了容斥原理的一些表现形式，重点讨论了容斥原理在数学各分支中的若干应用.

关键词：容斥原理；组合计数；应用.66685

一、前沿介绍

容斥原理是组合数学中一种重要而基础的计数原理，不仅在组合数学中有着重要的作用，而且在数学其他分支以及其他学科中也被广泛应用到.近年来，基于容斥原理的各项研究也日益增多. 本文主要在已有结果的基础上，总结容斥原理的一些性质及其在数学各分支中的应用.文献综述

二、正文

1 容斥原理的表现形式

首先给出容斥原理最常见的简单形式，即下面的定理1：

定理1[1]：设S是有限集合，P1，P2，…，Pn则是与集合S中元素有关的n个性质，令Ai为具有性质Pi的S子集，，其中i = 1，2，…，n，则有

(1) S中不具有性质P1，P2，…，Pn的元素个数为

○1

(2) S中至少具有P1，P2，…，Pn其中一条性质的元素个数为

○2

注1.1：式和式分别反映了同一问题相反的两方面，可以互相推导.

接下来给出容斥原理的一般形式：

定理2[2]：设S，P1，P2，…，Pn如上，令N(r)为集合S中同时具有Pi (i = 1，2，…，n)中恰好r个性质的元素个数，则有

○3

其中W(r)为同时具有r个性质的所有元素的权的和.

注2.1：W(r)求和就是对P={P1，P2，…，Pn}的所有r-子集进行求和.

注2.2：当r=0时，令W(0)为S中所有元素的权的和，则N(0)为S中不具有Pi (i = 1，2，…，n)中任何性质的元素数为，有

○4

2 容斥原理在组合数学中的应用

2.1 错位排列问题论文网

错位排列是具有限制的全排列的一种.若Z={1，2，…，n}的一个全排列i1i2…in满足条件ij ≠ j( j=1，2，…，n)，则称其为Z的一个错位排列.

例2.1给n个人照相后，把照片分别装入n个纸袋里分给每个人，求问：没有任何一个人得到装有自己照片的纸袋的情况有多少种？

分析：想要求解没有任何一个人得到自己的照片的可能情况，只要用所有的可能情况删去每个人得到自己照片的可能就可以得出.取n张照片构成集合X={1，2，…，n}，其中每张照片的位置都由它们在序列1，2，…，n中的位置确定.将n张照片进行排列i1i2…in，没有任何一个人得到自己的照片就是指没有一张照片在它指定的位置上，即ij≠j ( j=1，2，…，n).因此例题所求的就是集合X的所有错位排列的数目，可以运用容斥原理在X的所有全排列构成的集合中删去满足条件ij = j的全排列来进行求解.

解:设集合S是由X的所有全排列构成的.对于X的一个全排列i1i2…in，若有ij = j (j=1，2，…，n)，则称这种排列具有性质Pj.令Aj为具有性质Pj的X的全排列，则X所有错位排列组成的集合为

在A1中的排列是1 i2…in形式的排列，其中i2…in是的{2，…，n}一个排列，于是| A1 |=(n-1)!，同理，对于j=1，2，…，n，有| Aj |=( n-1)!

在A1∩A2中的排列是1 i3…in形式的排列，其中i3…in是的{2，…，n}一个排列，于是| A1∩A2 |=(n-2)!，同理，对于X中的任意2-组合{i ， j}，有| Ai∩Aj |=(n-2)! 容斥原理及其应用表现形式:http://www.751com.cn/shuxue/lunwen_74670.html