Prinsip Inklusi-Eksklusi, Derangement & Fungsi Onto

Jika himpunan-himpunan memiliki irisan, maka menjumlahkan ukuran masing-masing himpunan akan menghitung elemen irisan secara berlebih. Prinsip Inklusi-Eksklusi (PIE) memberikan formula umum untuk menghitung gabungan $n$ himpunan.

1. Formulasi PIE untuk $n$ Himpunan

Dua dan Tiga Himpunan

Untuk dua himpunan $A$ dan $B$ :

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$

Untuk tiga himpunan $A, B,$ dan $C$ :

$∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - (∣ A \cap B ∣ + ∣ A \cap C ∣ + ∣ B \cap C ∣) + ∣ A \cap B \cap C ∣$

Bentuk Umum PIE

Teorema (Prinsip Inklusi-Eksklusi (PIE))

Secara umum, untuk himpunan-himpunan berhingga $A_{1}, A_{2}, \dots, A_{n}$ , banyaknya elemen pada gabungan mereka adalah:

$∣ ⋃_{i = 1}^{n} A_{i} ∣ = \sum_{i = 1}^{n} ∣ A_{i} ∣ - \sum_{1 \leq i < j \leq n} ∣ A_{i} \cap A_{j} ∣ + \dots + (- 1)^{n - 1} ∣ A_{1} \cap \dots \cap A_{n} ∣$

Dalam notasi ringkas:

$∣ ⋃_{i = 1}^{n} A_{i} ∣ = \sum_{\emptyset \neq = S \subseteq {1, \dots, n}} (- 1)^{∣ S ∣ - 1} ⋂_{i \in S} A_{i}$

2. Aplikasi PIE: Derangement dan Fungsi Onto

Derangement (Pengacakan Total)

Sebuah derangement adalah permutasi dari elemen-elemen suatu himpunan sedemikian sehingga tidak ada satu pun elemen yang menempati posisi aslinya (no fixed points). Banyaknya derangement dari $n$ elemen dilambangkan dengan $D_{n}$ .

Teorema (Formula Derangement)

Banyaknya derangement dari $n$ objek berbeda adalah:

$D_{n} = n! (1 - \frac{1}{1 !} + \frac{1}{2 !} - \frac{1}{3 !} + \dots + (- 1)^{n} \frac{1}{n !})$

Jumlah Fungsi Onto (Surjektif)

Teorema (Banyaknya Fungsi Surjektif (Onto))

Banyaknya fungsi onto dari himpunan berukuran $n$ ke himpunan berukuran $m$ ( $n \geq m$ ) adalah:

$\sum_{k = 0}^{m} (- 1)^{k} (k m) (m - k)^{n}$

Contoh Soal & Pembahasan

Contoh (Kelipatan 3, 5, atau 7)

Berapa banyak bilangan bulat antara 1 sampai 100 (inklusif) yang habis dibagi 3, 5, atau 7?

Contoh (Masalah Penutupan Topi (D5))

Terdapat 5 orang pria yang masing-masing menitipkan topinya di sebuah penitipan. Saat pulang, petugas memberikan topi secara acak. Berapa banyak cara agar tidak ada satu pun pria yang menerima topi miliknya sendiri?

Latihan Soal

✏️ Latihan Soal 1 (Bilangan Relatif Prima (Fungsi Totient Euler))

Berapa banyak bilangan bulat dari 1 sampai 1000 yang tidak habis dibagi 2, 3, maupun 5?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Total $N = 1000$ .

$∣ A_{2} ∣ = 500$ , $∣ A_{3} ∣ = 333$ , $∣ A_{5} ∣ = 200$ .
$∣ A_{2} \cap A_{3} ∣ = 166$ , $∣ A_{2} \cap A_{5} ∣ = 100$ , $∣ A_{3} \cap A_{5} ∣ = 66$ .
$∣ A_{2} \cap A_{3} \cap A_{5} ∣ = ⌊ 1000/30 ⌋ = 33$ . Banyaknya yang habis dibagi 2, 3, atau 5: $(500 + 333 + 200) - (166 + 100 + 66) + 33 = 1033 - 332 + 33 = 734$ . Maka yang tidak habis dibagi ketiganya adalah $1000 - 734 = 266$ . $■$

✏️ Latihan Soal 2 (Mendistribusikan Bola ke Kotak Tanpa Kosong)

Berapa banyak cara menempatkan 6 bola berbeda ke dalam 3 kotak berbeda sedemikian sehingga tidak ada kotak yang kosong?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Ini setara dengan mencari jumlah fungsi onto dari himpunan berukuran $n = 6$ ke $m = 3$ :

$Total = (0 3) 3^{6} - (1 3) 2^{6} + (2 3) 1^{6} = 729 - 3 (64) + 3 (1) = 729 - 192 + 3 = 540 cara. ■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Pigeonhole & Paritas
Sub-Topik Selanjutnya: Relasi Rekurensi →

Prinsip Inklusi-Eksklusi, Derangement & Fungsi Onto

1. Formulasi PIE untuk $n$ Himpunan

Dua dan Tiga Himpunan

Bentuk Umum PIE

2. Aplikasi PIE: Derangement dan Fungsi Onto

Derangement (Pengacakan Total)

Jumlah Fungsi Onto (Surjektif)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

🏆 Soal ONMIPA Terkait (2 Soal)

Materi Terkait (Linked References) (5)

Prinsip Eksistensi: Pigeonhole & Paritas

Relasi Rekurensi & Persamaan Karakteristik

Fungsi Totient Euler & Teorema Euler-Fermat

Naskah Soal & Pembahasan KNMIPA PT 2021 — Seleksi Wilayah

Naskah Soal & Pembahasan ONMIPA PT 2025 — Seleksi Wilayah

Diskusi & Tanya Jawab

Title

1. Formulasi PIE untuk n Himpunan

Dua dan Tiga Himpunan

Bentuk Umum PIE

2. Aplikasi PIE: Derangement dan Fungsi Onto

Derangement (Pengacakan Total)

Jumlah Fungsi Onto (Surjektif)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

🏆 Soal ONMIPA Terkait (2 Soal)

Materi Terkait (Linked References) (5)

Prinsip Eksistensi: Pigeonhole & Paritas

Relasi Rekurensi & Persamaan Karakteristik

Fungsi Totient Euler & Teorema Euler-Fermat

Naskah Soal & Pembahasan KNMIPA PT 2021 — Seleksi Wilayah

Naskah Soal & Pembahasan ONMIPA PT 2025 — Seleksi Wilayah

Diskusi & Tanya Jawab

1. Formulasi PIE untuk $n$ Himpunan