容斥原理在组合学中的相关应用

姚箫生

摘 要：人类在发展生产和生活的过程中，难免会遇到很多计数问题，而有些计数问题，用直接的方法比较难以解决，在前人的经验基础之上，人们探索并创立了一种新的计数方法，其中就有容斥原理。本文通过研究运用容斥原理解决组合学中的组合计数问题的相关步骤及相关的题型，总结哪类组合计数问题可以运用容斥原理解决以及容斥原理解决这类问题的相关步骤。

关键词：容斥原理;排列;组合学

本文的工作就是总结出哪类组合计数问题可以运用容斥原理解决，以及总结出运用容斥原理解决这类组合计数问题的大致步骤。

本文主要讨论容斥原理在组合学中的应用。

1 容斥原理

容斥原理是由英国数学家詹姆斯·约瑟夫·西尔维斯特19世纪首次创立[10]。

我们知道运用容斥原理求解问题时，是将直接求解转换为间接求解，我们大学学过一个简单的定理，De Morgan定理。

1.1 De Morgan定理：若A和B是全集U的子集，则：

⑴∩;

⑵.

运用容斥原理求解时常会用到一些简单但又重要的基本公式。

1.2基本公式：设S是有限集，A、B、C∈S

⑴当时，;

⑵当时，;

⑶;

⑷;

⑸。

在求解问题时，我们要解决的要么是求，或是求，这两个我们其实可以把它们看成是对偶的，求解上述两个公式的值，就需要用到文献[11]中的两个定理：

2 容斥原理在组合计数中的相关应用

2.1 对元素在位置上存在限制的计数问题

这类问题也称为“错排问题”或者“重排问题”，由于错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利—欧拉的装错信封问题：在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？其已有的结果是共有种不同的装法。

例（排课表问题）某班级某一天的课程安排表要安排6门课程：语文、数学、英语、物理、化学、生物，规定每门课上仅且上一节，一天共安排六節课，并且生物不排在第一节，数学不排在最后一节，那么符合这种规定的课表有多少种不同的排法？

解 设所求结果数为N，令S表示为这六门课做成所有不同全排列所成之集，A表示为生物课排在第一节做成的所有不同全排列所成之集，B表示为数学课排在最后一节做成的所有不同全排列所成之集。则，我们可以得到：

，S为有限集，A、B∈S。

由1.4得：

=504

答：符合规定的课表有504种排法。

2.2 对元素相邻位置存在限制的计数问题

此类问题亦称为“夫妻问题”，最先是由法国数学家鲁卡斯在1891年提出的：今需安排n对夫妻围圆桌（2n个座位已编号）而坐，男女相间，夫妻不相邻，问有多少种不同的安排座法？已有的结果为：。

例甲、乙、丙、丁四名同学到一所学校实习，现有四个班级A、B、C、D，现将甲、乙、丙、丁四名同学分别分到这四个班级中，每个班级有且仅有一名同学，同时要求甲、乙两名同学所分到的班级不相邻，丙、丁两名同学所分到的班级不相邻，试问满足这种条件的排法有多少种？

解 设所求结果数为N，令S表示为四名同学做成的所有不同全排列所成之集，A表示为甲、乙两名同学所在班级相邻做成的所有不同全排列所成之集，B表示为丙、丁两名同学所在班级相邻做成的所有不同全排列所成之集，同时把甲、乙两名同学捆绑在一起算作一个，把丙、丁两名同学捆绑在一起算作一个，则我们可以得到：

，S有限集，A、B∈S

由1.4得：

答：满足题中所述条件的排法有8种。

3 容斥原理求解组合计数问题的步骤总结

第一种：能够直接利用容斥原理解决的，即限制的是元素位置的计数问题。

第1步：先用N表示为所求结果数，然后再用一个大写字母S（可以是任意一个不同于N的字母）表示为n个相异元组成的所有不同全排列所成之集，并求出这个全排列的个数。

第2步：如果题目中存在个限制性条件，则我们用不同于第1步的相应个数的大写字母A，B，C···表示出这k个限制性条件的否定做成的所有不同全排列所成之集。同时也求出相应的排列个数等。（这些排列个数的求法在高中已经学过，在此就不再给出方法）

第3步：利用公式求出具体的结果。

第二种：无法直接利用容斥原理解决的，即限制元的条件不是在位置上，而是其他一些限制的计数问题。

第1步：首先我们在题目中所给的集合中任取出一个元素，用s（可以是任意一个小写字母）表示，若s满足题中条件的肯定，则用表示s具有相对应的性质。（此处“条件的肯定”是指不出现否定词，如：不能被7和9整除的，我们要改成“能被7和9整除”，如果题目中的限制条件本来不含有否定词，则不用改。）

第2步：运用进行求解即可。其中以表示S中不具有中任一个性质的元素个数 。若第i个限制条件已经是肯定的了，我们就不用1去减了，直接写上ai，同时在等号前面里，ai不需要标上标。

通过上述例题的求解，我们不难发现，运用容斥原理求解排列组合计数问题的时候，就是把直接求解转换为间接求解，且在计算的过程中，若过多算了，我们就排除多算的部分，如果排除的多了，我们就再加上多排除的部分，如此类推下去，直至所求结果既不多也不少。这就是应用容斥原理求解的核心思路。

参考文献：

[1]曹汝成.广义容斥原理及其应用[J].数学研究与评论，1988，8（4）：526-530.

[2]孙淑玲，许胤龙.组合数学引论[M].合肥：中国科技大学出版社，1999，97-119.

[3]潘永亮，徐俊明.组合数学[M].北京：科学出版社，2006，43-46.

[4]卢开澄，卢华明.组合数学[M]（第4版）.北京：清华大学出版社，2006，119-133.

3908500338213