No45.数一数这里有多少关系

2019-12-29 本文已影响0人赫尔特

文章目录
$\color{#0FACAA}{1.等价关系的数目}$
$\color{#0FACAA}{2.关系数目}$
$\color{#0FACAA}{3.自反关系的数目}$
$\color{#0FACAA}{4.对称关系的数目}$
$\color{#0FACAA}{5.反对称(antisymmetric)关系的数目}$
$\color{#0FACAA}{6.非对称(Asymmetric)关系的数目}$
$\color{#0FACAA}{Reference}$

1.等价关系的数目

定义1：等价关系（equivalence relation）即设R是某个集合A上的一个二元关系。若R满足以下条件：

自反性： $\forall x\in A,~~xRx$
对称性： $\forall x,y\in A,~~xRy~~\implies ~~yRx$
传递性： $\forall x,y,z\in A,~~~(xRy~~\wedge ~~yRz)~~\implies ~~xRz$
则称 ${\displaystyle R}是一个定义在{\displaystyle A}上的等价关系。$

定义2：等价类， $假设在一个集合X上定义一个等价关系（用\sim来表示），$
$则X中的某个元素a的等价类就是在$
$X中等价于a的所有元素所形成的子集:$

$[a] = \{ x \in X | x \sim a \}。$

问：含有3个元素的集合可以构成多少个等价关系
答：3个元素可以构成1,2,3个等价类，即

若构成1个等价类：这个等价类就是{a,b,c}

若构成2个等价类，则可以是({a,b},{c}) , ({a,c},{b}) , ({b,c},{a})这3种（注释：每个小

括号里面有2个等价类，小括号里面的大括号就是等价类中含有的元素）

若构成3个等价类，则可以是({a},{b},{c})这一种

共5种

然后每种等价类对应一个等价关系，比如

({a},{b},{c})对应的等价关系是{(a,a),(b,b),(c,c)}

({a,b},{c})对应的等价关系是{(a,a),(b,b),(a,b),(b,a),(c,c)}

问：含有4个元素的集合可以构成多少个等价关系
答：4个元素可以构成1,2,3,4个等价类，即

若构成1个等价类，有1种
若构成2个等价类，有 $C_4^3+{{C_4^2 }\over{2!}}=7$ 种
若构成3个等价类，有 $C_4^2=6$ 种
若构成4个等价类，有1种
共15种。

2.关系数目

问：含有n个元素的集合可以构成多少种关系
答：设A是含有n个元素的集合，则笛卡尔积A x A含有 $n^2$ 个元素，A x A含有的子集数目为 $2^{n^2}$ ，所以可以构成 $2^{n^2}$ 种关系。

3.自反关系的数目

问：含有n个元素的集合可以构成多少种自反关系
答：假设元素分别为1,2,3,...,n，根据自反关系的定义，一定要有(1,1),(2,2),(3,3),...,(n,n)这n个对，还剩下 $n^2-n$ 个对，它们可以任意分配，所以一共可以构成 $2^{n^2-n}$ 种自反关系。

4.对称关系的数目

问：含有n个元素的集合可以构成多少种对称关系
答：假设元素分别为1,2,3,...,n，根据对称关系的定义，一定要有（a,b）,(b,a)

一定要同时出现，有 $2^{{n^2-n}\over 2}$ 种情况，还剩下(1,1),(2,2),(3,3),...,(n,n)这n个对,它们可以任意分配，所以一共有 $2^{{n^2-n}\over 2}\times 2^n=2^{{n^2+n}\over 2}$

5.反对称(antisymmetric)关系的数目

问：含有n个元素的集合可以构成多少种反对称关系
答：假设元素分别为1,2,3,...,n，根据反对称关系的定义，除非a=b否则，(a,b),

(b,a)不能同时出现，我们有 ${{n^2-n}\over 2}$ 这样的对（a,b）,（b,a），对于每一

个对，不选，选择对里的第一个，和第二个共计3种情况，根据乘法定理，一共有

$3^{{n^2-n}\over 2}$ 种情况，还剩下(1,1),(2,2),(3,3),...,(n,n)这n个对,它们可以任意

分配，所以一共有 $2^n3^{{n^2-n}\over 2}$ 种反对称关系

6.非对称(Asymmetric)关系的数目

问：含有n个元素的集合可以构成多少种非对称关系
答：假设元素分别为1,2,3,...,n，根据非对称关系的定义，(a,b),

(b,a)不能同时出现（包括a=b），我们有 ${{n^2-n}\over 2}$ 这样的对（a,b）,（b,a），对于每一

个对，不选，选择对里的第一个，和第二个共计3种情况，根据乘法定理，一共有

$3^{{n^2-n}\over 2}$ 种情况，所以一共有 $3^{{n^2-n}\over 2}$ 种非对称关系

Reference

1.等价类
2.等价关系
3.离散数学N元集合关系个数计算

到底啦，觉得有帮助的话点个赞吧，阿里嘎多(୨୧•͈ᴗ•͈)◞︎ᶫᵒᵛᵉ ♡

上一篇下一篇

猜你喜欢

热点阅读