Kombinasi dengan Pengulangan

Jika S adalah suatu himpunan yang memiliki 4 buah anggota, maka kita dapat menghitung banyak semua himpunan bagian yang beranggotakan 3 elemen dengan cara mendaftar semua himpunan bagian tersebut atau dengan memakai kombinasi, C(4, 3). Karena C(4, 3) = 4, maka banyak semua anggota himpunan bagian S yang beranggotakan 3 elemen ada 4 himpunan. Misalkan S = (a, b, c, d), maka keempat himpunan bagian tersebut adalah {a, b, c}, {a, b, d}, {a, c, d}, dan {b, c, d}. Atau dengan kata lain, kita memiliki 4 cara dalam memilih 3 dari 4 anggota himpunan S tersebut tanpa memperhatikan urutan sedemikian sehingga 3 anggota tersebut semuanya berbeda.

Akan tetapi, berapa cara yang dapat kita lakukan untuk memilih 3 anggota dari himpunan S tersebut tanpa memperhitungkan urutan jika pengulangan diperbolehkan? Agar mudah untuk membayangkannya, kita dapat menganggap anggota-anggota S tersebut sebagai kategori dari objek-objek yang akan kita pilih. Misalkan, jika kategori-kategorinya dilabeli dengan a, b, c, dan d dan tiga anggota dipilih, ada kemungkinan kita akan memilih 2 anggota dalam kategori a dan 1 anggota dari kategori d, atau tiga anggota yang kita pilih semuanya masuk kategori b, atau tiga anggota yang kita pilih masing-masing masuk dalam kategori a, c, dan d. Secara berturut-turut kita dapat menotasikan pilihan-pilihan tersebut sebagai [a, a, d], [b, b, b], dan [a, c, d]. Perhatikan bahwa, karena urutan diabaikan maka [a, a, d] = [a, d, a] = [d, a, a]. Selanjutnya, perhatikan contoh berikut.

Contoh 1: Kombinasi-r dengan Pengulangan Diperbolehkan

Tulislah semua kombinasi-3 dari {a, b, c, d} sedemikian sehingga pengulangan diperbolehkan.

Pembahasan Karena urutan dari anggota yang dipilih tidak diperhatikan, maka sebaiknya kita menulis kombinasi-3 tersebut dengan urutan menaik, untuk memastikan bahwa tidak adanya kombinasi yang sama ditulis lebih dari satu kali.

[a, a, a], [a, a, b], [a, a, c], [a, a, d]
[a, b, b], [a, b, c], [a, b, d]
[a, c, c], [a, c, d], [a, d, d]
[b, b, b], [b, b, c], [b, b, d]
[b, c, c], [b, c, d], [b, d, d]
[c, c, c], [c, c, d], [c, d, d]
[d, d, d]

Jadi, terdapat 20 kombinasi-3 dari {a, b, c, d} sedemikian sehingga pengulangan diperbolehkan.

Bagaimana cara kita memperoleh bilangan 20 sebagai banyaknya kombinasi yang mungkin, tanpa menuliskan semua kemungkinan kombinasinya? Anggaplah huruf-huruf a, b, c, dan d sebagai kategori-kategori dan bayangkan kita akan mengambil tiga huruf dari kategori-kategori tersebut sedemikian sehingga pengulangan diperbolehkan. Beberapa hasil dari pengambilan kita tersebut dapat digambarkan oleh tabel berikut.

Tabel I

Seperti yang terlihat pada tabel di atas, masing-masing pengambilan 3 huruf dari 4 huruf yang tersedia dapat direpresentasikan dengan tanda garis dan silang. Tiga garis digunakan untuk memisahkan 3 kategori, dan 3 tanda silang digunakan untuk menggambarkan berapa huruf yang diambil dari masing-masing kategori. Masing-masing urutan dari 3 tanda garis dan 3 tanda silang merepresentasikan pengambilan yang berbeda. Sebagai contoh, |××||× merepresentasikan pengambilan: dua dari kategori b dan 1 dari kategori d.

Sehingga banyaknya kombinasi-3 yang dipilih dari {a, b, c, d} sedemikian sehingga pengulangan diperbolehkan sama dengan banyaknya cara menyusun 3 tanda | dengan 3 tanda ×. Padahal banyaknya cara menyusun 3 tanda | dan 3 tanda × sama dengan banyaknya cara memilih 3 nomor urut dari 6 nomor urut yang tersedia sebagai nomor urut dari × atau |. Sehingga, jawabannya adalah

Kombinasi 3 dar 6

yang sama dengan hasil kita sebelumnya dengan mendaftar semua kemungkinannya.

Analisis dari contoh di atas dapat digunakan untuk menyelesaikan masalah yang lebih umum. Untuk mencacah kombinasi-r dengan pengulangan diperbolehkan yang diambil dari himpunan yang memiliki n anggota, anggap anggota-anggota tersebut sebagai kategori. Sehingga, kombinasi-r dengan pengulangan diperbolehkan tersebut dapat direpresentasikan dengan n – 1 tanda garis (untuk memisahkan n kategori) dan r tanda silang (untuk merepresentasikan r anggota yang dipilih). Banyaknya × pada masing-masing kategori merepresentasikan banyaknya anggota yang dipilih dari kategori tersebut.

Tabel II

Banyaknya cara dalam menyusun n – 1 tanda | dan r tanda × sama dengan banyaknya cara mengambil r nomor urut dari tanda × untuk dibentuk ke dalam simbol yang terdiri dari r + (n – 1) tanda | dan ×. Sehingga banyaknya cara tersebut adalah C(r + (n – 1), r).

Teorema Kombinasi dengan Pengulangan
Banyaknya kombinasi-r dengan pengulangan diperbolehkan yang dipilih dari himpunan dengan n anggota adalah,
Teorema Kombinasi dengan Pengulangan
Hasil ini sama dengan banyaknya cara r objek dipilih dari n kategori sedemikian sehingga pengulangan diperbolehkan.

Contoh 2: Menghitung Kemungkinan (i, j, k) dengan 1 ≤ ijk ≤ n

Jika n adalah bilangan bulat positif, berapa banyaknya (i, j, k) yang mungkin apabila 1 ≤ ijkn?

Pembahasan Sembarang tiga bilangan bulat berurutan (i, j, k) dapat direpresentasikan dengan n – 1 tanda garis dan 3 tanda silang, dengan posisi dari tanda silang mengindikasikan bilangan bulat positif mana yang dipilih dalam (i, j, k). Sehingga, berdasarkan teorema di atas, banyaknya urutan tiga bilangan bulat positif yang mungkin adalah,

Contoh 2

Semoga bermanfaat, yos3prens.

Iklan

Tentang Yosep Dwi Kristanto

Tahun 2012 memulai blogging untuk menyediakan sumber belajar matematika online, yang semoga dapat memberikan kontribusi bagi pendidikan di Indonesia. Pengagum pendekatan kontekstual dalam proses pembelajaran.
Pos ini dipublikasikan di Matematika Diskrit, Topik Matematika dan tag , , , . Tandai permalink.

Satu Balasan ke Kombinasi dengan Pengulangan

  1. armin berkata:

    bisa tidak di cantumkan pembuktian untuk permutasi dengan pengulangan?

    Suka

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s