Matdis — Bab 5
Kombinatorika
Seni menghitung tanpa menghitung satu per satu — permutasi, kombinasi, dan prinsip-prinsip pencacahan yang menentukan ukuran key space dan entropi kriptografi.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 5. — Rosen, Discrete Mathematics, 8th ed., Ch. 6.
Mengapa Kombinatorika?
Kombinatorika menjawab satu pertanyaan sederhana yang muncul di mana-mana: ada berapa banyak kemungkinan? Berapa susunan jadwal yang mungkin, berapa cara memilih panitia, berapa plat nomor yang bisa dibuat.
Kuncinya adalah membedakan dua hal: apakah urutan diperhitungkan (permutasi) atau tidak (kombinasi), dan apakah pengulangan diperbolehkan. Salah membedakan keduanya adalah sumber kesalahan paling umum — dan paling sering diuji.
Analogi: Menu Restoran vs. Kata Sandi
Memilih kata sandi 8 karakter dari 94 karakter ASCII = masalah kombinatorika: 94⁸ ≈ 6×10¹⁵ kemungkinan. Permutasi = urutan penting (kata sandi). Kombinasi = urutan tidak penting (memilih tim). Prinsip perkalian = pilihan menu: 5 pembuka × 10 makanan utama × 4 dessert = 200 kombinasi makan malam.
1. Prinsip Penjumlahan & Perkalian
Prinsip Penjumlahan
Jika tugas dapat diselesaikan dengan cara pertama (n₁) ATAU cara kedua (n₂) — dan keduanya disjoint:
Total = n₁ + n₂
Contoh: 6 buku fiksi ATAU 4 buku sains = 10 pilihan buku.
Prinsip Perkalian
Jika tugas pertama punya n₁ cara DAN tugas kedua punya n₂ cara (independen):
Total = n₁ × n₂
Contoh: 3 kemeja × 4 celana = 12 kombinasi pakaian.
Aplikasi: Ukuran Key Space
| Key Type | Formula | Key Space |
|---|---|---|
| 4-digit PIN | 10⁴ | 10,000 |
| 8-char password (a-z) | 26⁸ | 208,827,064,576 |
| 8-char password (printable ASCII) | 94⁸ | ≈ 6.1 × 10¹⁵ |
| AES-128 key | 2¹²⁸ | ≈ 3.4 × 10³⁸ |
| AES-256 key | 2²⁵⁶ | ≈ 1.2 × 10⁷⁷ |
2. Prinsip Sarang Merpati (Pigeonhole Principle)
Prinsip Sarang Merpati
Jika n + 1 merpati dimasukkan ke n lubang sarang, maka setidaknya satu lubang berisi 2 merpati atau lebih.
Jika k objek ke n wadah dan k > n, maka ≥1 wadah berisi ≥ ⌈k/n⌉ objek.
Aplikasi Kriptografi: Karena hash function punya output n bit tetapi input tak terbatas, ada collision. Birthday paradox: dengan ~√(2ⁿ) = 2^(n/2) percobaan, ekspektasi collision terjadi. Ini mengapa SHA-256 memberikan keamanan 128-bit collision resistance.
Demo Pigeonhole Interaktif
11 merpati, 10 lubang → setidaknya satu lubang berisi ≥ 2 merpati!
3. Permutasi
Definisi & Formula Permutasi
Permutasi P(n,r)
Memilih dan mengurutkan r objek dari n objek berbeda:
P(n,r) = n! / (n−r)!
Atau: n × (n-1) × ... × (n-r+1)
Permutasi Berulang
Memilih r dari n objek dengan pengulangan:
nʳ
Contoh: 5-digit PIN = 10⁵ = 100,000 kemungkinan.
4. Kombinasi
Definisi & Formula Kombinasi
Kombinasi C(n,r)
Memilih r objek dari n objek, tanpa memperhatikan urutan:
C(n,r) = n! / (r!(n−r)!)
C(n,r) = C(n,n-r) — simetris
Kombinasi Berulang (Multiset)
Memilih r dari n objek dengan pengulangan, urutan tidak penting:
C(n+r-1, r)
"Stars and bars": r stars dan (n-1) bars.
Kalkulator Permutasi & Kombinasi Interaktif
P(10, 3) = 10! / 7!
720
Permutasi (urutan penting)
C(10, 3) = 10! / (3! × 7!)
120
Kombinasi (urutan tidak penting)
P(n,r) = C(n,r) × r! (karena permutasi = kombinasi × semua urutan r objek)
5. Teorema Binomial & Segitiga Pascal
Teorema Binomial
(x + y)ⁿ = Σₖ₌₀ⁿ C(n,k) xᵏ yⁿ⁻ᵏ
Korolari Penting
Σₖ₌₀ⁿ C(n,k) = 2ⁿ (x=y=1)
Σₖ₌₀ⁿ (-1)ᵏ C(n,k) = 0 (x=1,y=-1)
Contoh: (a+b)³
= C(3,0)a³ + C(3,1)a²b + C(3,2)ab² + C(3,3)b³
= a³ + 3a²b + 3ab² + b³
Segitiga Pascal Interaktif (highlight baris ke-5)
Baris 5: koefisien (x+y)^5 = { 1, 5, 10, 10, 5, 1 }
Total = 2^5 = 32
Visualisasi SMIL: Pengisian Segitiga Pascal
6. Koefisien Multinomial
Teorema Multinomial
(x₁+x₂+...+xₘ)ⁿ = Σ [n!/(k₁!k₂!...kₘ!)] x₁ᵏ¹x₂ᵏ²...xₘᵏᵐ
Koefisien multinomial C(n; k₁,k₂,...,kₘ) = n! / (k₁!k₂!...kₘ!) menghitung jumlah cara membagi n objek menjadi grup berukuran k₁, k₂, ..., kₘ.
Contoh: Berapa cara mengatur kata "MISSISSIPPI" (11 huruf, M:1, I:4, S:4, P:2)?
= 11! / (1! × 4! × 4! × 2!) = 39916800 / (1×24×24×2) = 34,650
7. Birthday Paradox & Aplikasi Kriptografi
Demo: Probabilitas Dua Orang Berbagi Ulang Tahun
Dengan 23 orang, probabilitas ada dua orang berbagi ulang tahun:
50.73%
Lebih dari 50%! Hanya perlu 23 orang untuk probabilitas >50%.
Birthday Attack pada Hash Functions
Birthday Bound: Untuk fungsi hash dengan n-bit output (2ⁿ nilai), birthday attack menemukan collision setelah ≈ 2^(n/2) percobaan. SHA-256 memberikan 128-bit collision security (2¹²⁸ percobaan — aman).
Generalisasi: Jika domain berukuran N, ekspektasi collision setelah √N sampel. Ini mengapa MD5 (128-bit, √2¹²⁸ = 2⁶⁴) tidak aman — 2⁶⁴ komputasi feasible dengan GPU modern.
Permutasi dalam Pengacakan: Algoritma Fisher-Yates mengacak n elemen dengan setiap dari n! permutasi berpeluang sama. Dipakai untuk mengocok daftar putar, membagi data latih/uji, dan mengacak urutan soal ujian.
8. Contoh Soal & Pembahasan
Soal 1: Prinsip Perkalian
Berapa banyak kata sandi 6 karakter yang terdiri dari 2 huruf besar (A-Z) dan 4 digit (0-9)?
Soal 2: Permutasi
Dari 10 tim, berapa cara memilih juara 1, 2, 3?
Soal 3: Kombinasi
Dari 8 kryptographers, berapa cara memilih tim 3 orang?
Soal 4: Teorema Binomial
Tentukan koefisien x⁴ dalam (2x - 3)⁷.
Soal 5: Pigeonhole
Dalam sekelompok 367 orang, buktikan setidaknya dua orang lahir di tanggal dan bulan yang sama.
Soal 6: Birthday Attack
Hash function menghasilkan output 64-bit. Berapa ekspektasi percobaan untuk menemukan collision (birthday attack)?
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Referensi: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 5 — Kombinatorika.
MUDAH Soal Dasar Counting
K-M1: Aturan Perkalian
Sebuah password terdiri dari 2 huruf kapital (A-Z) diikuti 3 angka (0-9). Berapa banyak password yang bisa dibentuk?
K-M2: Permutasi
Berapa cara menyusun 4 buku berbeda pada sebuah rak? Berapa jika hanya 3 dari 6 buku yang dipilih dan disusun?
K-M3: Kombinasi
Dari 10 siswa, akan dipilih 4 untuk mewakili sekolah. Berapa cara memilihnya? Bedakan dari permutasi!
K-M4: Binomial Theorem
Ekspansi (x+y)⁴. Gunakan koefisien binomial C(4,k). Berapa koefisien x²y²?
SEDANG Counting Lanjut
K-S1: Pigeonhole Principle
Buktikan: dari setiap 13 orang, minimal 2 lahir di bulan yang sama. Berapa minimal orang agar pasti ada 3 lahir di bulan yang sama?
K-S2: Distribusi Bola ke Kotak (Stars & Bars)
Berapa cara mendistribusikan 8 bola identik ke 3 kotak berbeda (kotak boleh kosong)? Bagaimana jika tiap kotak minimal 1 bola?
K-S3: Permutasi dengan Pengulangan
Berapa banyak kata berbeda yang bisa dibentuk dari huruf-huruf kata "MISSISSIPPI"?
K-S4: Derangement
5 amplop dan 5 surat diacak. Berapa P(tidak ada surat yang masuk ke amplop yang benar)? Hitung D(5).
SULIT Counting Kompleks
K-H1: Catalan Numbers
Berapa banyak cara menyisipkan tanda kurung valid dalam ekspresi produk n+1 bilangan? Hitung C₄ (Catalan ke-4). Apa hubungannya dengan BST?
K-H2: Inclusion-Exclusion + Kombinatorika
Berapa banyak bilangan bulat dari 1 hingga 100 yang TIDAK habis dibagi 2, 3, atau 5?
K-H3: Recurrence Relation
Barisan Fibonacci: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1. Hitung F(10) menggunakan DP. Buktikan C(n,0)+C(n,1)+...+C(n,n) = 2^n menggunakan binomial theorem.
TERINTEGRASI Kombinatorika + Peluang & Himpunan
K-T1: Kombinasi + Peluang — Kartu & Cryptography
Dari 52 kartu, 5 diambil secara acak. Hitung P(dapat tepat 2 As). Lalu: jika ini model "key generation" dari 52 kandidat, apa implikasi jika ruang kunci hanya C(52,5)?
K-T2: Kombinatorika + Himpunan — Partisi & Secret Sharing
Sebuah secret S dibagi ke n=5 pihak dengan skema threshold (t=3,n=5). Berapa subset minimal yang bisa rekonstruksi secret? Berapa yang tidak bisa? Gunakan kombinatorika himpunan.
K-T3: Kombinatorika + Kompleksitas — Brute Force vs Kombinatorial
AES-256 menggunakan kunci 256-bit. Berapa C(256,128) sebagai perbandingan? Mengapa key space 2²⁵⁶ jauh lebih besar dari C(256,128)?