排容原理：正確計算重疊集合中元素個數的強大技巧

1. 引言

在數學和計算機科學中，我們經常會遇到需要計算滿足多個條件的元素數量的情況。然而，當存在多個條件時，滿足每個條件的元素集合通常會重疊（有交集）。簡單地將它們相加會導致元素被多次計算。

一種能準確消除這些重疊並得出正確元素數量的強大方法是 排容原理 （Inclusion-Exclusion Principle）。

在本文中，我們將全面詳細地解釋排容原理，從其基本概念到一般化的數學公式、數學證明以及具體的應用實例（例如歐拉函數和錯排問題）。此外，我們還將介紹程式設計實作範例，以從理論和實務兩個角度加深您的理解。

2. 集合與元素數量的基礎

在學習排容原理之前，讓我們先回顧一下基本的集合符號。

$A, B$ ：集合
$|A|$ ：集合 $A$ 的元素數量（勢）
$A \cup B$ ：集合 $A$ 和集合 $B$ 的聯集（屬於至少其中一個的元素）
$A \cap B$ ：集合 $A$ 和集合 $B$ 的交集（兩者都屬於的元素）

我們要尋找的是多個集合的聯集的元素數量，即 $|A \cup B \cup \dots|$ 。

3. 2個集合的排容原理

讓我們考慮最簡單的包含兩個集合 $A$ 和 $B$ 的情況。

3.1 公式

$$ |A \cup B| = |A| + |B| - |A \cap B| $$

3.2 直觀理解

  flowchart TD
    U["全集 U"]
    A["集合 A"]
    B["集合 B"]
    AandB["A ∩ B (交集)"]
    U -->|"包含"| A
    U -->|"包含"| B
    A -->|"重疊"| AandB
    B -->|"重疊"| AandB

4. 3個集合的排容原理

當有三個集合時，它變得稍微複雜一些。考慮集合 $A, B, C$ 。

4.1 公式

$$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| $$

4.2 直觀理解與證明

首先，將所有單獨的元素數量相加： $|A| + |B| + |C|$
這樣做之後，任意兩個集合的交集都被加了兩次，因此將它們減去： $- |A \cap B| - |B \cap C| - |C \cap A|$
最後，考慮所有三個集合的交集 $A \cap B \cap C$ 。它在步驟1中被加了3次，在步驟2中被減了3次，導致其目前的計算次數為 $0$ 。因此，我們在最後再把它加回來一次： $+ |A \cap B \cap C|$

4.3 具體範例：1到100中能被2、3或5整除的整數的數量

全集： $U = \{1, 2, \dots, 100\}$
2的倍數集合： $A$
3的倍數集合： $B$
5的倍數集合： $C$

讓我們計算每個集合的元素數量（其中 $\lfloor x \rfloor$ 表示向下取整函數）。

$|A| = \lfloor 100 / 2 \rfloor = 50$
$|B| = \lfloor 100 / 3 \rfloor = 33$
$|C| = \lfloor 100 / 5 \rfloor = 20$
$|A \cap B|$ (6的倍數) $= \lfloor 100 / 6 \rfloor = 16$
$|B \cap C|$ (15的倍數) $= \lfloor 100 / 15 \rfloor = 6$
$|C \cap A|$ (10的倍數) $= \lfloor 100 / 10 \rfloor = 10$
$|A \cap B \cap C|$ (30的倍數) $= \lfloor 100 / 30 \rfloor = 3$

$$ |A \cup B \cup C| = 50 + 33 + 20 - 16 - 6 - 10 + 3 = 74 $$

因此，能被2、3或5整除的數字有 74 個。

5. 一般 $n$ 個集合的排容原理

將其推廣到 $n$ 個集合 $A_1, A_2, \dots, A_n$ ，我們得到以下優美的公式。

5.1 公式

$$ \left| \bigcup_{i=1}^n A_i \right| = \sum_{k=1}^n (-1)^{k-1} \left( \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} \left| A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k} \right| \right) $$

用文字表達，該操作重複了「加上奇數個集合交集的元素數量，減去偶數個集合交集的元素數量」。

5.2 數學證明概要

我們將證明任何元素 $x \in \bigcup_{i=1}^n A_i$ 在右側的計算中被準確計算了1次。

假設某個元素 $x$ 恰好包含在 $m$ 個集合中（ $1 \le m \le n$ ）。元素 $x$ 在右側被計算的次數可以使用二項式係數表示如下：

$$ \text{計算次數} = \binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \dots + (-1)^{m-1} \binom{m}{m} $$

根據二項式定理，已知 $(1 - 1)^m = \binom{m}{0} - \binom{m}{1} + \binom{m}{2} - \dots + (-1)^m \binom{m}{m} = 0$ 。將其變形：

$$ \binom{m}{0} - \left( \binom{m}{1} - \binom{m}{2} + \dots + (-1)^{m-1} \binom{m}{m} \right) = 0 $$

由於 $\binom{m}{0} = 1$ ，括號內的表達式（即 $x$ 被計算的次數）的值正好是 $1$ 。這證明了每個元素都恰好被計算一次，沒有重複。

6. 應用範例1：歐拉函數

歐拉函數 $\varphi(N)$ 表示從 $1$ 到 $N$ 中與 $N$ 互質的整數的數量。這也可以使用排容原理來計算。

設 $N$ 的質因數為 $p_1, p_2, \dots, p_k$ 。設全集為 $U = \{1, 2, \dots, N\}$ ， $A_i$ 為「 $p_i$ 的倍數的集合」。我們要尋找的是不屬於任何 $A_i$ 的元素數量。

$$ \varphi(N) = N - \left| \bigcup_{i=1}^k A_i \right| $$

應用排容原理並進行化簡可得出這個著名的公式：

$$ \varphi(N) = N \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_k}\right) $$

7. 應用範例2：錯排問題

錯排是指將數字 $1$ 到 $n$ 進行排列，使得沒有任何第 $i$ 個數字在第 $i$ 個位置上。例如，這等同於在交換禮物時分配禮物的總方式，使得沒有人在其中收到自己的禮物。

設 $A_i$ 為「 $i$ 在第 $i$ 個位置的排列的集合」。全集的元素數量為 $n!$ 。我們要求的是 $n! - |A_1 \cup A_2 \cup \dots \cup A_n|$ 。

任何 $k$ 個集合交集的元素數量是 $(n-k)!$ ，而選擇這些 $k$ 個集合的方法有 $\binom{n}{k}$ 種。應用排容原理，錯排的數量 $D_n$ 如下：

$$ D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} $$

8. 透過程式設計計算和實作

排容原理在程式設計中非常有用。特別是當結合位元運算全排列搜尋（二進制枚舉）時，$n$ 個條件的排容原理可以被簡潔地實作。

以下是使用 Python 來尋找「在1到 $M$ 之間能被給定列表中的任何質數整除的整數數量」的程式碼。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def count_multiples(M: int, primes: list[int]) -> int:
    n = len(primes)
    total_count = 0
    
    # 使用從1到 2^n - 1 的位元遮罩遍歷所有子集
    for i in range(1, 1 << n):
        lcm = 1
        set_bits = 0
        
        # 計算所選質數的乘積（最小公倍數）
        for j in range(n):
            if (i >> j) & 1:
                lcm *= primes[j]
                set_bits += 1
                
        # 如果選擇了奇數個質數則相加，如果是偶數則相減（排容原理）
        if set_bits % 2 == 1:
            total_count += M // lcm
        else:
            total_count -= M // lcm
            
    return total_count

# 執行範例
M = 100
primes = [2, 3, 5]
# 預期輸出: 74
print(f"結果: {count_multiples(M, primes)}")