# 點算的奧秘：集合劃分問題

「集合劃分」問題就是以下的問題，設某個集合A共有r個元素，現要把A劃分為n個子集A1 ... An，共有多少種不同劃分法？按照是否容許在A1 ... An中存在空集，「 集合劃分」問題可分為「不容許空集的集合劃分」問題和「容許空集的集合劃分」問題這兩大類。舉例說，設A 共有3個元素(不妨稱它們命名為1、2和3)，現要把它們劃分為2個非空子集，那麼應共有以下3種劃分法(請注意 以下用「集合的集合」Set of Sets，或稱「集合族」Family of Sets來代表集合的「劃分」)：

{{1,2},{3}}; {{1,3},{2}}; {{1},{2,3}}

{Φ,{1,2,3}}; {{1,2},{3}}; {{1,3},{2}}; {{1},{2,3}}

{1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2}

Φ-{1,2,3}; {1,2,3}-Φ; {1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2}

N(n, 0) = Σ0 ≤ k ≤ n(−1)k C(n, k) nk     (1)

D1(r, n) = Σ0 ≤ k ≤ n(−1)k C(n, k) (n − k)r    (2)

 D1(3, 2) = Σ0 ≤ k ≤ 2(−1)k C(2, k) (2 − k)3 = 1 × 8 − 2 × 1 + 1 × 0 = 6

D1(r, n) = n! × P1(r, n)    (3)

P1(r, n) = [Σ0 ≤ k ≤ n(−1)k C(n, k) (n − k)r] / n!    (4)

D0(r, n) = nr

D0(r, n) = n! × P0(r, n)?

 P0(r, n) = Σ1 ≤ i ≤ nP1(r, i) = Σ1 ≤ i ≤ n Σ0 ≤ k ≤ i (−1)k C(i, k) (i − k)r / i!    (5)

 P1(3, 1) = [Σ0 ≤ k ≤ n(−1)k C(1, k) (1 − k)3] / 1! = 1 × 1 − 1 × 0 = 1

 D1(4, 3) = Σ0 ≤ k ≤ 3(−1)k C(3, k) (3 − k)4 = 1 × 81 − 3 × 16 + 3 × 1 − 1 × 0 = 36 □

 D(r1, ... rn) = M(r1, ... rn) = r! / [(r1)! × ... (rn)!]    (6)

D(r1, ... rn) = k1! × k2! × ... kr! × P(k1, ... kr)    (7)

D(1 ... 1, 2 ... 2, ... r ... r) = r! / [(1!)k1 (2!)k2 ... (r!)kr]    (8)

P(k1, ... kr) = r! / [(k1)! (1!)k1 (k2)! (2!)k2 ... (kr)! (r!)kr]     (9)

 D(2, 2) = 4! / (2! × 2!) = 6 □

<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898686" alt="setstats" border="0" width="1" height="1"></noscript><script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>