离散数学：详细解说集合上各种特殊类型的关系有多少个？

罗光宣

一、各类关系数量汇总表

设集合  为 元有限集，即  上二元关系总数为 。各类特殊关系的数量整理如下：

前置基础

集合 ，二元关系 。              
 共有  个有序对，分为三类：

1.对角线元素：，共  个；

2.非对角线有序对：分为成对的  与 ，共  组。

所有关系计数，本质是对这两类有序对做选取约束。

二、逐个详细解释

1. 自反关系：

定义约束：所有对角线元素  必须全部在关系  中，不能缺少。

·对角线  个有序对：强制全部选取，无选择余地；

·剩余  个非对角线有序对：每个都可以自由选择“选/不选”，各有2种可能。                
由乘法原理，总数为：。

2. 反自反关系：

定义约束：所有对角线元素  必须全部不在关系  中。

·对角线  个有序对：强制全部不选取；

·剩余  个非对角线有序对：依旧自由选择。                
因此数量和自反关系完全相同：。

3. 对称关系：

定义约束：若 ，则 ，有序对必须成对出现。

·对角线  个有序对：可自由选或不选，共  种；

·非对角线的  组有序对：每组必须同时选或同时不选，共  种。                
两者相乘：                

4. 反对称关系：

定义约束：若 ，则  和  不能同时在  中。

·对角线  个有序对：自由选取，共  种；

·每一组非对角线有序对，有3种合法选择：只选前者、只选后者、两者都不选；

· 组共有  种选法。                
总数为：。

5. 既不对称、也不反对称的关系

公式：
采用容斥原理计算：

1.总关系数：

2.减去对称关系数、反对称关系数；

3.加回重复扣除的部分：既对称又反对称的关系。                
这类关系要求：非对角线有序对全部不选，仅对角线可自由选，共  个。

因此：                

代入后即得最终公式。