16. Aturan penjumlahan dan perkalian

Kombinatorika adalah ilmu mencacah: menghitung banyaknya kemungkinan tanpa perlu mendaftar satu per satu. Di OSN ia muncul sebagai soal matematika langsung, dan sebagai bagian dari soal program yang jawabannya terlalu besar untuk dihitung dengan perulangan.

Dua aturan menjadi dasar semuanya.

Aturan penjumlahan

Kalau sebuah pilihan bisa dilakukan dengan a cara atau b cara, dan kedua kelompok itu tidak beririsan, maka seluruhnya ada a + b cara.

Kata kuncinya atau, dan syaratnya tidak beririsan.

Contoh: di meja ada 3 jenis kue dan 4 jenis gorengan. Kalau Budi mengambil satu makanan, ada 3 + 4 = 7 pilihan.

Aturan perkalian

Kalau sebuah kegiatan terdiri dari dua langkah, langkah pertama bisa dilakukan dengan a cara dan langkah kedua dengan b cara (berapa pun hasil langkah pertama), maka seluruhnya ada a × b cara.

Kata kuncinya dan, dan syaratnya jumlah cara langkah kedua tidak bergantung pada pilihan langkah pertama.

Contoh: Budi mengambil satu kue dan satu gorengan: 3 × 4 = 12 pasangan.

Gambar pohonnya memperlihatkan kenapa hasilnya dikalikan: setiap cabang pertama bercabang lagi sebanyak pilihan kedua.

                 pilih kue
        /            |            \
     kue A        kue B         kue C
    / | | \      / | | \       / | | \
   g1 g2 g3 g4  g1 g2 g3 g4   g1 g2 g3 g4

Ada 3 cabang di tingkat pertama, masing-masing melahirkan 4 cabang, jadi daunnya 3 × 4 = 12.

Kesalahan yang paling sering di dua aturan ini bukan salah menghitung, melainkan salah memilih aturan. Satu pertanyaan memutuskannya:

Apakah aku sedang memilih satu di antara beberapa kelompok (jumlah), atau mengambil satu dari masing-masing kelompok (kali)?

Menggabungkan keduanya

Plat nomor terdiri dari satu huruf (A–Z) diikuti tiga angka (0–9), dan angka boleh berulang. Ada berapa plat?

26 × 10 × 10 × 10 = 26.000.

Kalau angka tidak boleh berulang?

26 × 10 × 9 × 8 = 18.720. Setelah satu angka dipakai, pilihan berikutnya berkurang — inilah bentuk awal permutasi (Bab 17).

Berapa banyak kata sandi sepanjang 4 dari huruf kecil a–z, yang harus mengandung minimal satu huruf a?

Di sini lebih mudah menghitung kebalikannya:

• seluruh kata sandi: 26⁴ = 456.976
• yang tidak mengandung a sama sekali: 25⁴ = 390.625
• jawabannya: 456.976 − 390.625 = 66.351

Teknik ini bernama komplemen, dan sangat sering dipakai: menghitung yang "minimal satu" hampir selalu lebih mudah lewat "tidak ada satu pun".

Alasan menghitung langsung lebih sulit: "minimal satu a" berarti bisa satu a, bisa dua, bisa tiga, bisa empat — empat kelompok yang harus dihitung lalu dijumlahkan, dan kelompok-kelompok itu mudah tumpang tindih kalau tidak hati-hati. Sedangkan "tidak ada a sama sekali" hanya satu perhitungan: setiap posisi bebas memilih 25 huruf.

Contoh kecil yang bisa diperiksa dengan tangan: kata sandi sepanjang 3 dari 4 huruf a b c d, minimal satu a. Seluruhnya 4³ = 64, yang tanpa a 3³ = 27, jadi jawabannya 64 − 27 = 37. Mencacah langsung ketiga puluh tujuh kata itu satu per satu bisa dilakukan, tetapi jauh lebih lama — dan untuk panjang 10 sudah mustahil.

Bentuk lain yang juga memakai komplemen:

Ketika kelompoknya beririsan

Aturan penjumlahan hanya sah bila kedua kelompok tidak punya anggota bersama. Kalau beririsan, yang dipakai adalah inklusi-eksklusi:

|A ∪ B| = |A| + |B| − |A ∩ B|

Contoh: dari bilangan 1 sampai 100, berapa yang habis dibagi 3 atau 5?

• habis dibagi 3: ⌊100/3⌋ = 33
• habis dibagi 5: ⌊100/5⌋ = 20
• habis dibagi 15 (keduanya): ⌊100/15⌋ = 6
• jawabannya: 33 + 20 − 6 = 47

Tanpa mengurangi irisannya, bilangan seperti 15, 30, dan 45 terhitung dua kali.

Dua hal yang perlu dipahami dari perhitungan itu. Pertama, banyaknya bilangan dari 1 sampai n yang habis dibagi p adalah n / p dengan pembagian bulat — persis operasi / di C++ untuk bilangan positif, tanpa perlu perulangan. Kedua, irisan "habis dibagi 3 dan habis dibagi 5" bukan 3 × 5 dalam semua kasus, melainkan KPK-nya (Bab 15). Untuk 3 dan 5 kebetulan sama karena keduanya saling prima, tetapi untuk 4 dan 6 irisannya adalah kelipatan 12, bukan 24.

Untuk tiga himpunan, polanya berlanjut:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Tanda-tandanya berselang-seling: suku tunggal ditambah, suku berpasangan dikurangi, suku bertiga ditambah lagi. Alasannya bisa dilacak pada satu bilangan yang berada di ketiga himpunan sekaligus: ia terhitung 3 kali oleh suku tunggal, dikurangi 3 kali oleh suku berpasangan, lalu ditambah 1 kali oleh suku bertiga — total 1, persis seperti seharusnya.

Contoh: dari 1 sampai 100, berapa yang habis dibagi 2, 3, atau 5?

50 + 33 + 20 − 16 − 10 − 6 + 3 = 74

dengan 16 = ⌊100/6⌋, 10 = ⌊100/10⌋, 6 = ⌊100/15⌋, dan 3 = ⌊100/30⌋.

Memeriksa hitungan dengan program

Inilah kebiasaan yang membedakan peserta yang teliti: setiap rumus kombinatorika bisa diuji dengan program pencacah untuk kasus kecil.

// rumus: 26 * 10 * 9 * 8
long long rumus = 26LL * 10 * 9 * 8;

// pencacahan langsung
long long cacah = 0;
for (int h = 0; h < 26; h++)
    for (int a = 0; a < 10; a++)
        for (int b = 0; b < 10; b++)
            for (int c = 0; c < 10; c++)
                if (a != b && a != c && b != c) cacah++;

cout << rumus << " " << cacah << "\n";   // harus sama

Kalau keduanya berbeda, rumusnya salah — dan lebih baik ketahuan sekarang daripada saat lomba.

Pola soal OSN

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Terjemahkan soal menjadi satu kalimat "ada berapa cara memilih ...". Kalau kalimat itu berbunyi "lalu", pakai aturan perkalian; kalau berbunyi "atau", pakai aturan penjumlahan. Kebanyakan kesalahan pada soal kombinatorika lahir dari salah memilih di antara dua kata itu.

Hitung dulu dengan tangan untuk kasus terkecil. Untuk N = 1, N = 2, dan N = 3, jawabannya sering bisa dicacah satu per satu di kertas. Rumusmu harus cocok pada ketiganya sebelum dipercaya untuk N = 10¹⁸.

Periksa rumus dengan program pencacah. Tulis brute force yang mencacah semua kemungkinan untuk N kecil, lalu bandingkan dengan rumusmu. Ini cara paling cepat menemukan kesalahan sebesar satu faktor — dan satu-satunya cara yang bisa dipercaya saat waktu lomba menipis.

Komplemen hampir selalu lebih mudah daripada perhitungan langsung. Kalimat "sedikitnya satu" adalah isyaratnya: hitung semuanya, lalu kurangi yang tidak punya satu pun. Untuk "sedikitnya satu a dan sedikitnya satu b", komplemennya dua himpunan yang beririsan, dan irisannya harus dikembalikan sekali — itulah inklusi-eksklusi.

Jawaban kombinatorika meledak, jadi modulo hampir selalu diminta. Begitu ada % MOD, seluruh kebiasaan Bab 14 berlaku: ambil sisa di setiap langkah, pakai long long, dan bungkus pengurangan dengan + MOD.

Pengurangan modulo tanpa penyesuaian adalah bug yang menunggu. Rumus komplemen selalu berisi pengurangan, dan hasil sementaranya bisa negatif. Bentuk bakunya:

hasil = ((semua - tanpa) % MOD + MOD) % MOD;

Perhatikan apakah urutannya diperhitungkan. "Pasangan (x, y)" biasanya berarti terurut — (1, 2) dan (2, 1) berbeda. "Memilih dua orang" biasanya tidak. Soal OSN menyebutkannya, tetapi kalimatnya mudah terlewat, dan jawabannya berbeda tepat dua kali lipat.

Ringkasan

• Aturan penjumlahan untuk "atau" pada kelompok yang tidak beririsan; aturan perkalian untuk "dan" yang berlangkah.
• Kalau kelompoknya beririsan, pakai inklusi-eksklusi: |A ∪ B| = |A| + |B| − |A ∩ B|, dan tanda berselang-seling untuk tiga himpunan atau lebih.
• Irisan "habis dibagi p dan q" adalah kelipatan KPK(p, q), bukan selalu p × q.
• "Minimal satu" hampir selalu lebih mudah lewat komplemen: seluruhnya dikurangi "tidak ada satu pun".
• Banyaknya bilangan 1 sampai n yang habis dibagi p adalah n / p dengan pembagian bulat.
• Setiap rumus cacahan bisa dan sebaiknya diperiksa dengan pencacahan langsung pada data kecil, persis seperti penguji pembanding di Bab 10.

Latihan bergaya OSN

Ketiganya diselesaikan dengan rumus, bukan pencacahan. Sebelum mengetik, kerjakan N = 1 dan N = 2 dengan tangan, lalu pastikan rumusmu cocok.

Kerangka ketiganya ada di exercises/16/osn/.

Soal 1 — Bendera Berwarna

Sebuah bendera terdiri atas N jalur yang berjajar dari kiri ke kanan. Setiap jalur diwarnai dengan salah satu dari K warna yang tersedia. Dua jalur yang bersebelahan tidak boleh sewarna; jalur yang berjauhan boleh.

Hitung ada berapa bendera berbeda yang bisa dibuat, lalu keluarkan sisanya jika dibagi 1.000.000.007.

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

Format keluaran. Satu baris berisi banyaknya bendera modulo 1.000.000.007.

Batasan.

• 1 ≤ N ≤ 10¹⁸
• 1 ≤ K ≤ 10⁹

Contoh masukan

3 3

Contoh keluaran

12

Penjelasan. Jalur pertama boleh warna apa saja: 3 pilihan. Jalur kedua boleh warna apa saja kecuali warna jalur pertama: 2 pilihan. Jalur ketiga boleh warna apa saja kecuali warna jalur kedua: 2 pilihan. Seluruhnya 3 × 2 × 2 = 12.

Perhatikan kasus K = 1: satu-satunya bendera yang sah adalah bendera berjalur tunggal.

Kerangkanya: exercises/16/osn/01-bendera-warna.cpp

Soal 2 — Sandi Dua Huruf Wajib

Sebuah sistem menerima kata sandi sepanjang tepat N huruf, dan huruf yang boleh dipakai adalah K huruf pertama alfabet. Aturan tambahannya: kata sandi wajib memuat sedikitnya satu huruf a dan sedikitnya satu huruf b.

Hitung ada berapa kata sandi yang sah, lalu keluarkan sisanya jika dibagi 1.000.000.007.

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

Format keluaran. Satu baris berisi banyaknya kata sandi modulo 1.000.000.007.

Batasan.

• 1 ≤ N ≤ 10¹⁸
• 2 ≤ K ≤ 26

Contoh masukan

2 3

Contoh keluaran

2

Penjelasan. Hurufnya a, b, dan c. Dari sembilan kata sepanjang dua huruf, yang memuat a sekaligus b hanya ab dan ba.

Kerangkanya: exercises/16/osn/02-sandi-dua-huruf.cpp

Soal 3 — Pasangan Berjumlah Kelipatan K

Hitung ada berapa pasangan terurut (x, y) dengan 1 ≤ x, y ≤ N sehingga x + y habis dibagi K. Pasangan (1, 2) dan (2, 1) dianggap berbeda, dan x boleh sama dengan y.

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

Format keluaran. Satu baris berisi banyaknya pasangan.

Batasan.

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

Contoh masukan

5 3

Contoh keluaran

9

Penjelasan. Pasangannya adalah (1,2), (2,1), (1,5), (5,1), (2,4), (4,2), (3,3), (4,5), dan (5,4). Memeriksa semua pasangan satu per satu memerlukan N² = 10¹⁸ langkah, jadi yang harus dikelompokkan adalah sisanya, bukan bilangannya.

Kerangkanya: exercises/16/osn/03-pasangan-kelipatan.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.