Combinatorics adalah cabang matematika yang menghitung berapa banyak cara suatu konfigurasi dapat terbentuk tanpa harus mendaftarkannya satu per satu. Sebelum mempelajari permutasi dan kombinasi di Chapter berikutnya, kita perlu memahami empat prinsip dasar yang menjadi fondasinya: product rule, sum rule, inclusion-exclusion, dan pigeonhole principle. Pada Chapter ini kita menurunkan tiap prinsip, melihat kapan masing-masing berlaku, dan mempraktikkannya dengan C++.

Product Rule (Aturan Perkalian) #

Aturan #

Bila sebuah tugas terdiri dari k tahapan berurutan, di mana tahap i dapat dilakukan dengan nᵢ cara (dan pilihan tiap tahap independen), maka total cara menyelesaikan tugas adalah:

text 
Total = n₁ · n₂ · ... · nₖ

Contoh klasik: PIN 4-digit, tiap digit memiliki 10 pilihan (0-9) → 10 · 10 · 10 · 10 = 10⁴ = 10.000 PIN.

Mekanisme: Mengapa Berlaku #

Setiap kombinasi pilihan (c₁, c₂, ..., cₖ) dengan cᵢ ∈ {1..nᵢ} adalah satu cara unik. Banyak kombinasi tersebut adalah kardinalitas cartesian product {1..n₁} × {1..n₂} × ... × {1..nₖ}, yaitu n₁ · n₂ · ... · nₖ.

Sum Rule (Aturan Penjumlahan) #

Aturan #

Bila sebuah tugas dapat dilakukan dengan salah satu dari k cara yang mutually exclusive (tidak tumpang tindih), dan cara i memiliki nᵢ varian, maka total cara adalah:

text 
Total = n₁ + n₂ + ... + nₖ

Contoh: dari kota A ke kota B bisa lewat 2 jalur pegunungan atau 3 jalur pesisir → 2 + 3 = 5 cara.

Mekanisme: Kapan Tumpang Tindih? #

Bila cara-cara tersebut bisa tumpang tindih, sum rule menghitung dobel bagian irisan. Inilah yang memotivasi inclusion-exclusion di bawah.

Inclusion-Exclusion Principle #

Aturan #

Untuk dua himpunan A, B:

text 
|A ∪ B| = |A| + |B| - |A ∩ B|

Untuk tiga himpunan A, B, C:

text 
|A ∪ B ∪ C| = |A| + |B| + |C|
             - |A ∩ B| - |A ∩ C| - |B ∩ C|
             + |A ∩ B ∩ C|

Pola umum untuk k himpunan: jumlah himpunan tunggal, kurangi himpunan beririsan 2, tambah himpunan beririsan 3, dan seterusnya, dengan tanda selang-seling + - + - ....

Mekanisme: Mengapa Pola Selang-Seling #

Setiap elemen x yang berada di tepat m himpunan (dari k himpunan) dihitung C(m,1) - C(m,2) + C(m,3) - ... ± C(m,m) kali dalam formula. Identitas kombinatorial menyatakan jumlah ini = 1 (bila m ≥ 1). Jadi setiap elemen x ∈ A ∪ B ∪ ... dihitung tepat sekali. Komponen ∩ mengoreksi over-counting dari penjumlahan tunggal.

Pigeonhole Principle #

Aturan #

Bila n item dimasukkan ke m lubang dengan n > m, maka setidaknya satu lubang berisi ⌈n/m⌉ ≥ 2 item.

Versi kuat: bila n > (k - 1) · m, maka setidaknya satu lubang berisi ≥ k item. Minimum n agar pasti ada k item di satu lubang adalah n = (k - 1) · m + 1.

Mekanisme: Kontradiksi #

Asumsikan setiap lubang berisi ≤ k - 1 item. Maka total ≤ m · (k - 1). Tetapi n = (k - 1) · m + 1 > m · (k - 1) — kontradiksi. Maka setidaknya satu lubang berisi ≥ k item.

Implementasi C++ #

Kode: Empat Prinsip #

cpp 
#include <iostream>
#include <vector>

// Product rule: milih satu item dari tiap kategori (urutan kategori bebas)
// Misal: 3 warna baju, 2 celana, 4 topi => 3*2*4 outfit
long long product_rule(const std::vector<int>& choices) {
    long long total = 1;
    for (int c : choices) total *= c;
    return total;
}

// Sum rule: milih satu item dari salah satu kategori (kategori mutually exclusive)
long long sum_rule(const std::vector<int>& choices) {
    long long total = 0;
    for (int c : choices) total += c;
    return total;
}

// Inclusion-Exclusion untuk 3 himpunan: |A ∪ B ∪ C|
long long ie3(long long A, long long B, long long C,
              long long AB, long long AC, long long BC, long long ABC) {
    return A + B + C - AB - AC - BC + ABC;
}

// Pigeonhole: minimum item agar >= k di satu lubang
// ceil(total / holes) >= k  iff  total >= (k-1)*holes + 1
long long pigeonhole_min(long long holes, long long k) {
    return (k - 1) * holes + 1;
}

int main() {
    // Product rule: sandi 4 digit, tiap digit 0-9 => 10^4
    std::cout << "Product rule (PIN 4 digit): " << product_rule({10, 10, 10, 10}) << '\n';

    // Outfit: 3 baju x 2 celana x 4 topi
    std::cout << "Product rule (outfit): " << product_rule({3, 2, 4}) << '\n';

    // Sum rule: angka 1..30 yang habis dibagi 2 atau 3
    // Kelipatan 2: {2,4,...,30} -> 15
    // Kelipatan 3: {3,6,...,30} -> 10
    // Kelipatan 6 (irisan): {6,12,...,30} -> 5
    // |A ∪ B| = 15 + 10 - 5 = 20
    long long A = 30 / 2;       // 15
    long long B = 30 / 3;       // 10
    long long AB = 30 / 6;      // 5
    std::cout << "Sum rule |A|+|B|-|A∩B|: " << A + B - AB
              << " (angka 1..30 habis dibagi 2 atau 3)\n";

    // Inclusion-Exclusion 3 himpunan
    // 100 siswa: 60 suka matematika, 50 fisika, 40 kimia
    // 25 suka mat+fis, 20 mat+kim, 15 fis+kim, 10 suka ketiganya
    // Berapa yang suka minimal satu?
    std::cout << "IE3 (siswa suka min 1 mapel): "
              << ie3(60, 50, 40, 25, 20, 15, 10) << '\n';

    // Pigeonhole: berapa minimum orang di ruangan agar 3 orang pasti sebulan sama?
    // Bulan = 12 lubang, k = 3
    std::cout << "Pigeonhole min orang (12 bulan, 3 sebulan): "
              << pigeonhole_min(12, 3) << '\n';

    return 0;
}

Output yang Dihasilkan:

text 
Product rule (PIN 4 digit): 10000
Product rule (outfit): 24
Sum rule |A|+|B|-|A∩B|: 20 (angka 1..30 habis dibagi 2 atau 3)
IE3 (siswa suka min 1 mapel): 100
Pigeonhole min orang (12 bulan, 3 sebulan): 25
  1. Baris for (int c : choices) total *= c;: product rule — kalikan pilihan tiap tahap.
  2. Baris for (int c : choices) total += c;: sum rule — tambahkan varian tiap kategori mutually exclusive.
  3. Baris return A + B + C - AB - AC - BC + ABC;: inclusion-exclusion 3 himpunan. Tunggal: +, irisan-2: -, irisan-3: +. Selang-seling.
  4. Baris return (k - 1) * holes + 1;: minimum n agar ⌈n/holes⌉ ≥ k. Untuk holes = 12, k = 3 → (3-1)·12 + 1 = 25. Dengan 25 orang, pasti ada 3 orang sebulan ulang tahun.
  5. Hasil Product rule (PIN) = 10000: 10⁴ = 10.000 PIN 4-digit. Sesuai.
  6. Hasil Outfit = 24: 3·2·4 = 24 kombinasi pakaian. Sesuai.
  7. Hasil Sum rule = 20: dari 30 bilangan, 15 kelipatan 2, 10 kelipatan 3, 5 kelipatan 6 (dihitung dua kali). 15 + 10 - 5 = 20 bilangan habis dibagi 2 atau 3. Sesuai.
  8. Hasil IE3 = 100: 60+50+40 - 25-20-15 + 10 = 100. Semua 100 siswa suka minimal satu mapel (data disusun konsisten).
  9. Hasil Pigeonhole = 25: 24 orang masih mungkin sebulan ulang tahun maksimal 2 (2·12=24). Orang ke-25 memaksa satu bulan berisi 3 orang.

Aplikasi #

  • Product rule: kompleksitas nested loop (mis. for i, for j, for k → n³ iterasi), jumlah state DP.
  • Sum rule: analisis percabangan (if A then ...; if B then ...), kompleksitas total operasi dari beberapa fase independen.
  • Inclusion-exclusion: menghitung banyak bilangan di [1, N] yang koprima dengan angka-angka tertentu, algoritma subset convolutions.
  • Pigeonhole: pembuktian eksistensi (mis. “ada 2 subsekuen dengan jumlah sama” bila array cukup panjang), hashing collision lower bound.

Ringkasan #

  • Product rule: n₁ · n₂ · ... · nₖ untuk tugas berurutan dengan pilihan independen.
  • Sum rule: n₁ + n₂ + ... + nₖ untuk pilihan mutually exclusive.
  • Inclusion-exclusion: koreksi over-counting irisan dengan pola + - + - ....
  • Pigeonhole: n > (k-1)·m → setidaknya satu lubang berisi ≥ k item.
  • Empat prinsip ini menjadi dasar perhitungan permutasi, kombinasi, dan banyak algoritma probabilistik.