Định lýĐã chứng minh

Nguyên lý bao hàm loại trừ

Phát biểu

Với các tập hữu hạn $A_1,\dots,A_n$ , $\Big|\bigcup_{i=1}^n A_i\Big| = \sum_i |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1}|A_1 \cap \cdots \cap A_n|$ .

Vì sao đúng?

Chỉ đơn giản cộng kích thước các tập chồng lấp sẽ đếm trùng những phần tử nằm trong nhiều hơn một tập. Trừ đi các phần giao đôi một sẽ sửa việc đếm trùng đó, nhưng khi đó phần giao ba lại bị trừ quá nhiều lần, nên phải cộng trở lại, và cứ thế, đổi dấu luân phiên cho tới khi mỗi phần tử của hợp được đếm đúng một lần.

Phác thảo chứng minh

Cố định một phần tử $x$ trong hợp, thuộc đúng $m \ge 1$ tập. Chứng minh đóng góp ròng của nó vào tổng đan dấu là $\sum_{j=1}^{m} (-1)^{j-1}\binom{m}{j}$ , và theo định lý nhị thức áp dụng cho $(1-1)^m = 0$ thì tổng này bằng $1$ . Vì mỗi phần tử của hợp đóng góp đúng $1$ và các phần tử ngoài hợp đóng góp $0$ , tổng đan dấu bằng $|\bigcup A_i|$ .

Chủ đề chứa định lý này

Nguyên lý bao hàm và loại trừ

Định lý liên quan

Nguyên lý Dirichlet (nguyên lý chuồng bồ câu)Định lý nhị thức (nhị thức Newton)

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

J. H. van Lint, R. M. Wilson (2001). A Course in Combinatorics