Nguyên lý Bao hàm-Loại trừ

Nguyên lý bao hàm-loại trừ đếm kích thước của một hợp các tập hợp bằng cách luân phiên cộng và trừ kích thước của các giao điểm của chúng.

Definition

Một đồng nhất thức đếm cho rằng lực lượng của một hợp các tập hợp hữu hạn bằng tổng luân phiên của lực lượng của tất cả các giao điểm của chúng, được lấy trên mọi tập hợp con không rỗng.

Scope

Chủ đề này trình bày công thức bao hàm-loại trừ và các ứng dụng của nó để đếm các đối tượng tránh một danh sách các thuộc tính bị cấm: hoán vị lệch, toàn ánh, hàm phi Euler, và số lượng các số nguyên tố cùng nhau với một số đã cho. Nó giới thiệu quan điểm sàng và tổng quát hóa hàm Mobius trên các tập hợp được sắp thứ tự một phần, đặt nguyên lý này vào một bối cảnh đại số rộng hơn.

Core questions

• Có bao nhiêu phần tử thỏa mãn ít nhất một trong số các điều kiện chồng chéo?
• Làm thế nào để đếm các đối tượng tránh tất cả các thuộc tính bị cấm?
• Làm thế nào để các phép đếm hoán vị lệch và toàn ánh suy ra từ nguyên lý này?
• Hàm Mobius trên một poset tổng quát hóa nguyên lý bao hàm-loại trừ như thế nào?

Key concepts

• Hợp của các tập hợp chồng chéo
• Phương pháp sàng
• Hoán vị lệch thông qua bao hàm-loại trừ
• Đếm toàn ánh
• Hàm phi Euler
• Hàm Mobius trên các poset

Key theories

Công thức bao hàm-loại trừ

Lực lượng của một hợp các tập hợp A_1 đến A_n bằng tổng kích thước của các tập hợp đơn trừ đi các giao điểm từng cặp cộng với các giao điểm ba, v.v., điều chỉnh một cách có hệ thống cho việc đếm quá mức các phần tử chung.

Nghịch đảo Mobius trên các poset

Tổng quát hóa theo lý thuyết poset của Stanley thay thế các dấu luân phiên của bao hàm-loại trừ bằng hàm Mobius của một tập hợp được sắp thứ tự một phần, thống nhất nguyên lý này với các công thức nghịch đảo trong lý thuyết số và lý thuyết lưới.

Clinical relevance

Ý tưởng sàng tổng quát hóa sang lý thuyết số (sàng Eratosthenes và các sàng phân tích), xác suất (các bất đẳng thức Bonferroni giới hạn xác suất hợp), và phân tích độ tin cậy của các hệ thống với các chế độ lỗi chồng chéo.

History

Về cơ bản được phát biểu bởi de Moivre và Sylvester, nguyên lý này được Rota đặt vào một lý thuyết tổng quát về các hàm Mobius trên các tập hợp được sắp thứ tự một phần vào năm 1964, một cột mốc quan trọng của tổ hợp học hiện đại.

Key figures

• Abraham de Moivre
• Gian-Carlo Rota

Seminal works

• stanley2011

Frequently asked questions

Tại sao các dấu lại luân phiên?

Các phần tử nằm trong một số tập hợp được cộng quá nhiều lần; việc trừ đi các giao điểm từng cặp sẽ sửa quá mức, do đó các giao điểm ba được cộng lại, tạo ra mô hình luân phiên mà mỗi phần tử được đếm chính xác một lần.

Mối liên hệ với hàm Mobius là gì?

Bao hàm-loại trừ là trường hợp đặc biệt của nghịch đảo Mobius trên lưới Boolean của các tập hợp con, trong đó hàm Mobius nhận các giá trị cộng hoặc trừ một.