一些特殊传递关系的计数

Counting Some Special Transitive Relations

有限集合S上的关系是直积S×S的一个子集,可由布尔矩阵表示。至今,有限集合上传递关系个数的计算公式仍未找到。记T(n,c)为具有c列非0列的n阶传递布尔矩阵的个数,我们得到了T(n,c)当c=1,2,3时的计数公式。

A relation on a set S is a subset of the product set S × S, and can be represented by a Boolean matrix. So far, there is no general formula that counts the number of transitive relations on a finite set. Let T（n,c） denote the number of transitive Boolean matrix of order n with c non-zero columns, we give the formula of T（n,c） when c ： 1,2,3.