Aplikasi PIE: Derangement dan Fungsi Onto

Dua aplikasi utama dari Prinsip Inklusi-Eksklusi dalam kombinatorika adalah penghitungan permutasi tanpa titik tetap (derangement) dan pencacahan fungsi surjektif (onto).

1. 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 !})$

Bukti: Misalkan $S$ adalah himpunan semua permutasi ( $∣ S ∣ = n!$ ). Misalkan $A_{i}$ adalah himpunan permutasi di mana elemen ke- $i$ berada di posisi aslinya (fixed point). Kita ingin mencari $D_{n} = ∣ S ∣ - ∣ A_{1} \cup \dots \cup A_{n} ∣$ . Diperoleh $∣ A_{i} ∣ = (n - 1)!$ , $∣ A_{i} \cap A_{j} ∣ = (n - 2)!$ , dan seterusnya. Menggunakan PIE menghasilkan formula $D_{n}$ di atas. $■$

2. 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 (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?

Contoh (Bola ke Dalam Kotak Tanpa Kosong)

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

Latihan Soal

✏️ Latihan Soal 1 (Nilai D6)

Hitunglah nilai $D_{6}$ . Periksa apakah benar bahwa $D_{n}$ adalah bilangan bulat terdekat dari $n! / e$ .

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: $D_{6} = 6! (\frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120} + \frac{1}{720}) = 360 - 120 + 30 - 6 + 1 = 265$ . Nilai $6! / e = 720/2.71828 \approx 264.87$ , bilangan bulat terdekatnya adalah $265$ . $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Formulasi PIE untuk n Himpunan
Sub-Topik Selanjutnya: Barisan Fibonacci dan Aplikasinya →

Aplikasi PIE: Derangement dan Fungsi Onto

1. Derangement (Pengacakan Total)

2. Jumlah Fungsi Onto (Surjektif)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Barisan Fibonacci dan Aplikasinya

Formulasi PIE untuk n Himpunan

Diskusi & Tanya Jawab

Title