容斥原理与错排公式

luyuanhong

容斥原理与错排公式

原创  湖边男孩  数学谷  2025 年 03 月 29 日

     先思考一个“圆桌夫妻”问题：4 个大学同学聚餐，其中 3 个人携带配偶参加，1 个人单身。在圆桌就餐时为了照顾单身同学的情绪，要求夫妻不相邻；问一共有多少种就座方法？

    解决此类问题的经典方法就是利用容斥原理。根据问题条件和容斥原理，计算步骤如下：

    1、总人数与排列基础

        1.1 人数构成：4 位同学中，3 对夫妻（每对 2 人）和 1 位单身，共 7 人。

        1.2 圆桌排列特性：圆桌旋转视为相同排列，固定一人后转化为线性排列问题。

    2、总排列数

        固定单身同学的位置后，剩余 6 人自由排列的总数为： 6! = 720

    3、应用容斥原理排除夫妻相邻的情况

        3.1 至少一对夫妻相邻的情况：  

      单对夫妻相邻视为一个整体，剩余 5 个元素排列：  

      有  C（3,1）A（2,2）A（5,5）= 720 种  

     （3 对夫妻选 1 对，内部可互换位置，排列数 5! ）。

       3.2 至少两对夫妻相邻的情况：  

     两对夫妻视为整体，剩余 4 个元素排列：  

    有 C（3,2）A（2,2）A（2,2）A（4,4） = 288 种  

     （选 2 对夫妻，每对内部可互换，排列数 4! ）。

      3.3 三对夫妻均相邻的情况：  

     三对夫妻均视为整体，剩余3个元素排列：  

    有  C（3,3）A（2,2）A（2,2）A（2,2）A（3，3） = 48 种

     （三对夫妻全部相邻，内部可互换，排列数 3! ）。

     3.4 容斥计算：  

       720（总数）- 720（至少一对相邻）+ 288（至少两对相邻）- 48（三对全相邻）= 240 种

一、容斥原理

    高中必修一课后阅读材料提到过容斥原理相关知识，此时涉及到的是两个集合。



    推广到三个集合，借助韦恩图有如下表述：



   我们如果想求出三个集合并集的元素个数，就可以用三个集合元素的个数之和减去重复的元素个数。

我们给每个部分一个编号，其中 1 代表黄色圆形、2 代表绿色圆形、3 代表蓝色圆形、4 表示 1 和 2 的交集，5 表示 1 和 3 的交集、6 表示 2 和 3 的交集、7 表示 1 和 2 和 3 三者的交集。

那么最外圈的并集元素个数显然是 1+2+3-4-5-6+7 就能算出来啦。

用自然语言描述就是：

1. 先加起来三个圆；

2. 减去 1 和 2 的交集 4 、减去 1 和 3 的交集 5 、减去 2 和 3 的交集 6 ；

3. 而图形 7 ，在第一步被计算了三次，在第二步又被减去三次，所以一来一回相当于没有计算 7 ，但是 7 显然也是红色形状的组成部分，所以最后再加上 7 ，就得到了红色图形的面积。

n 个集合的容斥原理

基于上面的分析，我们用 来表示三个圆形的面积，那么对于红色形状的面积就可以表示成如下形式：



「进一步的，如果我们把 3 个图形扩展到 4 个图形呢？」

显然可以有如下表述：



「再进一步，如果扩展到 n 个图形呢？」

根据前文中三个集合、四个集合求并集的表示形式，进而可以推出 n 个集合求并集中元素个数的公式：



//以下过程为容斥原理的证明过程，中学阶段不需要掌握（本文选用二项式定理证明，也可以用数学归纳法进行证明）。

现在我们对上述公式进行证明：

1. 左边为 n 个集合的并集，任取其中一个元素 x ；因为集合中元素的互异性显然 x 只计算一次，称 x 的贡献为 1 。





二、错排公式的推导及应用

图片5

    现在我们考虑 n 个元素的一个错排，每一个大写字母都不能排到下方其对应的小写字母的位置。



//1 个元素的错排数为 0 ，2 个元素的错排数为 1 。高中阶段的错排问题一般不会超过 6 ，所以上述递推公式已经足以解决高考范围内的错排问题。

如《导学案·练习册》13 页第 6 题



//先将第一列全排列有 A（3,3）种，第二列错排有 a(3)=2(0+1) 种。

错排数公式为：



    证明 1 、由递推关系构造数列求解



    证明 2 、由容斥原理推导





作者为一线高中教师，创建公众号是为了记录自己在解题方面的想法。行笔匆匆，难免有误；欢迎读者们在留言区批评指正。

数学谷