Kombinasi

Kombinasi kita gunakan jika dari suatu himpunan objek kita memilih sejumlah objek tertentu dan urutan pemilihan objek-objek itu tidak diperhatikan. Contoh khasnya adalah undian 6 dari 49: di dalam wadah undian ada 49 nomor dan 6 nomor diambil darinya, sedangkan urutan pengambilannya tidak penting.

Penurunan rumus

Roda keberuntungan

Misalkan diberikan himpunan M, misalnya M = {a, b, c, d, e}. Kombinasi k unsur adalah himpunan bagian K ⊆ M yang mempunyai tepat k anggota. Karena K adalah himpunan, urutan tentu saja tidak diperhatikan. Jadi, kombinasi tiga unsur dari himpunan M misalnya {a, b, d} atau {b, c, d}.

Perbedaannya dengan permutasi k dari n unsur: pada permutasi urutan diperhatikan, sehingga (a, b, e) dan (e, b, a) adalah dua permutasi yang berbeda. Namun, keduanya adalah kombinasi yang sama, karena (a, b, e) dan (e, b, a) memuat unsur yang sama. Pada kombinasi kita tidak peduli bahwa unsur-unsurnya tersusun dalam urutan yang lain.

Namun, permutasi dapat kita manfaatkan untuk memperoleh rumus banyak semua kombinasi yang berbeda. Kita tahu bahwa banyak permutasi k unsur dari himpunan dengan n anggota adalah

$P (n, k) = \frac{n!}{(n - k)!} .$

Jika kita menghitung banyak semua permutasi tiga unsur dari himpunan M = {a, b, c, d, e} tadi, kita memperoleh P(5, 3) = 60 permutasi yang berbeda. Namun, di antaranya untuk setiap tripel terdapat juga semua susunan ulangnya. Artinya, di sana ada tripel abc, tetapi juga tripel acb, bac, bca, cab dan cba. Ini enam permutasi yang berbeda, tetapi hanya satu kombinasi, karena semuanya memuat unsur yang sama.

Jadi, jika kita mempunyai suatu tripel, ada berapa susunan berbeda dari tripel itu? Jawabannya 3!. Dengan kata lain, banyak permutasi tiga unsur adalah 3! kali banyak kombinasi tiga unsur. Alih-alih menghitung satu kombinasi, kita menghitung 3! permutasi, yaitu setiap susunan dari tripel itu. Jadi, jika banyak permutasi kita bagi dengan 3!, kita memperoleh banyak kombinasi.

Cara tadi dapat diperumum. Jika kita mencari banyak semua kombinasi k unsur yang berbeda dari himpunan dengan n anggota, banyaknya (kita tulis C(n, k)) sama dengan

$C (n, k) = \frac{P (n, k)}{k!},$

yaitu banyak permutasi dibagi k!, yang merupakan banyak susunan setiap kelompok k unsur. Rumus ini dapat kita ubah dengan menguraikan rumus permutasi:

$C (n, k) = \frac{P (n, k)}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Contoh: banyak kombinasi dua unsur dari himpunan {a, b, c} adalah

$C (3, 2) = \frac{3!}{1! \cdot 2!} = 3$

dan kombinasinya adalah {a, b}, {a, c} dan {b, c}. Untuk kombinasi tiga unsur dari himpunan semula M = {a, b, c, d, e} kita memperoleh

$C (5, 3) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

dan kombinasinya adalah {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Koefisien binomial

Selain notasi C(n, k) seperti di atas, sering dipakai notasi yang disebut koefisien binomial. Bentuknya seperti ini:

$(\binom{n}{k})$

Bentuk ini mirip pecahan tanpa garis pecahan (yang karena kebiasaan mungkin tetap kamu tulis), tetapi dengan tanda kurung (tanda kurung ini tidak boleh dihilangkan, harus selalu ada). Koefisien binomial dibaca “kombinasi k dari n” atau “n pilih k”. Nilainya sama dengan C(n, k).

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Jadi, jika ada himpunan dengan 5 anggota dan kita memilih kelompok berisi empat anggota darinya, banyak semua kelompok itu adalah

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Hubungan dasar

Untuk koefisien binomial dan n ∈ ℕ berlaku:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Selanjutnya, untuk n, k ∈ ℕ₀ dan k ≤ n berlaku

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

Untuk n, k ∈ ℕ₀ dan k < n berlaku

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Kalkulator

Kalkulator berikut menghitung koefisien binomial n pilih k.

Contoh soal

Kita mulai dengan undian 6 dari 49 yang sudah disebutkan. Dari wadah undian berisi 49 bola diambil 6 bola. Berapa banyak hasil undian yang berbeda?

Pertama-tama: apakah urutan pengambilan nomor diperhatikan? Tidak, yang ditebak hanya nomornya, bukan urutannya. Jadi, kita menggunakan kombinasi. Ada 49 bola dan diambil 6 bola, sehingga diperoleh koefisien binomial

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13.983 .816$

Seluruhnya ada 13.983.816 kemungkinan hasil undian. Omong-omong, ini berarti peluang menebak dengan benar dengan satu tebakan adalah 1/13.983.816, yaitu 0,00000715112%.
Andi diminta memilih 4 teman dari 13 teman sekelasnya untuk diajak ikut lomba cerdas cermat. Berapa banyak kelompok berisi empat orang yang dapat dipilih Andi?

Ini juga contoh sederhana kombinasi. Urutan tidak diperhatikan, karena keempat teman yang terpilih menjadi anggota tim yang sama. Jadi, ada himpunan 13 teman, dan setiap kali kita memilih 4 orang. Diperoleh koefisien binomial

$(\binom{13}{4}) = 715.$
Ada sekelompok lima puluh orang: separuhnya laki-laki dan separuhnya perempuan. Berapa banyak kelompok tiga orang yang berbeda jika kelompok itu tidak boleh terdiri atas orang yang berjenis kelamin sama saja (artinya, dalam satu kelompok tidak boleh ada tiga laki-laki atau tiga perempuan)?

Kombinasi ini sedikit lebih rumit. Jika kelompok yang anggotanya berjenis kelamin sama kita keluarkan, tinggal dua kemungkinan susunan kelompok: dua laki-laki dan satu perempuan, atau satu laki-laki dan dua perempuan. Banyak kombinasi jenis pertama (dua laki-laki dan satu perempuan) sama dengan banyak kombinasi jenis kedua. Jadi, cukup kita hitung banyak kombinasi jenis pertama, lalu kita kalikan dua. Sekarang soalnya mudah. Kita tentukan banyak pasangan laki-laki yang berbeda, yaitu dua puluh lima pilih dua, lalu kita kalikan dengan banyak cara memilih satu perempuan (yaitu dua puluh lima, lihat hubungan dasar di atas, tepatnya baris kedua). Hasil ini tinggal kita kalikan dua, dan diperoleh hasil akhir:

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
Di dalam sebuah kotak ada 15 barang, 4 di antaranya cacat. Ada berapa cara memilih 6 barang sehingga
- tidak ada yang cacat? Di sini kita memilih 6 barang dari 15 − 4 = 11 barang yang tidak cacat. Diperoleh koefisien binomial
  
  $(\binom{11}{6}) = 462.$
- tepat satu barang cacat? Kita memilih himpunan yang berisi 5 barang baik dan 1 barang cacat. Ada 11 barang baik dan 4 barang cacat. Dengan aturan perkalian, diperoleh hasil:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- paling banyak satu barang cacat? Kita gunakan hasil-hasil sebelumnya. Kita tahu bahwa ada 462 cara memilih tepat 6 barang baik dan 1848 cara memilih lima barang baik dan satu barang cacat. Dengan aturan penjumlahan, kedua hasil ini kita jumlahkan dan diperoleh yang kita cari, yaitu paling banyak satu barang cacat (= tidak ada barang cacat atau tepat satu). Hasilnya adalah 462 + 1848 = 2310.

Daftar isi: Kombinatorika, Permutasi k dari n unsur, Permutasi n unsur, Kombinasi, Susunan dengan pengulangan, Kombinasi dengan pengulangan, Ada berapa PIN yang berbeda?

« Artikel sebelumnya: Permutasi n unsur

Artikel berikutnya: Susunan dengan pengulangan »