离散数学N元集合关系个数计算

Author：ssjsMail：[e-mail]看了离散数学中的关系整理了一点关于n元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。如有错误之处请指正。定义：1，对称：对于a,bRab),b(),a(,A有如果只要2，反对称：如果RabRbabb),(),(a,A,a和时仅当3，自反：如果对每个元素R),(Aaaa有4，反自反：如果对于每个R),(Aaaa有5，传递：如果对R),(,R),(R),(,A,,cacbbacba则且6，非对称：如果R),(R),(abba推出【注】其中是含（a,a)这样的有序对的。【重要】集合A的关系是从A到A的关系（也就是说集合A的关系是AA的子集）。如下结论：N元集合上的自反关系数为：)1(2nnN元集合上的对称关系数为：2/)1(2nnN元集合上的反对称关系数为：2/)1(n32nnN元集合上的非对称关系数为：2/)1(3nnN元集合上的反自反关系数为：)1(n2nN元集合上的自反和对称关系数为：2/)1(n2nN元集合上的不自反也不反自反关系数为：)1(nn2222n下面是上面结论的计算1，自反2AA,Ann因为也就是说集合A有n平方个有序对，由自反定义可知，对R),(Aaaa有所以n个有序对).....3,2,1iX,X(nii其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有nn2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n222nnn下图有助于理解。（1,1)(2,2).......(n,n)|(1,2)(1,3).........(n-1,n)N个有序对nn2个有序对2，对称2AA,Ann因为也就是说集合A有n平方个有序对，由对称定义可知，对于Rabb),b(),a(,A,a有只要。另外知道在n平方个有序对中有n个有序对).....3,2,1iX,X(nii其中，相应的就有nn2个有序对（X,Y)且XY，定义可知后面的nn2个有序对只能成对出现，所以有2/)(n2n对。前面的那n对可以出现任意多对。图片如下。（1,1)(2,2).......(n,n)(1,2)(1,3).........(n-1,n)n个有序对(2,1)(3,1).........(n,n-1)(nn2)/2个有序对对共有n+(nn2)/2个元素即(nn2)/2个所以得到对称关系数为：2/)1(2nn3，反自反2AA,Ann因为也就是说集合A有n平方个有序对，由对称定义可知，如果对于每个R),(Aaaa有，构成该关系的元素个数为nn2个，所以得出结论)1(n2n，这个简单，不多说。4，自反和对称即是求自反的又对称的，由1知要是自反的就只能在nn2个有序对中生成子集，又由对称定义可知，将nn2个有序对分成形如(a,b)与(b,a)的(nn2)/2个有序对对。所以有自反和对称关系数为：2/)1(n2n。如下图（1,1)(2,2).......(n,n)(1,2)(1,3).........(n-1,n)n个有序对(2,1)(3,1).........(n,n-1)要自反这n个必在所求关系中(nn2)/2个有序对对N个有序对只有1种可能·有2/)1(n2n种可能=2/)1(n21n5，不自反也不反自反不自反也不反自反=不自反不反自反=）不反自反不自反（2n2=反自反）（自反2n2=)22(2)1()1(n2nnnn=)1(n2222nn6，非对称由定义：如果R),(R),(abba推出，很清楚形如(a,a)的有序对不在所求关系中。所以所求关系只能中剩下的nn2个有序对中来生成。如下图。（1,1)(2,2).......(n,n)(1,2)(1,3)...................................(n-1,n)n个有序对(2,1)(3,1)....................................(n,n-1)这n个一定不在所求关系中(nn2)/2个有序对对由定义上图的同色对中只能取一个或是一个也不取，就有三种状态1）选上面的2）选下面的3）两个都不选选取同色对？01不选选上还是选下？01选上选下由题知，不选，选上，选下是三种互斥结果。同集合二进制求集合个数原理，可得集合子集个为：2/)1(3nn7，反对称由定义：如果RabRbabb),(),(a,A,a和时仅当如下图。（1,1)(2,2)......................(n,n)(1,2)(1,3)...................................(n-1,n)n个有序对(2,1)(3,1)...................................(n,n-1)这n个有序对可以出现任意多次(nn2)/2个有序对对n22/)1(3nn(由6可知）所以得结果：n22/)1(3nn即2/)1(n32nn【注】其它组合或是要求可由定义同理推出。不要怕麻烦，其实不那么难，也还有许多方法可以导出结果，如矩阵之类的。强烈推荐看下DiscreteMathematicsandItsApplicationsSeventhEdition更新版的更好哈，讲得真的很不错。参考资料：DiscreteMathematicsandItsApplicationsSeventhEdition