Prinsip Inklusi-Eksklusi: Menghitung Presisi Tanpa Duplikasi

Dalam kombinatorika, musuh terbesar kita adalah double counting (menghitung elemen yang sama berkali-kali). Ketika himpunan saling tumpang tindih, menjumlahkannya begitu saja akan menyebabkan kesalahan. Prinsip Inklusi-Eksklusi (PIE) hadir sebagai solusi sistematis: Masukkan semua (Inklusi), buang yang berlebih (Eksklusi), masukkan lagi koreksinya, dan seterusnya. Ini adalah seni menyeimbangkan perhitungan untuk mencapai presisi.

Materi Prasyarat:

➡️ Logika Pencacahan: Aturan Penjumlahan & Perkalian ➡️ Panduan Lengkap Permutasi ➡️ Konsep Mendalam Kombinasi

1. Rumus Dasar Teori Himpunan

Untuk dua himpunan $A$ dan $B$ , jika kita hanya menjumlahkan ukuran $A$ dan $B$ , maka irisan $A \cap B$ akan terhitung dua kali (double counting). Untuk mengoreksinya, kita harus menguranginya sekali agar pas.

$Rumus PIE 2 Himpunan$

Laboratorium Himpunan

Uji rumus tersebut dengan angkamu sendiri.

Set A

Set B

Irisan

Hasil: 30

2. Derangement (Pengacakan Total)

Apa itu Derangement?

Derangement (dilambangkan $D_n$ atau $!n$ ) adalah permutasi dari $n$ elemen di mana tidak ada satu pun elemen yang menempati posisi aslinya. Contoh klasik: 4 surat dimasukkan ke 4 amplop secara acak, dan semuanya salah alamat.

🔗 Hubungan: PIE dan Pengacakan

Mengapa kita menggunakan Inklusi-Eksklusi untuk Derangement? Karena "Kekacauan" (Derangement) secara matematis didefinisikan sebagai Irisan dari Komplemen.

Misalkan $P_i$ adalah sifat bahwa "Elemen ke- $i$ berada di posisi yang BENAR".

Kita mencari situasi di mana $P_1$ salah, DAN $P_2$ salah, dan seterusnya.
PIE adalah alat yang sempurna untuk menghitung gabungan dari kejadian "Setidaknya 1 Benar", "Setidaknya 2 Benar", dst.
Akhirnya, kita mengurangi gabungan tersebut dari Total Semesta untuk mendapatkan skenario "Tidak Ada yang Benar".

Asal-Usul Rumus (Penurunan)

Kita menerapkan Inklusi-Eksklusi pada Total Permutasi ( $n!$ ):

Total Semesta: $n!$
Eksklusi (Setidaknya 1 Benar): Pilih 1 tetap $C(n,1)$ , sisanya bebas $(n-1)!$ .
Hasil: $\frac{n!}{1!}$ .
Inklusi (Setidaknya 2 Benar): Mengoreksi pengurangan ganda. Pilih 2 tetap $C(n,2)$ , sisanya $(n-2)!$ .
Hasil: $\frac{n!}{2!}$ .

Rumus Umum Derangement:
$Rumus Umum Dn$

Penyelesaian Manual

Contoh: Tukar Kado Acak

Soal: Andi, Budi, Caca, dan Dedi (4 sekawan) menukar kado secara acak. Berapa banyak skenario di mana tidak ada yang mendapatkan kadonya sendiri?

Langkah 1: Identifikasi n
Jumlah orang $n=4$ . Kita mencari $D_4$ .

Langkah 2: Terapkan Rumus
$D_4 = 4! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} \right)$

Langkah 3: Hitung Suku-suku
Kita tahu bahwa $\frac{1}{0!} - \frac{1}{1!} = 1 - 1 = 0$ (saling menghilangkan).
Sisa suku: $24 \times (\frac{1}{2} - \frac{1}{6} + \frac{1}{24})$ .

Langkah 4: Perhitungan Akhir
$D_4 = 12 - 4 + 1 = 9$ .
Jadi, tepat ada 9 skenario tukar kado yang "Acak Sempurna".

Simulasi Visual: Tukar Kado (n=4)

Klik tombol untuk mengacak kado. Apakah akan terjadi Derangement sempurna?

Andy
🎁D
✅

Bob
🎁B
❌

Charlie
🎁A
✅

Dave
🎁C
✅

⚠️ FAILED. 1 people got their own gift.

Kalkulator Rumus Pengacakan (Derangement)

Hitung nilai $D_n$ untuk jumlah objek lainnya.

Jumlah Objek (n)

Hasil: -

3. Kombinasi dengan Batasan (Restricted Combinations)

Mengapa Rumus Biasa Tidak Cukup?

Rumus kombinasi standar (Stars and Bars) mengasumsikan kita memiliki persediaan tak terbatas. Namun, di dunia nyata, stok seringkali terbatas (misal: hanya ada 4 manik merah).

Di sinilah Inklusi-Eksklusi berperan: Kita hitung semua kemungkinan seolah-olah stok tak terbatas (Semesta), lalu kita kurangi kasus-kasus pelanggaran (mengambil melebihi stok).

🔗 Rahasia Rumus: Trik "Paksa Ambil"

Bagaimana cara menghitung "Kasus Pelanggaran"?

Definisi Pelanggaran: Jika stok maksimal adalah $m$ , maka pelanggaran terjadi saat kita mengambil $m+1$ barang atau lebih.
Trik Menghitung: Untuk menjamin kita menghitung kasus pelanggaran, kita "Paksa Ambil" $m+1$ barang tersebut di awal dan memasukkannya ke keranjang.
Sisa Perhitungan: Setelah $m+1$ barang diambil, kita tinggal menghitung sisa kebutuhan yang belum terpenuhi menggunakan rumus Stars & Bars biasa. Hasil inilah yang menjadi jumlah "Himpunan Pelanggaran".

Inilah alasan matematis mengapa kita mengurangi total kebutuhan $n$ dengan $m+1$ dalam perhitungan.

$Total = Semesta - \sum N(Pelanggaran_1) + \sum N(Pelanggaran_2) - \dots$

Dimana Semesta dihitung menggunakan Stars & Bars: $C(n+r-1, r)$ .

Penyelesaian Manual

Contoh: Gelang Rifa

Soal: Rifa ingin membuat gelang dengan 10 manik. Dia punya 3 warna (Merah, Hijau, Biru), tapi stoknya terbatas masing-masing hanya 4 manik.

Langkah 1: Semesta (Tanpa Batas)
Anggap stok tak terbatas. Ambil 10 dari 3 jenis.
$C(10+3-1, 10) = C(12, 10) = 66$ cara.

Langkah 2: Definisi Pelanggaran
Stok maksimal = 4. Maka batas pelanggaran = $4+1=5$ .
Kita melanggar aturan jika mengambil $\ge 5$ manik sewarna.

Langkah 3: Pelanggaran 1 Warna (S1)
Trik "Paksa Ambil": Ambil 5 manik Merah dulu.
Sisa kebutuhan: $10 - 5 = 5$ manik.
Hitung variasi untuk sisa 5 manik dari 3 warna: $C(5+3-1, 5) = C(7, 5) = 21$ .
Karena ada 3 warna (M, H, B), totalnya: $3 \times 21 = 63$ .

Langkah 4: Pelanggaran 2 Warna (S2)
Trik "Paksa Ambil": Ambil 5 Merah DAN 5 Hijau.
Sisa kebutuhan: $10 - 5 - 5 = 0$ manik.
Hitung variasi sisa: $C(0+3-1, 0) = 1$ .
Kombinasi pasangan warna ada 3 (MH, MB, HB): $3 \times 1 = 3$ .

Langkah 5: Total Akhir
$Total = 66 - 63 + 3 = 6$ variasi valid.

Kalkulator Kombinasi Batasan

Simulasikan masalah gelang 3 warna (Maks 4 per warna).

Butuh Manik

Stok/Warna

Hasil: 6

4. Kuis Pemahaman

Q 1/10Score: 0

What is the first step in calculating restricted combinations?

Keywords: Prinsip Inklusi Eksklusi, Derangement, Kombinasi Terbatas, Stars and Bars, Matematika Diskrit.

Prinsip Inklusi-Eksklusi: Seni Menghitung Tanpa Pengulangan

Prinsip Inklusi-Eksklusi: Seni Menghitung Tanpa Pengulangan

Prinsip Inklusi-Eksklusi: Menghitung Presisi Tanpa Duplikasi