一个有n个元素的集合，有多少种不同的自反的二元关系？

Question

如题所述

Answer 1

一个二元关系与一个关系矩阵是一一对应的，所以只要满足条件的二元关系的关系矩阵数目即可。
如果即为对称又为反对称的二元关系，其关系只能是主对角线上元素，故有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<=j)
故反对称的二元关系有2^n×3^[(n^2-n)/2]

Answer 2

离散数学 2^(n-1) 每个元素都有两个位置可以选择，一共有2^n 两边的位置重复了一倍再除以2即可

Answer 3

C(2,n)种