Posted on 2007-07-25 11:03
ZelluX 閱讀(379)
評論(0) 編輯 收藏 所屬分類:
Mathematics
1.閉包 Closure
(1) 自反 reflexive
對稱 symmetric
傳遞 transitive
(2) 其中，設R屬于A*A（A為非空集合），則r(R) = R與A上恒等關系的并，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. 等價關系和劃分
(1) 設R屬于A*A，若R是自反的、對稱的和傳遞的，則稱R為A上的等價關系。
(2) 令[x]R為x的關于R的等價類，在不引起混亂時可簡記為[x]。
(3) 以關于R的全體不同的等價類為元素的集合稱為A關于R的商集，記作A/R。
(4) 設A為非空集合，若存在A的一個子集族S滿足
a. S中不包含空集元素
b. 對于一切x,y屬于S，且x,y不相等，則x與y不相交的(disjoint)
c. S中所有集合的并為A
則稱S為A的一個劃分，S中元素稱為劃分塊。
(5) 非空集合A上的等價關系與A的劃分是一一對應的。
(6) 第二類Stirling數，表示將n個不同的球放入r個相同的盒子中的方案數，可以由下列遞歸式計算：
f(n, r) = r * f(n - 1, r) + f(n - 1, r - 1)
很容易理解的一個遞歸式，其中初始狀態為
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上等價關系的數量可以通過Stiring數求出，以A={a,b,c,d}為例
f(4,1) + f(4,2) + f(4,3) + f(4,4) = 15