本文主要是介绍集合A(|A|=n)上可以定义多少种不同的等价关系，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
离散笔记
- 集合A(|A|=n)上可以定义多少种不同的等价关系？
- 看个栗子
- 再看一个例子
- 一个直观的递归想法
- 代入递归思想
- 一般规律
- 拓展
- 思考
集合A(|A|=n)上可以定义多少种不同的等价关系？
一个包含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种划分；
。。。
嗯！思考一下，我们可以归纳嘛！
找规律！！
| n=1 | 1 |
|---|---|
| n=2 | 2 |
| n=3 | 5 |
| n=4 | 15 |
| – | – |
| n=n | ? |
能看出规律吗？
不等差也不等比！
-------------------------------------------------------------------（这是一条无情的分割线）
看来没那么容易找规律？
一个直观的递归想法
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上的划分有如下四种情况：
- 元素4被单独分为一类，剩余3个元素随便划分，这样的划分总共有 B 3 B_3 B3种；
- 元素4与另3个元素中的某一个一起被分为一类，剩余2个元素随便划分，这样的划分总共有 B 2 B_2 B2种；
- 元素4与另3个元素中的某2个一起被分为一类，剩余1个元素随便划分，这样的划分总共有 B 1 B_1 B1种；
- 元素4与另3个元素一起被分为一类，剩余0个元素随便划分，这样的划分总共有 B 0 B_0 B0种；
哦哦哦出来了，出来了！！，
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=C30B3+C31B2+C32B1+C33B0
一般规律
集合 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−10Bn−1种；
元素 a n a_n an和剩余n-1个中抽取的某个元素分为一类，剩余n-2个元素随便划分，划分总共有 C n − 1 1 B n − 2 C_{n-1}^1B_{n-2} Cn−11Bn−2种；
元素 a n a_n an和剩余n-1个中抽取的某两个元素分为一类，剩余n-3个元素随便划分，划分总共有 C n − 1 2 B n − 3 C_{n-1}^2B_{n-3} Cn−12Bn−3种；
元素 a n a_n an和剩余n-1个中抽取的某三个元素分为一类，剩余n-4个元素随便划分，划分总共有 C n − 1 3 B n − 4 C_{n-1}^3B_{n-4} Cn−13Bn−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−1B0种；
因此，我们有
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−10Bn−1+Cn−11Bn−2+Cn−12Bn−3+Cn−13Bn−4+......+Cn−1n−1B0
这就是递归定义出来的结果！
我们可以一一验证是正确的。
拓展
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是不一样的。
你能从中得到规律吗？
期待不同的回答。
这篇关于集合A(|A|=n)上可以定义多少种不同的等价关系的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
