17. Permutasi dan kombinasi

Bab sebelumnya mencacah dengan dua aturan dasar. Bab ini memberi nama dan rumus untuk dua pola yang paling sering muncul: memilih dengan memperhatikan urutan (permutasi) dan tanpa memperhatikan urutan (kombinasi).

Satu pertanyaan memisahkan keduanya:

Apakah menukar urutan menghasilkan hasil yang berbeda?

• Menyusun tiga orang sebagai ketua, sekretaris, bendahara → ya, urutan penting → permutasi.
• Memilih tiga orang untuk masuk tim → tidak, urutan tidak penting → kombinasi.

Faktorial

n! adalah hasil kali 1 sampai n, dan 0! = 1.

Kenapa 0! = 1: ada tepat satu cara menyusun barisan kosong, yaitu tidak menyusun apa-apa. Kesepakatan ini bukan sekadar kesepakatan — tanpa itu, rumus kombinasi di bawah akan pecah pada kasus tepi r = 0 dan r = n.

Faktorial membesar sangat cepat: 21! sudah tidak muat di long long. Karena itu soal yang memakai faktorial hampir selalu meminta jawabannya modulo 10⁹ + 7.

Permutasi

Menyusun seluruh n benda ada n! cara: pilihan pertama n, berikutnya n − 1, dan seterusnya — aturan perkalian menurun dari Bab 16.

Menyusun r dari n benda (urutan penting):

P(n, r) = n! / (n − r)! = n × (n−1) × … × (n−r+1)

Contoh: dari 10 siswa dipilih ketua, sekretaris, dan bendahara: P(10, 3) = 10 × 9 × 8 = 720.

Dari mana rumus itu: pilihan pertama punya n kemungkinan, pilihan kedua n − 1 karena satu sudah terpakai, dan seterusnya sampai r pilihan. Bentuk n! / (n − r)! hanyalah cara ringkas menuliskan perkalian menurun itu — pembagian dengan (n − r)! membuang ekor perkalian yang tidak dipakai.

Contoh kecil yang bisa didaftar seluruhnya: dari huruf A B C dipilih 2 dengan urutan penting. P(3, 2) = 3 × 2 = 6, dan memang ada enam:

AB  AC  BA  BC  CA  CB

Permutasi dengan unsur yang sama. Kalau ada benda yang tidak bisa dibedakan, bagi dengan faktorial banyaknya masing-masing:

n! / (n₁! × n₂! × … )

Contoh: susunan huruf pada kata OSNOSN (6 huruf: O×2, S×2, N×2): 6! / (2! × 2! × 2!) = 720 / 8 = 90.

Kombinasi

Memilih r dari n benda tanpa memperhatikan urutan:

C(n, r) = n! / (r! × (n − r)!)

Hubungannya dengan permutasi: setiap kelompok berisi r benda bisa disusun dalam r! urutan, jadi C(n, r) = P(n, r) / r!.

Contoh: dari 10 siswa dipilih 3 untuk tim: C(10, 3) = 720 / 6 = 120.

Kembali ke contoh A B C tadi. Kalau urutan tidak dipedulikan, keenam susunan tadi menciut menjadi tiga kelompok:

Setiap kombinasi diwakili 2! = 2 susunan, jadi C(3, 2) = 6 / 2 = 3. Angka pembagi r! pada rumus kombinasi persis jumlah susunan yang dianggap sama itu.

Cara memeriksa cepat apakah sebuah soal permutasi atau kombinasi: tukar posisi dua benda yang sudah dipilih. Kalau hasilnya dianggap berbeda, itu permutasi; kalau dianggap sama, kombinasi.

Sifat yang sering dipakai:

Baris ketiga adalah yang paling berguna untuk program: ia mengubah kombinasi menjadi dynamic programming. Bacanya: benda ke-n ikut dipilih (sisa r−1 dari n−1) atau tidak ikut (r dari n−1).

Perhatikan bentuknya — "ambil atau tidak ambil, lalu jumlahkan kedua kemungkinan" — persis bentuk transisi knapsack di Bab 13. Bedanya hanya knapsack mengambil yang terbesar, sedangkan cacahan menjumlahkan. Bila dua jalur pada sebuah soal tidak pernah menghasilkan hal yang sama, menjumlahkan keduanya adalah cara mencacahnya.

Segitiga Pascal

n=0             1
n=1           1   1
n=2         1   2   1
n=3       1   3   3   1
n=4     1   4   6   4   1
n=5   1   5  10  10   5   1

Setiap angka adalah jumlah dua angka di atasnya. Dalam kode:

long long C[1005][1005];

for (int n = 0; n <= batas; n++) {
    C[n][0] = 1;
    for (int r = 1; r <= n; r++)
        C[n][r] = (C[n-1][r-1] + C[n-1][r]) % MOD;
}

Cara ini O(n²) dan tidak memerlukan pembagian sama sekali — cocok untuk n sampai beberapa ribu. Karena tidak ada pembagian, ia juga bekerja untuk modulus apa pun, bahkan yang bukan bilangan prima.

Kombinasi modulo untuk n besar

Untuk n sampai sejuta, tabel Pascal terlalu besar (10¹² sel). Yang dipakai adalah rumus faktorial, dengan pembagian diganti perkalian invers modulo (Bab 14):

long long fakt[1000005];

void siapkan(int n) {
    fakt[0] = 1;
    for (int i = 1; i <= n; i++) fakt[i] = fakt[i-1] * i % MOD;
}

long long kombinasi(int n, int r) {
    if (r < 0 || r > n) return 0;
    long long atas = fakt[n];
    long long bawah = fakt[r] * fakt[n-r] % MOD;
    return atas * pangkat_mod(bawah, MOD - 2, MOD) % MOD;
}

Inilah pemakaian teorema Fermat kecil yang paling sering di OSN: tanpa invers modulo, rumus kombinasi tidak bisa dihitung.

Pola soal

Jalur di papan. Dari pojok kiri atas ke pojok kanan bawah papan b × k, hanya boleh melangkah ke kanan atau ke bawah. Setiap jalur terdiri dari b−1 langkah bawah dan k−1 langkah kanan; jawabannya tinggal memilih posisi langkah bawah di antara seluruh langkah:

C((b−1) + (k−1), b−1)

Contoh kecil untuk papan 2 × 3: setiap jalur terdiri dari 1 langkah bawah dan 2 langkah kanan, jadi jawabannya C(3, 1) = 3. Ketiganya bisa didaftar sebagai urutan langkah:

kanan kanan bawah
kanan bawah kanan
bawah kanan kanan

Inti gagasannya: sebuah jalur sepenuhnya ditentukan oleh di langkah keberapa saja kamu bergerak ke bawah. Jadi mencacah jalur sama dengan memilih posisi langkah bawah di antara seluruh langkah — dan itu persis kombinasi.

Memilih tim. "Berapa cara memilih 5 dari 12 pemain" → C(12, 5).

Membagi menjadi dua kelompok. "Berapa cara membagi 10 orang menjadi dua kelompok berisi 4 dan 6" → C(10, 4).

Himpunan bagian. "Berapa himpunan bagian dari n benda" → 2ⁿ, yang juga merupakan jumlah satu baris segitiga Pascal.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Bedakan tiga pertanyaan yang bunyinya mirip. Hampir semua kesalahan pada soal kombinatorika berasal dari salah memilih di antara ketiganya:

Kata kuncinya: kalau menukar dua pilihan menghasilkan susunan yang dianggap berbeda, urutannya penting.

Siapkan faktorial sekali di awal. Untuk soal dengan banyak pertanyaan, hitung fakt[0..n] satu kali, lalu setiap kombinasi menjadi satu perkalian dan satu invers. Menghitung ulang faktorial di dalam perulangan pertanyaan adalah penyebab Time Limit Exceeded yang paling sering pada bab ini.

Pembagian modulo selalu berarti invers. C(n, k) mod p tidak boleh dihitung dengan /. Untuk p prima, inversnya pangkat(x, p − 2). Kalau pertanyaannya sangat banyak, siapkan juga array invers faktorial supaya setiap pertanyaan tidak memerlukan pangkat modulo tersendiri.

Periksa rumus dengan pencacah brute force. Untuk n ≤ 10, semua susunan bisa dicacah dengan next_permutation atau perulangan bitmask. Membandingkan rumus dengan pencacah pada n kecil menemukan kesalahan faktor dalam hitungan detik.

Kenali bentuk sekat-dan-bintang. Kalimat "bagikan N benda identik kepada K orang" hampir selalu berarti kombinasi: dengan syarat setiap orang mendapat sedikitnya satu, jawabannya C(N − 1, K − 1); kalau boleh ada yang tidak kebagian, C(N + K − 1, K − 1). Bedanya satu kata pada soal.

Batas atas faktorial jauh lebih kecil daripada dugaan. 20! sudah mendekati 2,4 × 10¹⁸ dan 21! melewati long long. Jadi soal yang meminta faktorial tanpa modulo hampir pasti membatasi n ≤ 20 — dan kalau batasannya lebih besar, modulo pasti diminta.

Ringkasan

• Satu pertanyaan memisahkan keduanya: apakah menukar urutan menghasilkan hasil yang berbeda? Ya → permutasi, tidak → kombinasi.
• P(n, r) = n! / (n − r)! adalah perkalian menurun n × (n−1) × … sebanyak r faktor.
• C(n, r) = P(n, r) / r!, karena setiap kelompok berisi r benda bisa disusun dalam r! urutan.
• Permutasi dengan unsur yang sama: bagi dengan faktorial banyaknya masing-masing unsur.
• C(n, r) = C(n−1, r−1) + C(n−1, r) adalah segitiga Pascal, bentuk DP-nya, dan cocok untuk n sampai beberapa ribu.
• Untuk n besar, pakai tabel faktorial modulo dan invers dari teorema Fermat kecil (Bab 14).
• Jalur pada papan yang hanya boleh ke kanan dan ke bawah adalah soal kombinasi: pilih di langkah mana saja bergerak ke bawah.

Latihan bergaya OSN

Ketiga soal berikut memakai kombinasi dengan tiga penyamaran berbeda: permutasi dengan unsur berulang, sekat-dan-bintang, dan pemilihan dengan pantangan. Kenali bentuknya lebih dulu, baru tulis rumusnya.

Kerangka ketiganya ada di exercises/17/osn/.

Soal 1 — Susunan Huruf

Diberikan sebuah kata S. Hitung ada berapa kata berbeda yang bisa dibentuk dengan menyusun ulang seluruh huruf S. Dua susunan dianggap sama kalau hurufnya sama persis pada setiap posisi.

Keluarkan jawabannya modulo 1.000.000.007.

Format masukan. Satu baris berisi kata S yang seluruhnya huruf kecil a sampai z.

Format keluaran. Satu baris berisi banyaknya susunan berbeda modulo 1.000.000.007.

Batasan. 1 ≤ panjang S ≤ 10⁶.

Contoh masukan

aabb

Contoh keluaran

6

Penjelasan. Susunannya aabb, abab, abba, baab, baba, dan bbaa. Kalau keempat hurufnya dianggap berbeda, susunannya 4! = 24; tetapi menukar dua a tidak menghasilkan kata baru, begitu juga dua b, sehingga setiap kata terhitung 2! × 2! = 4 kali.

Kerangkanya: exercises/17/osn/01-susunan-huruf.cpp

Soal 2 — Bagi Permen

Seorang guru punya N permen yang bentuknya sama persis dan akan membagikannya kepada K anak. Setiap anak harus mendapat sedikitnya satu permen, dan seluruh permen harus habis dibagikan.

Dua pembagian dianggap berbeda kalau ada anak yang menerima jumlah permen berbeda. Hitung banyaknya pembagian yang mungkin, modulo 1.000.000.007.

Format masukan. Satu baris berisi dua bilangan bulat N dan K.

Format keluaran. Satu baris berisi banyaknya pembagian modulo 1.000.000.007. Kalau tidak ada pembagian yang mungkin, cetak 0.

Batasan.

• 1 ≤ N ≤ 10⁶
• 1 ≤ K ≤ 10⁶

Contoh masukan

5 2

Contoh keluaran

4

Penjelasan. Pembagiannya (1, 4), (2, 3), (3, 2), dan (4, 1). Karena anaknya bisa dibedakan, (1, 4) dan (4, 1) dihitung sebagai dua pembagian berbeda — sedangkan permennya identik, sehingga yang membedakan hanya jumlahnya.

Kerangkanya: exercises/17/osn/02-bagi-permen.cpp

Soal 3 — Pilih Tanpa Bertetangga

Di sebuah ruangan terdapat N kursi yang berjajar dalam satu baris. Panitia ingin menempatkan K peserta, dan demi mencegah contek-mencontek, tidak boleh ada dua peserta yang duduk di kursi bersebelahan.

Hitung ada berapa cara memilih kursi yang akan diduduki, modulo 1.000.000.007. Pesertanya dianggap tidak dibedakan — yang dihitung hanya kumpulan kursinya.

Format masukan. Satu baris berisi dua bilangan bulat N dan K.

Format keluaran. Satu baris berisi banyaknya cara modulo 1.000.000.007. Kalau tidak ada cara yang mungkin, cetak 0.

Batasan.

• 1 ≤ N ≤ 10⁶
• 0 ≤ K ≤ 10⁶

Contoh masukan

5 2

Contoh keluaran

6

Penjelasan. Pilihan kursinya (1,3), (1,4), (1,5), (2,4), (2,5), dan (3,5). Pilihan seperti (2,3) tidak sah karena kursinya bersebelahan.

Kerangkanya: exercises/17/osn/03-pilih-tanpa-bertetangga.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.