posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          離散學(xué)習(xí)筆記 - 二元關(guān)系

          Posted on 2007-07-25 11:03 ZelluX 閱讀(379) 評論(0)  編輯  收藏 所屬分類: Mathematics
          1.閉包 Closure
          (1) 自反 reflexive
          對稱 symmetric
          傳遞 transitive
          (2) 其中,設(shè)R屬于A*A(A為非空集合),則r(R) = R與A上恒等關(guān)系的并,s(R) = R與R的逆的并,
          t(R) = R 并 R^2 并 R^3 并...并 R^l。
          (3) rs(R) = sr(R)
          rt(R) = tr(R)
          st(R) 屬于 ts(R)


          2. 等價關(guān)系和劃分
          (1) 設(shè)R屬于A*A,若R是自反的、對稱的和傳遞的,則稱R為A上的等價關(guān)系。
          (2) 令[x]R為x的關(guān)于R的等價類,在不引起混亂時可簡記為[x]。
          (3) 以關(guān)于R的全體不同的等價類為元素的集合稱為A關(guān)于R的商集,記作A/R。
          (4) 設(shè)A為非空集合,若存在A的一個子集族S滿足
          a. S中不包含空集元素
          b. 對于一切x,y屬于S,且x,y不相等,則x與y不相交的(disjoint)
          c. S中所有集合的并為A
          則稱S為A的一個劃分,S中元素稱為劃分塊。
          (5) 非空集合A上的等價關(guān)系與A的劃分是一一對應(yīng)的。
          (6) 第二類Stirling數(shù),表示將n個不同的球放入r個相同的盒子中的方案數(shù),可以由下列遞歸式計算:
          f(n, r) = r * f(n - 1, r) + f(n - 1, r - 1)
          很容易理解的一個遞歸式,其中初始狀態(tài)為
          f(n, 0) = 0, f(n, 1) = 1, f(n, 2) = 2^(n-1) - 1, f(n, n - 1) = C(n, 2), f(n, n) = 1
          (7) A上等價關(guān)系的數(shù)量可以通過Stiring數(shù)求出,以A={a,b,c,d}為例
          f(4,1) + f(4,2) + f(4,3) + f(4,4) = 15
          主站蜘蛛池模板: 滨州市| 灵山县| 葵青区| 屯昌县| 二连浩特市| 竹山县| 安乡县| 阳高县| 朝阳县| 阿图什市| 于都县| 筠连县| 清河县| 库尔勒市| 永康市| 长岛县| 建始县| 瑞昌市| 忻州市| 会昌县| 东港市| 微博| 马关县| 永新县| 凉城县| 牙克石市| 青海省| 克什克腾旗| 恭城| 鸡泽县| 兴国县| 台东市| 溆浦县| 湘西| 新泰市| 台南县| 乌兰察布市| 英山县| 开平市| 旬阳县| 白银市|