Question

5个元素的集合有多少种等价关系？

Answer 1

http://hi.baidu.com/lca001/blog/item/92f236c3d7e98927e4dd3b24.html
集合上每个等价关系对应集合的一种划分,集合的每一种划分又对应于该集合的一个等价关系,不同的等价关系对应于集合的划分也不同,因此集合有多少不同划分,就有多少不同等价关系,用Bn表示n个元素集合X的划分个数,其中称Bn为Bell数,关于Bell数有如下递推公式：
Bn+1=C(n,0)B0+ C(n,1)B1+ C(n,2)B2+…+ C(n,n)Bn
其中B0=1, C(n,k)是个n元数取k个元的组合数,利用公式可以计算出前几个Bell数:
B1= C(0,0)B0=1×1=1，
B2= C(1,0)B0+ C(1,1)B1=1×1+1×1=2，
B3= C(2,0)B0+ C(2,1)B1+ C(2,2) B2=1×1+2×1+1×2=5，
B4= C(3,0)B0+ C(3,1)B1+ C(3,2) B2+ C(3,3) B3=1+3+6+5=15，
B5= C(4,0)B0+ C(4,1)B1+ C(4,2) B2+ C(4,3) B3+ C(4,4) B4
=1+4+12+20+15=52，
故5个元素的集合的等价关系有52种。