集合A(

一个包含n元素的集合A，有 2 n 2^{n} 2n个子集， A × A A \times A A×A笛卡尔积集合中有 n 2 n^2 n2个元素，对应的不同的二元关系（子集）有 2 n × n 2^{n \times n} 2n×n个，那其中有多少个为等价关系呢？

例： 求出A＝{1,2,3}上所有的等价关系 求解思路：先求出A的所有划分, 然后根据划分写出对应的等价关系。

划分和等价关系为一一对应关系 划分里的元素即为等价关系得到的等价类 也就是说，划分即为商集

可见对应有五个等价关系。 让我们看看有什么规律：

每个划分块里面的元素范围为：[1,n] 每个划分块非空 每个划分块不交 所有划分块的并集为集合A本身

n=1时,只有一个划分； n=2时,一个划分块的情形有1个,2个划分块的有1个,共2种划分； n=3时,一个划分块的情形有1个,2个划分块的有3个,3个划分块的有1个,共5种划分； 。。。

嗯！思考一下，我们可以归纳嘛！

找规律！！

能看出规律吗？ 不等差也不等比！ -------------------------------------------------------------------（这是一条无情的分割线） 看来没那么容易找规律？

f ( n ) = 操 作 ∗ f ( n − 1 ) + C f(n)=操作*f(n-1)+C f(n)=操作∗f(n−1)+C 是不是适用呢？

一般地，非空集合A上的等价关系与A上的划分一一对应。设n元集合上的划分有 B n B_n Bn​种。    例2：设A={1,2,3,4}，则A上的划分有如下四种情况：

哦哦哦出来了，出来了！！， B 0 = 0 B_0=0 B0​=0， B 1 = 1 B_1=1 B1​=1呀， （于是我们得到了结论） 并且其中

元素4和抽取的其他某个元素分为一类，满足组合形式即为 C 3 1 C_3^1 C31​ 元素4和抽取的其他两个元素分为一类，满足组合形式即为 C 3 2 C_3^2 C32​ 元素4和抽取的其他三个元素分为一类，满足组合形式即为 C 3 3 C_3^3 C33​ 同理 元素4和抽取的其他0个元素分为一类，满足组合形式即为 C 3 0 C_3^0 C30​

因此，我们有 B 4 = C 3 0 B 3 + C 3 1 B 2 + C 3 2 B 1 + C 3 3 B 0 B_4=C_3^0B_3+C_3^1B_2+C_3^2B_1+C_3^3B_0 B4​=C30​B3​+C31​B2​+C32​B1​+C33​B0​

集合 A ( ∣ A ∣ = n ) = { a 1 , a 2 , . . . , a n } A(|A|=n)=\{ a_1,a_2,...,a_n\} A(∣A∣=n)={a1​,a2​,...,an​}上可以定义多少种不同的等价关系？

元素 a n a_n an​被单独分为一类，剩余n-1个元素随便划分，这样的划分总共有 C n − 1 0 B n − 1 C_{n-1}^0B_{n-1} Cn−10​Bn−1​种； 元素 a n a_n an​和剩余n-1个中抽取的某个元素分为一类，剩余n-2个元素随便划分，划分总共有 C n − 1 1 B n − 2 C_{n-1}^1B_{n-2} Cn−11​Bn−2​种； 元素 a n a_n an​和剩余n-1个中抽取的某两个元素分为一类，剩余n-3个元素随便划分，划分总共有 C n − 1 2 B n − 3 C_{n-1}^2B_{n-3} Cn−12​Bn−3​种； 元素 a n a_n an​和剩余n-1个中抽取的某三个元素分为一类，剩余n-4个元素随便划分，划分总共有 C n − 1 3 B n − 4 C_{n-1}^3B_{n-4} Cn−13​Bn−4​种； … … 元素 a n a_n an​和剩余n-1个中抽取的n-1个元素分为一类，剩余0个元素随便划分，划分总共有 C n − 1 n − 1 B 0 C_{n-1}^{n-1}B_{0} Cn−1n−1​B0​种；

因此，我们有 B n = C n − 1 0 B n − 1 + C n − 1 1 B n − 2 + C n − 1 2 B n − 3 + C n − 1 3 B n − 4 + . . . . . . + C n − 1 n − 1 B 0 B_n= C_{n-1}^0B_{n-1}+ C_{n-1}^1B_{n-2}+ C_{n-1}^2B_{n-3}+ C_{n-1}^3B_{n-4}+......+ C_{n-1}^{n-1}B_{0} Bn​=Cn−10​Bn−1​+Cn−11​Bn−2​+Cn−12​Bn−3​+Cn−13​Bn−4​+......+Cn−1n−1​B0​

这就是递归定义出来的结果！ 我们可以一一验证是正确的。

B n B_n Bn​被称为 Bell Number 详情请见：https://mathworld.wolfram.com/BellNumber.html

还有别的方法吗？ 例如： 划分即为序列插空分成若干部分，每部分非空不交，即： a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​

若分成n部分，即： a 1 ∣ a 2 ∣ . . . ∣ a n a_1 | a_2| ...|a_n a1​∣a2​∣...∣an​

若分成2部分，即为 a 1 ∣ a 2 , . . . , a n a_1|a_2,...,a_n a1​∣a2​,...,an​或 a 1 , a 2 ∣ . . . , a n a_1,a_2 | ...,a_n a1​,a2​∣...,an​，或 a 1 , a 2 , a 3 , ∣ . . . , a n a_1,a_2,a_3,|...,a_n a1​,a2​,a3​,∣...,an​等。 此外，还需要考虑序列的排序，因为 a 1 ∣ a 2 , . . . , a n a_1|a_2,...,a_n a1​∣a2​,...,an​和 a 2 , ∣ a 2 , . . . , a n a_2,|a_2,...,a_n a2​,∣a2​,...,an​是不一样的。

你能从中得到规律吗？ 期待不同的回答。