容斥原理公式用於計算多個集合的併集的元素個數,同時考慮到交集中的重複計數問題。該原理可以推廣到任意數量的集合,但最常見的是二集合和三集合的情況。
二集合容斥原理公式:
\( |A \cup B| = |A| + |B| - |A \cap B| \)
三集合容斥原理公式:
標準型:\( |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| \)
非標準型:\( |A \cup B \cup C| = |A| + |B| + |C| - |\text{只} A \cap B \cap C| - 2 \times |A \cap B \cap C| \)
一般情況下的容斥原理公式:
對於 \( m \) 個集合 \( A_1, A_2, \ldots, A_m \),容斥原理的公式可以表示為:
\( n(A_1 \cup A_2 \cup \ldots \cup A_m) = \sum_{i=1}^{m} n(A_i) - \sum_{1 \leq i < j \leq m} n(A_i \cap A_j) + \sum_{1 \leq i < j < k \leq m} n(A_i \cap A_j \cap A_k) - \ldots + (-1)^{m-1} n(A_1 \cap A_2 \cap \ldots \cap A_m) \)
這些公式幫助我們在計算多個集合的併集的大小時,正確地處理集合之間的交集,避免重複計數。