Question

集合A，|A|=n, 求在A上有多少个不同的等价关系？

http://zhidao.baidu.com/question/473375970.html?quesup2

Answer 1

集合A上的等价关系与集合A的划分是一一对应的，集合的划分就是把集合分解为几个不相交的非空子集的并集。
n=1时，只有一个划分；
n=2时，一个划分块的情形有1个，2个划分块的有1个，共2种划分；
n=3时，一个划分块的情形有1个，2个划分块的有3个，3个划分块的有1个，共5种划分；
.....
构造递推关系式，可推出一个公式：n个元素的集合上的等价关系有(2n)! / [(n+1)*n!*n!]个。