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
          主站蜘蛛池模板: 永德县| 丰宁| 哈尔滨市| 三门县| 石阡县| 邮箱| 兖州市| 搜索| 夹江县| 宁晋县| 陆良县| 稷山县| 远安县| 隆子县| 铁岭县| 开江县| 武隆县| 武陟县| 遵义市| 手机| 丽水市| 博客| 台江县| 阳东县| 肥城市| 南阳市| 古交市| 宁强县| 安西县| 崇州市| 葫芦岛市| 浦城县| 睢宁县| 宁强县| 淮阳县| 满洲里市| 北流市| 阿荣旗| 辽宁省| 铜山县| 兰州市|