離散數(shù)學(xué)N元集合關(guān)系個(gè)數(shù)計(jì)算

1、Author：ssjs Mail：看了離散數(shù)學(xué)中的關(guān)系整理了一點(diǎn)關(guān)于n元集合中各種關(guān)系的計(jì)算，現(xiàn)寫(xiě)下這個(gè)方便大家學(xué)習(xí)交流理解。對(duì)文章所致一切后果不負(fù)任何責(zé)任，請(qǐng)謹(jǐn)慎使用。如有錯(cuò)誤之處請(qǐng)指正。定義：1，對(duì)稱(chēng)：對(duì)于a,b2，反對(duì)稱(chēng)：如果3，自反：如果對(duì)每個(gè)元素4，反自反：如果對(duì)于每個(gè)5，傳遞：如果對(duì)6，非對(duì)稱(chēng)：如果【注】其中是含（a,a)這樣的有序?qū)Φ摹！局匾考螦的關(guān)系是從A到A的關(guān)系 （也就是說(shuō)集合A的關(guān)系是的子集）。如下結(jié)論：N元集合上的自反關(guān)系數(shù)為：N元集合上的對(duì)稱(chēng)關(guān)系數(shù)為：N元集合上的反對(duì)稱(chēng)關(guān)系數(shù)為：N元集合上的非對(duì)稱(chēng)關(guān)系數(shù)為：N元集合上的反自反關(guān)系數(shù)為：N元集合上的自反和對(duì)稱(chēng)關(guān)系數(shù)為

2、：N元集合上的不自反也不反自反關(guān)系數(shù)為：下面是上面結(jié)論的計(jì)算1，自反 也就是說(shuō)集合A有n平方個(gè)有序?qū)?，由自反定義可知，對(duì)所以n 個(gè)有序?qū)σ欢ㄔ谒箨P(guān)系中，否則的話(huà)此關(guān)系就不是自反的了，那么還有個(gè)有序?qū)Γ杂杉献蛹瘜?duì)應(yīng)二進(jìn)制串可得自反關(guān)系數(shù)為下圖有助于理解。（1,1) (2,2).(n,n) | (1,2) (1,3).(n-1,n) N個(gè)有序?qū)?個(gè)有序?qū)?，對(duì)稱(chēng) 也就是說(shuō)集合A有n平方個(gè)有序?qū)?，由?duì)稱(chēng)定義可知，對(duì)于。另外知道在n平方個(gè)有序?qū)χ杏衝 個(gè)有序?qū)?，相?yīng)的就有個(gè)有序?qū)Γ╔,Y)且X，定義可知后面的個(gè)有序?qū)χ荒艹蓪?duì)出現(xiàn)，所以有對(duì)。前面的那n對(duì)可以出現(xiàn)任意多對(duì)。圖片如下。（1,1) (

3、2,2).(n,n) (1,2) (1,3).(n-1,n) n個(gè)有序?qū)?(2,1) (3,1).(n,n-1) ()/2個(gè)有序?qū)?duì) 共有n+ ()/2 個(gè)元素 即 ()/2個(gè)所以得到對(duì)稱(chēng)關(guān)系數(shù)為：3，反自反 也就是說(shuō)集合A有n平方個(gè)有序?qū)?，由?duì)稱(chēng)定義可知，如果對(duì)于每個(gè)，構(gòu)成該關(guān)系的元素個(gè)數(shù)為個(gè)，所以得出結(jié)論，這個(gè)簡(jiǎn)單，不多說(shuō)。4，自反和對(duì)稱(chēng)即是求自反的又對(duì)稱(chēng)的，由1知要是自反的就只能在個(gè)有序?qū)χ猩勺蛹?，又由?duì)稱(chēng)定義可知，將個(gè)有序?qū)Ψ殖尚稳?a,b)與(b,a)的()/2個(gè)有序?qū)?duì)。所以有自反和對(duì)稱(chēng)關(guān)系數(shù)為：。如下圖（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n)

4、n個(gè)有序?qū)?(2,1) (3,1).(n,n-1) 要自反這n個(gè)必在所求關(guān)系中 ()/2個(gè)有序?qū)?duì)N個(gè)有序?qū)χ挥?種可能· 有種可能 = 5，不自反也不反自反不自反也不反自反 = 不自反不反自反 = = = = 6，非對(duì)稱(chēng)由定義：如果，很清楚形如(a,a)的有序?qū)Σ辉谒箨P(guān)系中。所以所求關(guān)系只能中剩下的個(gè)有序?qū)χ衼?lái)生成。如下圖。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n) n個(gè)有序?qū)?(2,1) (3,1).(n,n-1)這n個(gè)一定不在所求關(guān)系中 ( )/2個(gè)有序?qū)?duì) 由定義上圖的同色對(duì)中只能取一個(gè)或是一個(gè)也不取，就有三種狀態(tài)1）選上面的 2）選下面的

5、3）兩個(gè)都不選選取同色對(duì)？ 0 1 不選 選上還是選下？ 0 1 選上 選下由題知，不選，選上，選下是三種互斥結(jié)果。同集合二進(jìn)制求集合個(gè)數(shù)原理，可得集合子集個(gè)為：7，反對(duì)稱(chēng)由定義：如果 如下圖。（1,1) (2,2).(n,n) (1,2) (1,3).(n-1,n) n個(gè)有序?qū)?(2,1) (3,1).(n,n-1)這n個(gè)有序?qū)梢猿霈F(xiàn)任意多次 ( )/2個(gè)有序?qū)?duì) (由6可知）所以得結(jié)果 ：即【注】其它組合或是要求可由定義同理推出。不要怕麻煩，其實(shí)不那么難，也還有許多方法可以導(dǎo)出結(jié)果，如矩陣之類(lèi)的。強(qiáng)烈推薦看下Discrete Mathematics and Its Applications Seventh Editio