Permutasi dan Kombinasi

Banyak soal DSA — menghitung banyak cara menyusun tim, koefisien binomial pada ekspansi (a+b)ⁿ, hingga koefisien pada algoritma DP — memerlukan perhitungan permutasi P(n, k) dan kombinasi C(n, k). Tanpa teknik modular, factorial n! meluap dengan cepat (21! sudah lebih dari 2⁶³). Pada Chapter ini kita menurunkan rumus keduanya, lalu membangun struktur precompute factorial + inverse factorial untuk menjawab banyak query C(n, k) mod p dalam O(1) per query, dengan p = 10⁹+7.

Definisi Permutasi dan Kombinasi #

Aturan #

Diberikan himpunan n elemen berbeda:

Permutasi P(n, k) = n! / (n - k)!: banyak cara memilih k elemen berurutan dari n elemen. Urutan penting.
Kombinasi C(n, k) = n! / (k! · (n - k)!): banyak cara memilih k elemen tanpa urutan dari n elemen. Urutan tidak penting.
Hubungan: P(n, k) = C(n, k) · k!. Kombinasi adalah permutasi yang membagi k! (banyak urutan internal yang setara).

Contoh: dari {1, 2, 3, 4} pilih 2:

Permutasi: (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3) → 12 = 4!/2!.
Kombinasi: {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4} → 6 = 4!/(2!·2!).

Mekanisme: Mengapa Rumus Berlaku #

P(n, k): tahap 1 ada n pilihan, tahap 2 ada n-1 (satu sudah dipakai), …, tahap k ada n-k+1. Total via product rule: n · (n-1) · ... · (n-k+1) = n! / (n-k)!.

C(n, k): dari P(n, k) cara terurut, bagi k! karena k! urutan internal yang berbeda menghasilkan kombinasi yang sama. Maka C(n, k) = P(n, k) / k! = n! / (k! · (n-k)!).

Identitas Penting #

Aturan #

Beberapa identitas yang sering muncul:

text
Pascal identity : C(n, k) = C(n-1, k-1) + C(n-1, k)
Symmetry        : C(n, k) = C(n, n-k)
Summation       : Σ_{k=0}^{n} C(n, k) = 2^n           (baris ke-n segitiga Pascal)
Vandermonde     : Σ_{i} C(m, i) · C(n, k-i) = C(m+n, k)

Mekanisme: Pembuktian Pascal Secara Kombinatorial #

C(n, k) menghitung banyak subset ukuran k dari n elemen. Pisahkan menjadi: (a) subset yang memuat elemen ke-n, dan (b) subset yang tidak memuat elemen ke-n. Jenis (a): pilih k-1 dari n-1 sisanya → C(n-1, k-1). Jenis (b): pilih k dari n-1 sisanya → C(n-1, k). Total C(n-1, k-1) + C(n-1, k).

Komputasi Modular: Precompute Faktorial #

Aturan #

Untuk menghitung C(n, k) mod p (dengan p prima seperti 10⁹+7):

Precompute fact[i] = i! mod p untuk i = 0..N (sekali, O(N)).
Precompute invfact[i] = (i!)⁻¹ mod p untuk i = 0..N (O(N) + O(log p) via Fermat’s little theorem).
Query C(n, k) = fact[n] · invfact[k] · invfact[n-k] mod p — O(1) per query.

Mekanisme: Fermat untuk Invers Faktorial #

Untuk prima p, Fermat’s little theorem menyatakan a^(p-1) ≡ 1 (mod p) bila gcd(a, p) = 1. Maka a^(-1) ≡ a^(p-2) (mod p). Invers dari N! adalah (N!)^(p-2) mod p, dihitung dengan fast exponentiation dalam O(log p).

Setelah invfact[N] diketahui, kita turun mundur: invfact[i-1] = invfact[i] · i mod p (karena invfact[i] · i! = 1, maka invfact[i-1] = invfact[i] · i). Ini menghemat O(N log p) menjadi O(N + log p).

Kode: Precompute + Query #

cpp
#include <iostream>
#include <vector>

const long long MOD = 1'000'000'007;

// Fast exponentiation modulo (lihat chapter Fast Exponentiation)
long long power(long long b, long long k, long long m) {
    long long r = 1; b %= m;
    while (k > 0) {
        if (k & 1) r = (r * b) % m;
        b = (b * b) % m;
        k >>= 1;
    }
    return r;
}

struct Factorials {
    int n;
    std::vector<long long> fact, invfact;
    explicit Factorials(int n_) : n(n_), fact(n_ + 1), invfact(n_ + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % MOD;
        invfact[n] = power(fact[n], MOD - 2, MOD);
        for (int i = n - 1; i >= 0; --i)
            invfact[i] = invfact[i + 1] * (i + 1) % MOD;
    }
    // C(n, k) = n! / (k! (n-k)!)
    long long C(int n_, int k) const {
        if (k < 0 || k > n_) return 0;
        return fact[n_] * invfact[k] % MOD * invfact[n_ - k] % MOD;
    }
    // P(n, k) = n! / (n-k)!
    long long P(int n_, int k) const {
        if (k < 0 || k > n_) return 0;
        return fact[n_] * invfact[n_ - k] % MOD;
    }
};

// Pascal identity: C(n, k) = C(n-1, k-1) + C(n-1, k)
long long pascal_C(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    return pascal_C(n - 1, k - 1) + pascal_C(n - 1, k);
}

int main() {
    Factorials F(20);

    // P(n, k) dan C(n, k) untuk n=5..7
    std::cout << "Permutasi P(n, k):\n";
    for (int n = 5; n <= 7; ++n) {
        for (int k = 0; k <= n; ++k)
            std::cout << "P(" << n << "," << k << ")=" << F.P(n, k) << ' ';
        std::cout << '\n';
    }

    std::cout << "\nKombinasi C(n, k) (segitiga Pascal):\n";
    for (int n = 0; n <= 6; ++n) {
        for (int k = 0; k <= n; ++k)
            std::cout << F.C(n, k) << ' ';
        std::cout << '\n';
    }

    // Verifikasi Pascal identity dengan rekursi (naif, tanpa mod)
    std::cout << "\nVerifikasi Pascal C(6,3) rekursif: " << pascal_C(6, 3) << '\n';

    // Mod test: C(10^6, 5) mod 1e9+7
    Factorials Fbig(1'000'000);
    std::cout << "C(10^6, 5) mod 1e9+7 = " << Fbig.C(1'000'000, 5) << '\n';
    // Manual check: 10^6 * (10^6-1) * ... * (10^6-4) / 120
    long long num = 1;
    for (int i = 0; i < 5; ++i) num = num * (1'000'000 - i) % MOD;
    long long denom_inv = power(120, MOD - 2, MOD);
    std::cout << "Manual check            = " << num * denom_inv % MOD << '\n';

    return 0;
}

Output yang Dihasilkan:

text
Permutasi P(n, k):
P(5,0)=1 P(5,1)=5 P(5,2)=20 P(5,3)=60 P(5,4)=120 P(5,5)=120 
P(6,0)=1 P(6,1)=6 P(6,2)=30 P(6,3)=120 P(6,4)=360 P(6,5)=720 P(6,6)=720 
P(7,0)=1 P(7,1)=7 P(7,2)=42 P(7,3)=210 P(7,4)=840 P(7,5)=2520 P(7,6)=5040 P(7,7)=5040 

Kombinasi C(n, k) (segitiga Pascal):
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 

Verifikasi Pascal C(6,3) rekursif: 20
C(10^6, 5) mod 1e9+7 = 287783408
Manual check            = 287783408

Baris fact[0] = 1;: base case — 0! = 1 menurut konvensi (produk kosong).
Baris fact[i] = fact[i - 1] * i % MOD;: precompute iteratif i!. Modulo setiap iterasi.
Baris invfact[n] = power(fact[n], MOD - 2, MOD);: invers n! via Fermat: a^(p-2) ≡ a^(-1) (mod p). Lihat Chapter Modular Inverse .
Baris invfact[i] = invfact[i + 1] * (i + 1) % MOD;: turun mundur. (i+1)!⁻¹ · (i+1) = i!⁻¹. Lebih cepat dari menghitung i!⁻¹ satu per satu via power.
Baris return fact[n_] * invfact[k] % MOD * invfact[n_ - k] % MOD;: C(n, k) = n! / (k! · (n-k)!) = n! · (k!)⁻¹ · ((n-k)!)⁻¹. Dua kali mod untuk mencegah overflow intermediate (long long aman hingga (10⁹)² ≈ 10¹⁸).
Hasil P(5, 3) = 60: 5!/2! = 120/2 = 60. Sesuai.
Hasil P(7, 5) = 2520: 7!/2! = 5040/2 = 2520. Sesuai.
Segitiga Pascal: baris ke-n berisi C(n, 0), C(n, 1), ..., C(n, n). Baris ke-6: 1 6 15 20 15 6 1 — simetris sesuai identitas C(n, k) = C(n, n-k).
Hasil pascal_C(6, 3) rekursif = 20: identitas Pascal C(6,3) = C(5,2) + C(5,3) = 10 + 10 = 20. Cocok dengan F.C(6, 3) = 20.
Hasil C(10^6, 5) mod 1e9+7 = 287783408: perhitungan modular precompute O(N + log p) lalu O(1) query. Verifikasi dengan perhitungan manual num · 120⁻¹ mod p menghasilkan nilai yang sama.

Variasi dan Ekstensi #

Multinomial Coefficient #

text

n! / (k₁! · k₂! · ... · kₘ!)   dengan k₁ + k₂ + ... + kₘ = n

Banyaknya cara membagi n objek menjadi m kelompok berukuran k₁, k₂, ..., kₘ. Contoh: berapa anagram “MISSISSIPPI” = 11! / (1! · 4! · 4! · 2!).

Kombinasi dengan Pengulangan #

text

C(n + k - 1, k)

Banyaknya cara memilih k item dari n kategori dengan pengulangan (boleh pilih kategori yang sama lebih dari sekali). Equivalen dengan menempatkan k bola identik ke n kotak berbeda (stars and bars).

Kombinasi Large `n`, Small `k` #

Untuk n sangat besar (mis. 10¹⁸) tetapi k kecil (≤ 10⁶), gunakan formula langsung:

text

C(n, k) = ∏_{i=0}^{k-1} (n - i) / (i + 1)

Hitung secara iteratif modulo p, dengan setiap pembagian dilakukan via power(denom, p-2, p). Precompute faktorial tidak dimungkinkan bila n > 10⁷.

Aplikasi #

Binomial coefficient: koefisien pada ekspansi (a+b)ⁿ, jumlah subset ukuran k.
DP: banyak soal DP berbasis kombinasi (mis. paths pada grid, koefisien Catalan C(2n, n)/(n+1)).
Probabilitas: peluang menarik k sukses dari n trial (distribusi binomial).
Kompetisi: menghitung banyak cara berlatar kombinasi mod p, sering dengan precompute O(N) di awal.

Ringkasan #

P(n, k) = n! / (n - k)! — permutasi, urutan penting.
C(n, k) = n! / (k! · (n - k)!) — kombinasi, urutan tidak penting.
Identitas Pascal: C(n, k) = C(n-1, k-1) + C(n-1, k) — basis segitiga Pascal.
Komputasi modular: precompute fact[] dan invfact[] dalam O(N + log p), lalu query C(n, k) mod p dalam O(1).
Invers faktorial via Fermat: invfact[N] = fact[N]^(p-2) mod p, lalu turun mundur invfact[i-1] = invfact[i] · i.

Definisi Permutasi dan Kombinasi #

Aturan #

Mekanisme: Mengapa Rumus Berlaku #

Identitas Penting #

Aturan #

Mekanisme: Pembuktian Pascal Secara Kombinatorial #

Komputasi Modular: Precompute Faktorial #

Aturan #

Mekanisme: Fermat untuk Invers Faktorial #

Kode: Precompute + Query #

Variasi dan Ekstensi #

Multinomial Coefficient #

Kombinasi dengan Pengulangan #

Kombinasi Large n, Small k #

Aplikasi #

Ringkasan #

Kombinasi Large `n`, Small `k` #