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

文章目录
$\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元集合关系个数计算

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

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,222评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,455评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,720评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,568评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,696评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,879评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,028评论 3赞 409
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,773评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,220评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,550评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,697评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,360评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,002评论 3赞 315
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,782评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,010评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,433评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,587评论 2赞 350