一个n元有限集上的等价关系的个数并详细证明

一个n元有限集上的等价关系的个数为Bell数Bn。

证明：

我们可以将一个n元有限集上的等价关系表示为一个由若干个不相交的等价类组成的集合。因此，问题转化为求一个n元有限集的所有划分的个数。

设Pn表示n元集合的所有划分的个数。我们考虑对n个元素进行分类，将它们划分为若干个非空子集。首先，我们可以选择一个元素作为集合中一个子集的唯一元素，然后将剩下的n-1个元素划分为若干个非空子集。这样，我们就将问题转化为对n-1个元素进行分类，将它们划分为若干个非空子集。

因此，有递推公式Pn = Pn-1 + Pn-2 + … + P1 + 1 (其中，P1=1表示只有一个元素时只有一种划分，即它本身)。

这是因为对于n个元素的划分，我们可以按照最后一个元素所在的子集来分类，如果它是一个单独的子集，那么前面n-1个元素的划分数为Pn-1；如果它和其他元素在同一个子集中，那么前面n-1个元素的划分数为Pn-2；以此类推。

根据递推公式，我们可以得到P2=2，P3=5，P4=15，P5=52，P6=203，P7=877，P8=4140，P9=21147，P10=115975，P11=678570，P12=4213597，P13=27644437，P14=190899322，P15=1382958545，P16=10480142147，P17=82864869804，P18=682076806159，P19=5832742205057，P20=51724158235372。

这些数就是Bell数Bn。因此，一个n元有限集上的等价关系的个数为Bell数Bn