一个有n个元素的集合，有多少种不同的自反的二元关系？
3个回答
展开全部
一个二元关系与一个关系矩阵是一一对应的，所以只要满足条件的二元关系的关系矩阵数目即可。
如果即为对称又为反对称的二元关系，其关系只能是主对角线上元素，故有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]
如果即为对称又为反对称的二元关系，其关系只能是主对角线上元素，故有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]
已赞过
已踩过<
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
