Prinsip Inklusi-Eksklusi (PIE)

Prinsip Inklusi-Eksklusi (PIE) adalah teknik dasar dalam kombinatorika untuk menghitung banyaknya anggota dalam gabungan beberapa himpunan yang tidak saling lepas (non-disjoint).

Formulasi Himpunan

Teorema 4.1 (Prinsip Inklusi-Eksklusi)

Misalkan $A_1, A_2, \dots, A_n$ adalah himpunan-himpunan berhingga. Maka kardinalitas gabungannya adalah: $\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$

Aplikasi: Jumlah Derangement (Pengacakan Total)

Sebuah derangement adalah permutasi tanpa titik tetap. Banyaknya derangement dari $n$ objek dinotasikan $D_n$ : $D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \dots + \frac{(-1)^n}{n!} \right)$

Saat $n \to \infty$ , rasio $D_n / n! \to 1/e \approx 0.3678$ .

Lihat juga:

Keterbagian & Fungsi Euler untuk aplikasi PIE pada kalkulasi $\phi(n)$ .

Formulasi Himpunan

Aplikasi: Jumlah Derangement (Pengacakan Total)

Materi Terkait (Linked References) (1)

Fungsi Totient Euler & Teorema Euler-Fermat

Title