1. Quy tắc cộng tổng quát (Công thức bao hàm và loại trừ)
Bản chất toán học của quy tắc cộng (phát biểu cho công việc với nhiều phương án) là công thức tính số phần tử của hợp \(n\) tập hợp hữu hạn đôi một không giao nhau.
Cho \(n\) tập hợp \(A_1, A_2, \dots, A_n\) đôi một rời nhau (không giao nhau). Khi đó:
\[|A_1 \cup A_2 \cup \dots \cup A_n| = \sum_{i=1}^{n} |A_i|\]Trong nhiều bài toán tổ hợp, chúng ta phải tính số phần tử của hợp \(n\) tập hợp bất kỳ (không nhất thiết rời nhau). Khi đó ta có quy tắc cộng mở rộng, thường được gọi là công thức bao hàm và loại trừ (nguyên lý bù trừ).
Định lý: Cho \(n \ge 2\) tập hợp hữu hạn \(A_1, A_2, \dots, A_n\). Khi đó ta có:
\[ \begin{aligned} |A_1 \cup A_2 \cup \dots \cup A_n| = & \sum_{i=1}^{n} |A_i| - \sum_{1 \le i < k \le n} |A_i \cap A_k| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| \\ & + \dots + (-1)^{k+1} \sum_{1 \le i_1 < i_2 < \dots < i_k \le n} |A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_k}| \\ & + \dots + (-1)^{n+1} |A_1 \cap A_2 \cap \dots \cap A_n| \end{aligned} \](Định lý này có thể chứng minh tương đối dễ dàng bằng phương pháp quy nạp toán học).
2. Các ví dụ minh họa
Ví dụ 1: Trong tập \(S = \{1, 2, \dots, 280\}\), có bao nhiêu số không chia hết cho bất kỳ số nào trong các số \(2, 3, 5, 7\)?
Lời giải:
Ta đếm xem trong tập \(S\) có bao nhiêu số chia hết cho ít nhất một trong các số \(2, 3, 5, 7\).
Ký hiệu các tập con của \(S\) như sau:
- \(A_1 = \{k \in S : k \text{ chia hết cho } 2\}\)
- \(A_2 = \{k \in S : k \text{ chia hết cho } 3\}\)
- \(A_3 = \{k \in S : k \text{ chia hết cho } 5\}\)
- \(A_4 = \{k \in S : k \text{ chia hết cho } 7\}\)
Khi đó, \(A_1 \cup A_2 \cup A_3 \cup A_4\) là tập hợp các số thuộc \(S\) chia hết cho ít nhất một trong các số \(2, 3, 5, 7\).
Ta xác định số phần tử của các tập hợp và các giao của chúng:
\[ |A_1| = \left\lfloor \frac{280}{2} \right\rfloor = 140; \quad |A_2| = \left\lfloor \frac{280}{3} \right\rfloor = 93; \quad |A_3| = \left\lfloor \frac{280}{5} \right\rfloor = 56; \quad |A_4| = \left\lfloor \frac{280}{7} \right\rfloor = 40 \] \[ |A_1 \cap A_2| = \left\lfloor \frac{280}{6} \right\rfloor = 46; \quad |A_1 \cap A_3| = \left\lfloor \frac{280}{10} \right\rfloor = 28; \quad |A_1 \cap A_4| = \left\lfloor \frac{280}{14} \right\rfloor = 20 \] \[ |A_2 \cap A_3| = \left\lfloor \frac{280}{15} \right\rfloor = 18; \quad |A_2 \cap A_4| = \left\lfloor \frac{280}{21} \right\rfloor = 13; \quad |A_3 \cap A_4| = \left\lfloor \frac{280}{35} \right\rfloor = 8 \] \[ |A_1 \cap A_2 \cap A_3| = \left\lfloor \frac{280}{30} \right\rfloor = 9; \quad |A_1 \cap A_2 \cap A_4| = \left\lfloor \frac{280}{42} \right\rfloor = 6 \] \[ |A_1 \cap A_3 \cap A_4| = \left\lfloor \frac{280}{70} \right\rfloor = 4; \quad |A_2 \cap A_3 \cap A_4| = \left\lfloor \frac{280}{105} \right\rfloor = 2 \] \[ |A_1 \cap A_2 \cap A_3 \cap A_4| = \left\lfloor \frac{280}{210} \right\rfloor = 1 \]Áp dụng công thức bao hàm và loại trừ, ta tính được:
\[ |A_1 \cup A_2 \cup A_3 \cup A_4| = 216 \]Vậy trong tập \(S\) có tất cả số phần tử không chia hết cho \(2, 3, 5, 7\) là:
\[ 280 - 216 = 64 \text{ số} \]Ví dụ 2 (Công thức hàm Euler): Với mỗi số nguyên dương \(n > 1\), ký hiệu \(\phi(n)\) là số các số nguyên dương bé hơn \(n\) và nguyên tố cùng nhau với \(n\). Hàm \(\phi(n)\) được gọi là hàm Euler (phi hàm Euler), đóng một vai trò quan trọng trong số học.
Chứng minh rằng:
\[\phi(n) = n \prod_{i=1}^{m} \left(1 - \frac{1}{p_i}\right)\]trong đó \(p_1, p_2, \dots, p_m\) là tất cả các ước nguyên tố phân biệt của số nguyên dương \(n\).