定义在n个元素上的集合A之上的等价关系共有多少种？

Question

定义在n个元素上的集合A之上的等价关系共有多少种？

Answer 1

在一个集合定义一个等价关系相当于把这个集合划分成许多子集的集。（这里假如不懂请追问） 于是求等价关系的数目，就是求划分的数目。 这其实是个定理，这个数叫Bell数。 Bell数没有通项公式，但我们有一个递推公式： B(n+1)=C(0,n)B(0)+C(1,n)B(1)+...+C(n,n)B(n)，C(k,n)就是在n个数里选k的数的选法个数。 这个很好证明：取第n+1个数，并考虑除了含有它的那个部分以外所有其他的部分。含有它的部分的元素个数从1到n+1都有可能，而剩下的数就是从n到0。而每次我们可以挑选剩下来的数，所以就有C(k,n)。 Bell数的前几项是： B(0)=1,B(1)=1,B(2)=2,B(3)=5,B(4)=15,B(5)=52,B(6)=203。 从上面的递推公式我们还可以得到下面的表达式：(Dobinski公式) B(n)=(1/e)(1^n/n!+2^n/n!+3^n/n!...)（一直加到正无穷） 这个其实就是泊松分布的第n个矩。 不懂请追问，这个问题太大了，很难短时间说清楚。