Algoritmika · Pelajaran 5 dari 10

Kombinatorika dasar

10 menit baca · BelajarCode

Kombinatorika adalah ilmu menghitung banyaknya kemungkinan tanpa mendaftar semuanya satu per satu.

Aturan perkalian dan penjumlahan

Aturan perkalian: jika langkah pertama punya a pilihan dan langkah kedua punya b pilihan, keduanya bersama-sama punya a × b pilihan.
Aturan penjumlahan: jika harus memilih salah satu dari dua kelompok yang tidak beririsan, banyak pilihannya a + b.

Contoh: kode loker terdiri dari 3 huruf lalu 2 angka. Banyak kodenya 26 × 26 × 26 × 10 × 10 = 1.757.600.

Permutasi dan kombinasi

	Permutasi	Kombinasi
Urutan diperhatikan?	Ya	Tidak
Rumus memilih r dari n	n! / (n - r)!	n! / (r! × (n - r)!)
Contoh	Memilih ketua, wakil, dan sekretaris dari 8 orang	Memilih 3 orang perwakilan dari 8 orang
Hasil contoh	336	56

Memilih ketua, wakil, dan sekretaris berbeda dengan memilih tiga perwakilan, karena pada yang pertama setiap posisi punya peran sendiri.

Python

1import math23print("5 buku disusun di rak:", math.factorial(5))4print("Ketua, wakil, sekretaris dari 8:", math.perm(8, 3))5print("3 perwakilan dari 8:", math.comb(8, 3))6print("Jabat tangan 10 orang:", math.comb(10, 2))

Keluaran

5 buku disusun di rak: 120
Ketua, wakil, sekretaris dari 8: 336
3 perwakilan dari 8: 56
Jabat tangan 10 orang: 45

Jabat tangan adalah kombinasi 2 dari 10, karena jabat tangan A dengan B sama dengan B dengan A.

Prinsip sarang merpati

Jika ada lebih banyak merpati daripada sarang, pasti ada sarang yang berisi lebih dari satu merpati. Contohnya, di antara 13 orang pasti ada dua yang lahir di bulan yang sama, karena hanya ada 12 bulan.

Prinsip sederhana ini sering dipakai di soal OSN untuk membuktikan bahwa sesuatu pasti terjadi.

Periksa dengan mendaftar kasus kecil

Kesalahan paling umum adalah tertukar antara permutasi dan kombinasi. Untuk memeriksa, coba versi kecil soalnya, misalnya memilih 2 dari 3 orang, lalu daftar semua kemungkinannya secara manual dan bandingkan dengan rumusmu.

Cek pemahaman

Dari 6 siswa akan dipilih 2 orang untuk menjadi petugas upacara dengan tugas yang sama. Berapa banyak cara memilihnya?

12153036

Latihan

Tiga soal hitung

Berapa banyak PIN 4 digit (angka 0 sampai 9) yang semua digitnya berbeda?
Dari 12 anggota klub, berapa banyak cara memilih ketua dan wakil ketua?
Dari 12 anggota yang sama, berapa banyak cara memilih 2 orang untuk mewakili klub di rapat?

Pembahasan

Digit pertama 10 pilihan, kedua 9, ketiga 8, keempat 7: 10 × 9 × 8 × 7 = 5.040. Ini permutasi 4 dari 10.
Urutan diperhatikan karena ketua dan wakil berbeda peran: 12 × 11 = 132.
Urutan tidak diperhatikan: 132 / 2 = 66.