Prinsip Inklusi-Eksklusi

Prinsip inklusi-eksklusi menghitung ukuran gabungan himpunan dengan secara bergantian menambah dan mengurangi ukuran irisan-irisannya.

Definition

Identitas penghitungan yang menyatakan bahwa kardinalitas gabungan himpunan-himpunan hingga sama dengan jumlah bergantian dari kardinalitas semua irisan-irisannya, yang diambil dari setiap subkoleksi tak kosong.

Scope

Topik ini menyajikan formula inklusi-eksklusi dan aplikasinya untuk menghitung objek yang menghindari daftar properti terlarang: derangement, surjeksi, fungsi totient Euler, dan jumlah bilangan bulat koprima terhadap bilangan tertentu. Ini memperkenalkan sudut pandang saringan (sieve viewpoint) dan generalisasi fungsi Mobius pada himpunan terurut parsial, yang menempatkan prinsip ini dalam pengaturan aljabar yang lebih luas.

Core questions

• Berapa banyak elemen yang memenuhi setidaknya satu dari beberapa kondisi yang tumpang tindih?
• Bagaimana seseorang dapat menghitung objek yang menghindari semua himpunan properti terlarang?
• Bagaimana derangement dan perhitungan surjeksi berasal dari prinsip ini?
• Bagaimana fungsi Mobius pada poset menggeneralisasi inklusi-eksklusi?

Key concepts

• Gabungan himpunan yang tumpang tindih
• Metode saringan
• Derangement melalui inklusi-eksklusi
• Menghitung surjeksi
• Fungsi totient Euler
• Fungsi Mobius pada poset

Key theories

Formula inklusi-eksklusi

Kardinalitas gabungan himpunan A_1 hingga A_n sama dengan jumlah ukuran himpunan tunggal dikurangi irisan berpasangan ditambah irisan rangkap tiga, dan seterusnya, mengoreksi secara sistematis penghitungan berlebihan elemen yang dibagi.

Inversi Mobius pada poset

Generalisasi teori poset Stanley menggantikan tanda bergantian inklusi-eksklusi dengan fungsi Mobius dari himpunan terurut parsial, menyatukan prinsip tersebut dengan formula inversi teori bilangan dan teori kisi.

Clinical relevance

Ide saringan digeneralisasi ke teori bilangan (saringan Eratosthenes dan saringan analitik), probabilitas (ketaksamaan Bonferroni yang membatasi probabilitas gabungan), dan analisis keandalan sistem dengan mode kegagalan yang tumpang tindih.

History

Pada dasarnya dinyatakan oleh de Moivre dan Sylvester, prinsip ini ditempatkan dalam teori umum fungsi Mobius pada himpunan terurut parsial oleh Rota pada tahun 1964, sebuah tonggak penting dalam kombinatorika modern.

Key figures

• Abraham de Moivre
• Gian-Carlo Rota

Seminal works

• stanley2011

Frequently asked questions

Mengapa tanda-tandanya bergantian?

Elemen-elemen yang terletak di beberapa himpunan ditambahkan terlalu banyak; mengurangi irisan berpasangan mengoreksi secara berlebihan, sehingga irisan rangkap tiga ditambahkan kembali, menghasilkan pola bergantian yang menghasilkan setiap elemen tepat satu kali.

Apa hubungan dengan fungsi Mobius?

Inklusi-eksklusi adalah kasus khusus inversi Mobius pada kisi Boolean dari himpunan bagian, di mana fungsi Mobius mengambil nilai plus atau minus satu.