GENERALISASI KOMBINASI

Generalisasi Kombinasi
Generalisasi kombinasi merupakan perluasan dari kombinasi yang membolehkan
pengulangan suatu unsur. Misalnya kita ingin memilih 4 kelereng dari se-
buah kantong yang berisi paling sedikitnya 4 kelereng dari masing-masing
warna yaitu merah, biru dan kuning. Kemungkinan terpilihnya 4 kelereng
tersebut adalah
f4 merahg f3 merah, 1 birug
f2 merah, 2 birug f1 merah, 3 birug
f3 merah, 1 kuningg f2 merah, 2 kuningg
f1 merah, 3 kuningg f4 birug
f3 biru, 1 kuningg f2 biru, 2 kuningg
f1 biru, 3 kuningg f4 kuningg
f2 merah, 1 biru, 1 kuningg f1 merah, 2 biru, 1 kuningg
f1 merah, 1 biru, 2 kuningg
Sehingga terdapat 15 kemungkinan terpilihnya 4 kelereng tersebut.
Permasalahan di atas dapat kita nyatakan sebagai seleksi dari 4+3-1 simbol
yang terdiri dari 4 simbol o sebagai kelereng dan 3 1 simbol k sebagai
pemisah kelereng yang berbeda warna. Selanjutnya kita menentukan posisi
dari simbol-simbol tersebut, yaitu:
8Merah Biru Kuning
oooo k k
ooo k o k
oo k oo k
o k ooo k
ooo k k o
oo k k oo
o k k ooo
k oooo k
k ooo k o
k oo k oo
k o k ooo
k k oooo
oo k o k o
o k oo k o
o k o k oo
Dari seleksi diperoleh 15 kemungkinan pengaturan simbol-simbol tersebut.
Secara umum permasalahan diatas dapat disajikan dalam teorema berikut
ini.
Teorema 3.5
Jika X merupakan sebuah himpunan yang mempunyai t unsur dimana pen-
gulangan diperbolehkan, maka banyaknya seleksi k unsur tak terurut dari X
adalah
C(k + t 1; t 1) = C(k + t 1; k)
Bukti.
Misalkan X = fx1; x2; :::; xtg. Asumsikan bahwa terdapat k + t 1 slot yang
akan diisi oleh k +t1 simbol yang terdiri dari k simbol o dan t1 simbol k.
Penempatan simbol-simbol pada slot tertentu merupakan representasi dari
proses seleksi. Bilangan n1 dari simbol o hingga simbol k yang pertama
merepresentasikan seleksi dari n1x1; bilangan n2 dari simbol o dari simbol
k yang pertama hingga simbol k yang kedua merepresentasikan seleksi dari
n2x2; dan seterusnya sampai seleksi dari ntxt
Karena terdapat C(k + t .
1; t 1) cara untuk menentukan posisi simbol k, maka juga terdapat C(k +
t 1; t 1) seleksi. Hal ini juga sama dengan C(k + t 1; k) cara untuk
menentukan posisi simbol o. Sehingga terdapat
C(k + t 1; t 1) = C(k + t 1; k)
seleksi k-unsur tak terurut dari X dimana pengulangan diperbolehkan. 2
9Contoh 3.11
Gunakan Teorema 3.5 untuk menentukan banyaknya cara memilih 4 kelereng
dari sebuah kantong yang berisi paling sedikitnya 4 kelereng dari masing-
masing warna yaitu merah, biru dan kuning.
Karena ada 3 warna kelereng dan 4 kelereng akan dipilih, maka t = 3 dan
k = 4. Sehingga banyaknya cara pemilihan 4 kelereng adalah:
C(4 + 3 1; 3 1) =
6!
(6 2)!:2!
=
6:5
2
= 15
Contoh 3.12
Berapa banyak solusi bilangan bulat tak negatif dari persamaan
x1 + x2 = 10
Setiap solusi dari persamaan tersebut ekuivalen dengan pemilihan 10 butir
xi dari jenis i, i = 1; 2. Sehingga banyaknya seleksi adalah
C(10 + 2 1; 2 1) = C(11; 1) = 11
Latihan
3.1. Berapa banyak untai yang bisa dibentuk dengan mengurutkan huruf
ABCDE jika :
a. mengandung subuntai ACE.
b. mengandung huruf ACE dalam sembarang urutan.
c. A muncul sebelum D (misalnya BCADE, BCAED).
d. tidak mengandung subuntai AB atau CD.
3.2. Dalam berapa banyak cara 5 mahasiswa dan 7 mahasiswi dapat berbaris
jika tidak boleh ada 2 mahasiswa yang berdekatan?
3.3. Dalam berapa banyak cara 5 mahasiswa dan 7 mahasiswi dapat duduk
di meja mundar jika tidak boleh ada 2 mahasiswa yang berdekatan?
3.4. Sebuah kelompok terdiri dari 6 mahasiswa dan 7 mahasiswi. Ada be-
rapa cara kita bisa memilih panitia yang terdiri dari:
a. 3 mahasiswa dan 4 mahasiswi.
b. 4 orang paling sedikitnya 1 mahasiswi.
10c. 4 orang paling sedikitnya 1 mahasiswa.
d. 4 orang dimana jumlah mahasiswa sama dengan mahasiswi.
3.5. Tentukan banyaknya kemungkinan lima kartu (tak terurut) yang dipilih
dari 52 kartu jika:
a. mengandung 4 As.
b. mengandung 4 kartu dari nilai yang sama.
c. mengandung semua spade.
d. mengandung kartu dari semua rupa.
3.6. Dalam berapa banyak cara 10 buku yang berbeda dapat dibagikan
pada 3 mahasiswa jika mahasiswa pertama mendapatkan 5 buku, ma-
hasiswa kedua mendapatkan 3 buku dan mahasiswa ketiga mendap-
atkan 2 buku?
3.7. Misalkan terdapat kumpulan bola yang berwarna merah, biru dan hijau
yang masing-masing mengandung paling sedikitnya 10 bola.
a. berapa banyak cara 10 bola bisa dipilih?
b. berapa banyak cara 10 bola bisa dipilih jika paling sedikit 1 bola
merah harus terpilih?
c. berapa banyak cara 10 bola bisa dipilih jika paling sedikit 1 bola
merah, paling sedikit 2 bola biru dan paling sedikit 3 bola hijau
harus terpilih?
d. berapa banyak cara 10 bola bisa dipilih jika tepat 1 bola merah
dan paling sedikit 1 bola biru harus terpilih?
3.8. Carilah banyaknya solusi bilangan bulat dari persamaan
x1 + x2 + x3 = 15
jika:
a. x1  0, x2  0 dan x3  0.
b. x1  1, x2  1 dan x3  1.
c. x1 = 1, x2  0 dan x3  0.