组合数学3

例8.9

设A为n元集，A上可定义 `2^n` 个不同的二元关系，其中有

(1)多少个自反的二元关系？

(2)多少个对称的二元关系？

(3)多少个反对称的二元关系？

答案，(1)自反关系有`2^((n^2 +n )/2)`个;

(2)对应关系有`2^((n^2+n)/2)`个

(3)反对称关系有`2^n 3^((n(n-1))/2)`个.

分析，考虑关系矩阵。

(1)自反关系矩阵的主对角线元素全是1，其他元素可以是1也可以是0，由于主对角线有n个，其他元素有`n^2-n`个。每个元素有2种选择，根据乘法法则，有`2^(n^2-n)`个自反的关系。

(2)对称关系的矩阵是对称矩阵，为此仅需考虑上三角或下三角矩阵(含主对角线元素在内)。以上三角矩阵为例,含`(n^2 +n)/2`个元素。每个元素可以有1和0两种选择，因此这种矩阵的个数是`2^((n^2+n)/2)`,从而对称关系有`2^((n^2+n)/2)`个。

(3)反对称关系的矩阵中主对角线元素可以有1和0两种选择，共有`2^n`种方式。其他元素以主对角线为界其位置成对称分布。位置对称的元素`r_(ij)`和`r_(ji)`的选择可以是0和0、0和1、1和0这三种可能。这样的元素有`(n(n-1))/2`对，根据乘法法则有`2^n3^((n(n-1))/2)`个反对称关系。