【集合论】等价关系个数计算问题 ( 有序对个数计算 | 二元关系个数计算 | 划分 | 等价关系 )

韩曙亮

发布于 2023-03-27 16:21:03

1.4K0

发布于 2023-03-27 16:21:03

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

等价关系与划分对应问题

等价关系与划分计算 :

1.等价关于与划分一一对应 : 非空集合

上的等价关系与

上的划分是一一对应的 ; (

上有多少个不同的等价关系 , 就产生同样个数的不同的划分 )

2.数学模型 : 将

个不同的球 , 放入

个相同的盒子中 , 并且不能出现空盒 ,

n \geq r

; 不同的放球方法对应不同的划分数 ;

3.第二类 Stirling 数 : 将

个不同的球, 放入

个相同的盒子中 , 方案数记做

S(n,r)

, 或

\begin{Bmatrix} n \\ r \end{Bmatrix}

;

第二类斯特林数计算公式

第二类 Stirling 数计算方法 :

1.Stirling 数计算公式 :
- ①
S(n,0) = 0
- ②
S(n,1) = 1
- ③
S(n,2) = 2^{n-1} - 1
- ④
S(n,n-1) = C(n, 2)
- ⑤
S(n,n) = 1
2.Stirling 数递推公式 :

S(n,r) = rS(n-1, r) + S(n-1, r-1)

4元集等价关系计算

题目 : 等价关系

条件 : 集合

A = \{a,b,c,d\}

;

问题 : 上述集合有多少等价关系 ;

解答 :

分析 :

1.有序对个数 : 集合

上有

4 \times 4 = 16

个有序对 ;

2.二元关系个数 : 集合

上的二元关系个数是

2^{有序对个数} = 2^{16}

个 ;

① 公式推演 : 每个二元关系有

到

个不等的有序对个数 , 分别统计有

个有序对 ,

\cdots

个有序对的情况 ;

② 计算过程 :

C(16, 0) + C(16, 1) + C(16,2) + \cdots + C(16, 16) = 2^{16}

;

3.无法直接得出等价关系数 :

上有

2^{16}

个二元关系 , 逐个验证等价关系要求的自反 , 对称 , 传递性质 , 肯定行不通 , 计算量巨大 ;

4.求划分个数 : 集合

的等价关系个数与划分个数是一一对应的 , 因此求其划分个数即可 ;

分步求解 :

① 使用第二类 Stirling 求其不同的划分个数 :

S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4)

② 根据公式 :

S(n,1) = 1

, 计算 Stirling 数的值 :

S(4, 1) = 1

③ 根据公式 :

S(n,2) = 2^{n-1} - 1

, 计算 Stirling 数的值 :

S(4, 2) = 2^{4 - 1} - 1 = 2^3 -1=7

④ 根据公式1 :

S(n,n-1) = C(n, 2)

( Stirling 数计算公式 ) , 根据公式2 :

C(n, r) = \cfrac{n!}{(n-r)!r!}

, 计算 Stirling 数的值 :

S(4, 2) = C(4,2) =\dbinom{4}{2} =\cfrac{4!}{(4-2)!2!} = \cfrac{4 \times 3 \times 2 \times 1}{2 \times 2} = 6

⑤ 根据公式 :

S(n,n) = 1

, 计算 Stirling 数的值 :

S(4, 4) = 1

⑥ 最终划分结果 :

上有 15 个划分 ;

S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4) = 1 + 7 + 6 + 1 = 15

6元集等价关系计算

题目 :

条件 :

A=\{1,2,3,4,5,6\}

问题 : 计算

上的二元关系的个数和

上等价关系的个数 ;

解答 :

二元关系个数 :

1> 集合元素个数 : 集合

中有

个元素 ,

|A| = 6

;

2> 有序对个数 :

|A| \times |A| = 6 \times 6 = 36

;

3> 二元关系个数 :
- ① 推演过程 : 二元关系包含
0
到
36
不等的有序对 , 那么需要考虑以上所有情况 , 分别统计有
0
个有序对 ,
1
个有序对 ,
2
个有序对 ,
\cdots
,
36
个有序对的情况 ;
- ② 计算公式 :
C(36, 0) + C(36, 1) + C(36,2) + \cdots + C(36, 36) = 2^{36}

等价关系个数 :

1> 一一对应 : 等价关系的个数与集合的划分数是一一对应的 ,
2> 进行划分 : 将集合

划分成

块 ,

块,

块 ;

3>写出对应式子 : 集合的划分数为

S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6)

逐个求出

S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6)

每个 Stirling 数的值 ;

① 根据公式 :

S(n,1) = 1

, 计算 Stirling 数的值 :

S(6, 1) = 1

② 根据公式 :

S(n,2) = 2^{n-1} - 1

, 计算 Stirling 数的值 :

S(6, 2) = 2^{6-1} - 1 = 2^5 - 1 = 32 - 1 = 31

③ 根据递推公式 :

S(n,r) = rS(n-1, r) + S(n-1, r-1)

, 计算 Stirling 数的值 :

S(6, 3) = 3S(5,3) + S(5,2)

拆分成下面两部进行计算 :

( 1 ) 先计算

S(5, 3) = 3S(4,3) + S(4,2)

1> 其中使用公式

S(n, n-1) = C(n,2)

计算

S(4,3)

S(4,3) = C(4,2) = \dbinom{4}{2} = \cfrac{4!}{(4-2)! \times 2!} = \cfrac{4 \times 3 \times 2 \times 1}{2 \times 2} = 6

2> 使用公式

S(n, 2) = 2^{n-1} - 1

计算

S(4,2)

S(4,2) = 2^{4-1} - 1 = 7

S(5, 3)

结果 :

S(5, 3) = 3S(4,3) + S(4,2) =3\times 6 + 7 =25

( 2 ) 在计算

S(5,2)

的结果 , 使用公式

S(n, 2) = 2^{n-1} - 1

进行计算 :

S(5, 2) = 2^{5-1} - 1 =15

( 3 ) 最终结果 :

S(6, 3) = 3S(5,3) + S(5,2) = 3\times25 + 15 =90

④ 根据递推公式 :

S(n,r) = rS(n-1, r) + S(n-1, r-1)

, 计算 Stirling 数的值 :

S(6, 4) = 4S(5,4) + S(5,3) = 4\times C(5,2) + 25 = 4\times \cfrac{5!}{3!\times2!}+25 = 4\times \cfrac{5\times4\times3\times2}{3\times2\times2}+25=65

⑤ 根据公式 :

S(n, n-1)= C(n,2)

, 计算

S(6,5)

S(6,5) = C(6,2) = \cfrac{6!}{(6-2)! \times2!} = \cfrac{6\times5\times4\times3\times2}{4\times3\times2 \times2} =15

⑥ 根据公式 :

S(n, n) = 1

, 计算

S(6,6)

;

S(6,6) = 1

⑦ 将上面计算的

个斯特林数相加 , 得到的结果 :

S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6) = 1 + 31 + 90 + 65 + 15 + 1 =203

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-07-17，如有侵权请联系 cloudcommunity@tencent.com 删除

集合

统计

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

集合

统计

登录后参与评论

0 条评论

热度