17. Permutasi dan kombinasi — Pembahasan PR

Soal 1 dikerjakan di kertas. Berkas .cpp untuk soal 2 sampai tantangan ada di exercises/17/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Untuk soal kertas, tulis dulu jawabanmu, baru bandingkan — membaca jawaban orang lain terasa jelas padahal belum tentu bisa diulang sendiri. Bagian Uji berisi masukan dan keluaran yang sudah diperiksa untuk soal berkode.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/17/homework/solutions/02-pascal.cpp
./jawab

Soal 1 — Hitung di kertas

a. Susunan huruf BUKU → 12.

Empat huruf dengan U muncul dua kali: 4! / 2! = 24 / 2 = 12.

b. Memilih 3 dari 8 siswa → 336 dan 56.

Kalau ketiganya punya tugas berbeda, urutan penting: P(8, 3) = 8 × 7 × 6 = 336. Kalau tugasnya sama, urutan tidak penting: C(8, 3) = 336 / 3! = 56.

Perhatikan hubungannya: jawaban kedua adalah jawaban pertama dibagi 3!, karena setiap kelompok yang sama bisa disusun dalam 6 urutan.

c. Jalur pada papan 3 × 4 → 10.

Dari pojok kiri atas ke kanan bawah dibutuhkan 2 langkah ke bawah dan 3 langkah ke kanan, seluruhnya 5 langkah. Tinggal memilih 2 posisi di antara 5 untuk langkah bawah: C(5, 2) = 10.

d. Memilih paling sedikit satu dari 10 siswa → 1.023.

Seluruh himpunan bagian ada 2¹⁰ = 1.024, termasuk himpunan kosong. Buang yang kosong: 1.023. Ini pemakaian komplemen dari Bab 16.

Soal 2 — Segitiga Pascal

Soal. Cetak segitiga Pascal baris 0 sampai n (≤ 30).

Cara berpikir. Setiap baris dibangun dari baris di atasnya dengan C(n, r) = C(n−1, r−1) + C(n−1, r), dan setiap baris diawali C(n, 0) = 1. Tidak ada pembagian dan tidak ada faktorial, sehingga tidak ada risiko pembulatan.

Untuk n = 30, nilai terbesarnya C(30, 15) = 155.117.520 — masih muat di int, tetapi pakai long long sebagai kebiasaan.

Pembahasan.

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

Uji. Masukan 5 menghasilkan enam baris:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Masukan 0 menghasilkan satu baris berisi 1. Dua pemeriksaan cepat untuk tiap baris: angkanya simetris, dan jumlah satu baris sama dengan 2ⁿ — baris terakhir di atas berjumlah 32 = 2⁵.

Kesalahan umum.

• Mengisi C[i][r] untuk r > i. Nilainya nol dan ikut tercetak.
• Mencetak spasi di akhir baris.
• Memakai rumus faktorial untuk n = 30. 30! tidak muat di long long walaupun hasil akhirnya muat.

Soal 3 — Kombinasi modulo

Soal. 100.000 pertanyaan C(n, r) mod 10⁹ + 7 dengan n sampai sejuta.

Cara berpikir. Tabel Pascal berukuran sejuta × sejuta mustahil. Yang dipakai: tabel faktorial sekali di awal (sejuta sel), lalu setiap pertanyaan dijawab dengan

C(n, r) = n! × (r!)⁻¹ × ((n−r)!)⁻¹ mod p

Invers dihitung dengan teorema Fermat kecil, O(log p) per pertanyaan. Total: 10⁶ untuk persiapan + 10⁵ × 30 untuk pertanyaan ≈ 4 juta langkah.

Jangan lupa ios::sync_with_stdio(false) untuk masukan sebesar ini.

Pembahasan.

fakt[0] = 1;
for (int i = 1; i < MAKS; i++) fakt[i] = fakt[i - 1] * i % MOD;

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

Periksa: C(10, 3) = 120, C(30, 15) = 155.117.520 (sama dengan hasil Pascal), C(1.000.000, 500.000) mod p = 996.692.777.

Uji.

Baris ketiga berguna sekali untuk menguji: C(30, 15) = 155.117.520 masih lebih kecil daripada 10⁹ + 7, jadi kalau jawabanmu berbeda di sini, kesalahannya pasti pada rumus atau inversnya — bukan pada modulonya.

Kesalahan umum.

• Membagi fakt[n] / bawah dengan pembagian bulat. Nilai yang tersimpan sudah berupa sisa; hasilnya tidak berhubungan dengan jawaban (sering malah nol).
• Menyiapkan tabel faktorial di dalam perulangan pertanyaan, sehingga dikerjakan 100.000 kali.
• Lupa menangani r > n, yang seharusnya bernilai 0.

Soal 4 — Jalur di papan

Soal. Jalur pada papan b × k sampai 500.000 × 500.000.

Cara berpikir. Setiap jalur adalah barisan langkah: b − 1 kali ke bawah dan k − 1 kali ke kanan, dalam urutan apa pun. Jadi soalnya menjadi "pilih posisi langkah bawah di antara seluruh langkah":

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

Ukuran terbesarnya sekitar sejuta, jadi tabel faktorial sejuta sel sudah cukup.

Pembahasan.

cout << kombinasi((int)(b - 1 + k - 1), (int)(b - 1)) << "\n";

Periksa: 3 4 memberi 10 — sama dengan jawaban kertas soal 1(c).

Uji.

Baris terakhir menguji ukuran tabel faktorial: jalur pada papan 500.000 × 500.000 memerlukan C(999.998, 499.999), jadi tabel faktorialnya harus disiapkan sampai sekitar satu juta — bukan sampai 500.000.

Kesalahan umum.

• Memakai DP papan b × k (dp[i][j] = dp[i-1][j] + dp[i][j-1]). Benar untuk papan kecil, tetapi 500.000 × 500.000 sel mustahil disimpan.
• Salah menghitung jumlah langkah: papan b × k berisi b baris dan k kolom, sehingga langkahnya b − 1 dan k − 1, bukan b dan k.

Tantangan — Periksa rumusmu

Soal. Bandingkan segitiga Pascal dengan pencacahan langsung.

Cara berpikir. cacah(n, r) menelusuri seluruh 2ⁿ himpunan bagian dan mencacah yang berukuran tepat r. Untuk n = 15 itu 32.768 mask dikali 15 pemeriksaan bit — ringan.

Pemeriksaan ketiga (jumlah satu baris = 2ⁿ) berguna karena sifatnya berbeda: ia menguji seluruh baris sekaligus, bukan satu nilai.

Pembahasan.

long long cacah(int n, int r) {
    long long banyak = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int bit = 0;
        for (int i = 0; i < n; i++) if (mask & (1 << i)) bit++;
        if (bit == r) banyak++;
    }
    return banyak;
}

Keluarannya: rumus dan cacahan cocok untuk semua n ≤ 15, dan jumlah tiap barisnya sama dengan 2ⁿ.

Kebiasaan ini — menguji rumus kombinatorika dengan pencacahan kecil — adalah cara paling cepat menemukan salah rumus sebelum jawaban dikirim. Ia sama dengan penguji pembanding Bab 10, hanya diterapkan pada matematika.

Uji. Program jawabannya mencetak kesimpulannya sendiri:

rumus dan cacahan cocok untuk semua n <= 15
jumlah tiap baris sama dengan 2^n

Dua pemeriksaan itu saling melengkapi. Yang pertama membandingkan rumus dengan pencacahan langsung, sehingga menangkap kesalahan rumus. Yang kedua memeriksa sifat yang harus dipenuhi seluruh baris sekaligus, sehingga menangkap kesalahan yang kebetulan lolos pada satu nilai r tertentu. Pola dua lapis ini persis penguji pembanding Bab 10, diterapkan pada rumus alih-alih pada algoritma.

Kesalahan umum.

• Menguji dengan n besar sehingga pencacahannya sendiri terlalu lambat.
• Menulis cacah memakai rumus lagi (misalnya faktorial), sehingga yang dibandingkan dua bentuk dari rumus yang sama. Pencacahan harus polos.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/17/osn/solutions/.

Soal 1 — Susunan Huruf

Cara berpikir. Andaikan semua huruf dianggap berbeda — misalnya dua a diberi tanda a₁ dan a₂. Maka susunannya N!. Tetapi menukar a₁ dengan a₂ menghasilkan kata yang sama, jadi setiap kata sebenarnya terhitung berkali-kali: sebanyak cara mengurutkan huruf-huruf kembar itu di antara mereka sendiri.

Kalau huruf ke-h muncul cₕ kali, setiap kata terhitung ∏ cₕ! kali. Jadi jawabannya:

N! / (c₁! × c₂! × … × c₂₆!)

Karena jawabannya modulo, pembagiannya dikerjakan dengan invers: untuk modulus prima, x⁻¹ ≡ x^(p−2).

Pembahasan.

vector<long long> fakt(n + 1);
fakt[0] = 1;
for (int i = 1; i <= n; i++) fakt[i] = fakt[i - 1] * i % MOD;

long long cacah[26] = {0};
for (char c : s) cacah[c - 'a']++;

long long hasil = fakt[n];
for (int h = 0; h < 26; h++) {
    if (cacah[h] > 1) hasil = hasil * invers(fakt[cacah[h]]) % MOD;
}

Paling banyak ada 26 huruf berbeda, jadi paling banyak 26 kali pangkat modulo — biayanya tidak berarti dibandingkan menyiapkan faktorialnya. Diukur pada mesin penulis, kata sepanjang 10⁶ selesai dalam 0,02 detik.

Uji.

Ketiga baris pertama layak dicek dengan tangan; bandingkan juga dengan program pencacah untuk kata sepanjang 6–7 huruf.

Kesalahan umum.

• Membagi dengan / alih-alih mengalikan dengan invers. Hasilnya hampir selalu salah karena fakt[n] sudah tersisa modulo.
• Menghitung n! dengan long long tanpa modulo. 21! saja sudah meluap.
• Memakai indeks c - 'A', padahal masukannya huruf kecil.

Soal 2 — Bagi Permen

Cara berpikir. Bayangkan N permen berjajar dalam satu baris. Di antara dua permen berdekatan ada celah, dan seluruhnya ada N − 1 celah.

Memasang sekat pada sebuah celah memotong barisan menjadi dua bagian. Untuk mendapat K bagian, diperlukan tepat K − 1 sekat, dan setiap celah paling banyak dipasangi satu sekat — kalau dua sekat berada di celah yang sama, akan ada anak yang tidak kebagian.

Jadi soalnya berubah menjadi: berapa cara memilih K − 1 celah dari N − 1 celah? Jawabannya C(N − 1, K − 1).

Syarat sahnya K ≤ N: kalau anaknya lebih banyak daripada permennya, tidak ada pembagian yang mungkin.

Pembahasan.

if (k > n) { cout << "0\n"; return 0; }

// C(n-1, k-1)
long long atas = fakt[n - 1];
long long bawah = fakt[k - 1] * fakt[n - k] % MOD;

cout << atas * pangkat(bawah, MOD - 2) % MOD << "\n";

Pemeriksaan k > n harus mendahului rumusnya — tanpa itu, fakt[n - k] dibaca dengan indeks negatif.

Uji.

Kesalahan umum.

• Memakai C(N, K). Itu jawaban untuk soal yang berbeda.
• Memakai C(N + K − 1, K − 1), yaitu rumus untuk kasus "boleh ada anak yang tidak kebagian".
• Lupa memeriksa K > N.

Soal 3 — Pilih Tanpa Bertetangga

Cara berpikir. Ini bentuk yang tampak baru tetapi sebenarnya kombinasi biasa dengan penyamaran.

Bayangkan K peserta sudah duduk berurutan dari kiri ke kanan. Syaratnya adalah ada sedikitnya satu kursi kosong di antara dua peserta yang berdekatan. Ambil satu kursi kosong wajib itu dari setiap celah di antara peserta — seluruhnya K − 1 kursi — lalu singkirkan dari perhitungan. Sisanya N − (K − 1) kursi, dan pada barisan yang tinggal itu peserta boleh dipilih bebas.

Jadi jawabannya C(N − K + 1, K).

Cara memeriksa cepat: untuk N = 5, K = 2, rumusnya memberi C(4, 2) = 6, dan pilihan yang sah memang ada enam.

Syarat sahnya K ≤ N − K + 1. Kalau tidak, jawabannya 0.

Pembahasan.

long long atasN = n - k + 1;
if (k > atasN || atasN < 0) { cout << "0\n"; return 0; }

vector<long long> fakt(atasN + 1);
fakt[0] = 1;
for (long long i = 1; i <= atasN; i++) fakt[i] = fakt[i - 1] * i % MOD;

long long bawah = fakt[k] * fakt[atasN - k] % MOD;
cout << fakt[atasN] * pangkat(bawah, MOD - 2) % MOD << "\n";

Uji.

Kasus 5 0 sering terlewat. Memilih nol kursi adalah satu cara, bukan nol cara, dan rumusnya memang memberi C(6, 0) = 1.

Kesalahan umum.

• Memakai C(N, K) lalu mengurangi yang bersebelahan satu per satu. Bisa benar untuk K = 2, tetapi tidak bisa diperluas.
• Lupa memeriksa K > N − K + 1, sehingga fakt dibaca dengan indeks negatif.
• Menjawab 0 untuk K = 0.

Kalau masih tersendat

• Bingung permutasi atau kombinasi → Bab 17, pertanyaan pembukanya: apakah menukar urutan menghasilkan hasil yang berbeda?
• Jawaban r! kali terlalu besar → berarti kamu memakai permutasi untuk soal kombinasi.
• Kombinasi modulo memberi angka yang salah → Bab 17, peringatan tentang pembagian sesudah modulo; pakai invers dari Bab 14.

Dengan bab ini seluruh isi buku sudah dilalui. Langkah berikutnya bukan bab baru, melainkan soal: kerjakan arsip soal OSN di penilai daring yang kamu daftari pada Bab 01, dan pakai kembali kebiasaan yang sama — abstraksi, hitung langkah, uji kasus tepi.