题目

基数为N的集合X有多少个反对称的二元关系?
急!

提问时间：2020-10-05

答案

我在陈国郧的《离散数学问题解析》里找到了答案：
一个二元关系与一个关系矩阵是一一对应的,所以只要满足条件的二元关系的关系矩阵数目即可.
如果即为对称又为反对称的二元关系,其关系只能是主对角线上元素,故有2^n种；
而反对称的二元关系矩阵满足,若Rij=1则Rji=0(i≠j),即Rij×Rji=0(i≠j).主对角线上的元素可以任取0或1,取法有2^n种.矩阵左下半部与右上半部元素为(n^2-n)/2,记为m,则满足Rij×Rji=0(i≠j)的矩阵数为：
C(0,m)( C(0,m) + C(1,m) + ...+ C(m,m) )+
C(1,m)( C(0,m-1) + C(1,m-1)+ ...+ C(m-1,m-1) )+
...
...
...
C(m-1,m)( C(0,1) + C(1,1) ) +
C(m,m)C(0,0) = C(0,m)×2^m + C(1,m)×2^(m-1) +...+ C(m-1,m)×2 + C(m,m)×1 = 3^m = 3^[(n^2-n)/2]
注：C(i,j)表是从j个元素中取出i个元素的组合数(i