# 點算的奧秘：容斥原理基本公式

「容斥原理」(Principle of Inclusion and Exclusion)(亦作「排容原理」)是「點算組合學」中的一條重要 原理。但凡略為複雜、包含多種限制條件的點算問題，都要用到這條原理。現在首先從一個點算問題說起。

|S1 ∪ S2 ∪ S3| = (|S1| + |S2| + |S3|) − (|S1 ∩ S2| + |S1 ∩ S3| + |S2 ∩ S3|) + |S1 ∩ S2 ∩ S3|

 |S1 ∪ S2 ∪ ... Sn| = (|S1| + |S2| + ... |Sn|) − (|S1 ∩ S2| + |S1 ∩ S3| + ... |Sn − 1 ∩ Sn|) + (|S1 ∩ S2 ∩ S3| + |S1 ∩ S2 ∩ S4| + ... |Sn − 2 ∩ Sn − 1 ∩ Sn|) − (|S1 ∩ S2 ∩ S3 ∩ S4| + ... |Sn − 3 ∩ Sn − 2 ∩ Sn − 1 ∩ Sn|) ...... + (−1)n − 1 |S1 ∩ S2 ∩ ... Sn − 1 ∩ Sn|     (1)

|S1 ∪ S2 ∪ ... Sn| = Σ1 ≤ k ≤ n (−1)k − 1 Sn, k     (2)

C(k, 1) − C(k, 2) + C(k, 3) − C(k, 4) ... (−)k − 1 C(k, k) = Σ1 ≤ r ≤ k(−1)r − 1 C(k, r)

 Σ1 ≤ r ≤ k(−1)r − 1 C(k, r) = − Σ1 ≤ r ≤ k(−1)r C(k, r) = − [Σ0 ≤ r ≤ k(−1)r C(k, r) − (−1)0 C(k, 0)] = − Σ0 ≤ r ≤ kC(k, r) (−1)r + 1

|S1 ∪ S2 ∪ ... Sn| = Σ1 ≤ k ≤ n (−1)k − 1 C(n, k) nk     (3)

|S1' ∩ S2' ∩ ... Sn'| = |U| + Σ1 ≤ k ≤ n(−1)k Sn, k     (4)

|S1' ∩ S2' ∩ ... Sn'| = |U| + Σ1 ≤ k ≤ n(−1)k C(n, k) nk     (5)

Σ1 ≤ k ≤ 5(−1)k − 1 C(5, k) (26 − k) 10 = 5 × 2510 − 10 × 2410 + 10 × 2310 − 5 × 2210 + 2110

 |U| − C(3, 1) n1 + C(3, 2) n2 − C(3, 3) n3 = 6! − 3 × 5! × 2 + 3 × 4! × 22 − 1 × 3! × 23 = 720 − 720 + 288 − 48 = 240 □

<!-- 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?us1490898851" 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>