KOMBINATORIAL
Kombinatorial adalah cabang matematika yang mempelajari pengaturan objek – objek.
Solusi yang ingin kita peroleh dari kombinatorial ini adalah jumlah cara pengaturan objek
– objek didalam kumpulanya. Kombinatorial didasarkan pada hasil yang diperoleh dari
suatu percobaan (experiment) atau kejadian (event). Percobaan adalah proses fisis
yang hasilnya dapat diamati.
KAIDAH DASAR PERHITUNGAN
1. Kaidah Dasar Penjumlahan (Rule of Sum) / ROS
Andaikan terdapat n himpunan Ai, I = 1,2,3 . . . , n. Andaikan juga cacah banyaknya
anggota himpunan Ai adalah ni dan Ai ∩ Aj = ∅, maka banyaknya anggota himpuan
A1 atau A2 atau . . . atau An adalah (n1 + n2 + . . . + nn). Dengan kata lain
(n1 + n2 + . . . + nn)
Contoh:
Dalam Perpustakaan terdapat 10 buku Matematika, 25 buku Statistik dan 5 buku
social. Berapa cara yang dapat dilakukan untuk mengambil 1 buku.
Jawab:
Banyaknya cara mengambil 1 buku Matematika ada 10 cara.
Banyaknya cara mengambil 1 buku Statistik ada 25 cara.
Banyaknya cara mengambil 1 buku Sosial ada 5 cara.
Jadi, banyaknya cara untuk mengambil 1 buku (sembarang) ada:
10 + 25 + 5 = 40 cara.
2. Kaidah Dasar Perkalian (Rule of Product) / ROP
Andaikan suatu prosedur dapat diselesaikan dengan k tahap.
Tahap 1 dapat diselesaikan dengan n1 cara.
Tahap 2 dapat diselesaikan dengan n2 cara.
.
.
.
Tahap k dapat diselesaikan dengan nk cara.
Maka prosedur tersebut dapat diselesaikan dengan : n1 . n2 . . . nk cara
Contoh: Pada soal no.1
Berapa banyaknya cara untuk mengambil 3 buah buku masing – masing 1 buku
Matematika, 1 buku Statistik dan 1 buku social.
Jawab:
Prosedur untuk mengambil 3 buah buku yang berbeda dapat diselesaikan dengan 3
tahap.
Tahap 1: Mengambil 1 buku Matematika dapat dilakukan dengan 10 cara.
Tahap 2 : Mengambil 1 buku Statistik dapat dilakukan dengan 25 cara.
Tahap 3 : mengambil 1 buku Sosial dapat dilakukan dengan 5 cara.
Dengan prinsip ROP, banyaknya cara utnuk mengambil 3 buah buku yang berbeda
ada: 10.25.5 = 1250 cara.
Prinsip ROP menyatakan bahwa suatu percobaan dilakukan secara bersamaan
sedangkan ROS percobaan dilakukan tidak bersamaan.
Contoh soal:
1. Sekelompok mahasiswa terdiri dari 4 orang pria dan 3 orang wanita. Berapa cara
memilih 1 orang yang mewakili kelompok tersebut (tidak perduli pria atau wanita).
Jawab:
Ada 4 cara untuk memilih pria dan 3 cara untuk memilih satu wakil wanita, maka
banyaknya cara untuk memilih 1 orang wakil adalah 4 + 3 = 7 cara.
2. Suatu seri dari mikrokomputer terdiri dari 5 karakter masing – masing 2 huruf yang
diikuti oleh angka (huruf besar dan kecil tidak dibedakan). Berapa cara nomor seri
yang dapat dibuat.
Jawab:
Banyaknya huruf ada 26 dan banyaknya angka ada 10. Kemungkinan no seri yang
dapat dibuat ada:
26 . 26 . 10 . 10 . 10 = 676000 cara
3. Berapa banyak bilangan 4 digit yang tidak mengandung angka yang berulang
jawab:
banyaknya angka ada 10. Banyaknya bilangan 4 digit yang dapat dibentuk jika tidak
ada angka yang diulang ada: 10 . 9 . 8 . 7 = 4536
4. Berapa banyak bilangan ganjil antara 1000 sampai 9999 yang semua digitnya
berbeda.
Jawab:
Posisi satuan : ada 5 kemungkinan
Posisi ribuan : ada 8 kemungkinan
Posisi ratusan : ada 8 kemungkinan
Posisi puluhan : ada 7 kemungkinan
Jadi, banyaknya bilangan ganjil antara 1000 – 9999 ada: 5 . 8 . 8 . 7 = 2240 buah
PRINSIP INKLUSI – EKSLUSI
Contoh:
1. Berapa banyak 8 bit string yang dimulai dari 11 atau berakhir 11
Jawab:
Misal A = Himpunan byte yang dimulai 11
B = Himpunan byte yang diakhiri 11
C = Himpunan byte yang dimulai dengan 11 dan diakhiri 11
Jumlah byte yang dimulai dengan 11 ada 2⁶ = 64 ( 2 posisi pertama sudah diisi),
sehingga│A│= 64.
Jumlah byte yang diakhiri dengan 11 ada :2⁶ = 64, sehingga │B│= 64.
Jumlah byte yang berawal dan berakhir dengan 11 ada : 2⁴ = 16,
sehingga |A ∩B |= 16. dengan prinsip inklusi – Ekslusi maka jumlah byte yang
dimulai dengan 11 atau diakhiri 11 ada:
丨A ∪B丨=丨A丨+丨B丨-丨A ∩B丨= 64 + 64 – 16 = 112 buah.
2. Seorang professor mempunyai 25 mahasiswa Kalkulus, 31 mahasiswa stastistik dan
13 mahasiswa yang mengikuti keduanya. Berapa jumlah mahasiswa professor.
Jawab:
Misal A = himpunan mahasiswa kalkulus
B = himpunan mahasiswa Statistik
丨A丨= 25,丨B 丨= 31,丨A ∩B丨= 13 sehingga total mahasiswa ada:
丨A ∪B丨=丨A丨+丨B丨-丨A ∩B丨= 25 + 31 – 13 = 43
PERMUTASI
Definisi 1:
Untuk n≥0, n factorial yang ditulis dengan n! didefinisikan sebagai:
n! = n . (n-1) . (n-2) . . . 3. 2. 1
Definisi 2:
Andaikan terdapat n sembarang objek. Akan diadakan pengaturan r objek dengan 1 ≤
r ≤ n. Banyaknya permutasi ditulis dengan: nPr atau P(n,r) didefinisikan sebagaikan:
Bentuk umum: untuk n = r, P(n,n) = n!
Dalam permutasi hal yang perlu diperhatikan:
- Pengaturan
- Urutan
Contoh:
1. Perhatikan kata “KOMPUTER”, akan diatur huruf – huruf dalam kata tersebut.
a. Berapa banyak pengaturan huruf jika semua huruf pada kata tersebut digunakan.
b. Berapa banyak pengaturan jika hanya diambil 4 huruf.
Jawab:
2. Tiga buah ujian dilakukan dalam satu periode 6 hari. Berapa banyak pengaturan
jadwal yang dapat dilakukan sehingga tidak ada 2 ujian atau lebih yang dilakukan
pada hari yang sama.
Jawab:
KOMBINASI
Andaikan terdapat n objek berbeda, akan dipilih r objek dengan 1 ≤ r ≤ n (tampa
memperhatikan urutan). Banyaknya kombinasi disajikan dengan nCr atau C(n,r)
Andaikan urutan diperhatikan, banyaknya pengaturan r objek dari n objek adalah P(n,r).
Dari r objek,urutan tidak diperhatikan, banyaknya pengaturan adalah P(r,r) = r!
Jadi,
Contoh:
1. Sekelompok anak terdiri dari 4 anggota. Berapa cara memilih 2 anak dari 4 anak
tersebut.
Jawab:
2. string biner panjangnya 32 bit disusun oleh digit 1 atau 0. berapa banyak string biner
yang tepat berisi 7 buah bit 1
Jawab:
Kasus diatas analog dengan terdapat 7 bola yang akan dimasukan ke 32 kotak.
Banyaknya string biner yang terbentuk adalah C(32,7).
3. Sekelompok anak terdiri dari 6 anak laki – laki dan 5 anak perempuan . Akan dipilih
3 orang anak dengan ketentuan 2 anak laki – laki dan 1 anak perempuan. Berapa
banyak cara yang dapat dilakukan untuk memilih 3 orang tersebut.
Jawab:
Terdapat 2 prosedur pemilihan:
- Pemilihan 2 anak laki – laki
- Pemilihan 1 anak perempuan
Banyaknya cara memilih 2 anak laki-laki dari 6 anak ada: C(6,2) cara.
Banyaknya cara memilih 1 anak perempuan dari 5 anak ada: C(5,1) cara.
Jadi, banyaknya cara memilih 2 anak laki – laki dan 1 anak perempuan:
C(6,2).C(5,1) = 15 . 5 = 75 cara
4. Tiga buah apartemen A, B, C disewakan ke mahasiswa. Tiap apartemen dapat
menampung 3 atau 4 orang . Berapa banyak cara menyewakan apartemen kepada
10 orang mahasiswa.
Jawab:
Ada 3 kemungkinan:
- Apartemen A untuk 4 orang, apartemen B,C untuk 3 orang.
Banyaknya cara: C(10,4). C(6,3) . C(3,3)
- Apartemen A untuk 3 orang, B untuk 4 orang dan C untuk 3 orang
Banyaknya cara: C(10,3) . C(7,4) . C(3,3)
- Apartemen A,B untuk 3 orang dan C utnuk 4 orang
Banyaknya cara : C(10,3) . C(7,3) . C(3,3)
Total seluruh cara: C(10,4). C(6,3) . C(3,3) + C(10,3) . C(7,4) . C(3,3) +C(10,3) .
C(7,3) .C(3,3)
5. Berapa banyak cara 8 orang disusun dalam suatu lingkaran.
Jawab:
Untuk menyusun 8 orang dalam lingkaran, maka 1 orang harus tetap ditempatnya,
sedang yang lain berpindah, sehingga banyaknya cara ada: 7!
PERLUASAN PERMUTASI DAN KOMBINASI
Andaikan terdapat n objek dengan:
n1 objek pertama
n2 objek kedua
.
.
.
nk objek ke-k
dengan n = n1 + n2 + . . . + nk,maka banyaknya permutasi dari n objek tersebut adalah:
Objek pertama diatur dengan : C(n,n1) cara
Objek kedua diatur dengan : C(n-n1,n2) cara
Objek ketiga diatur dengan : C(n-n1-n2,n3) cara
.
.
.
Objek ke-k diatur dengan : C(n-n1-n2-…-nk,nk)
Dengan prinsip ROP, pengaturan n objek dapat dilakukan dengan:
Contoh:
1. Berapa banyak string yang dapat dibentuk dari kata “MISSISSIPPI”
Jawab:
Banyaknya huruf M = 1, huruf I = 4, huruf S = 4, hurup P = 2 sehingga
n = 1 + 4 + 4 + 2 = 11.
2. Berapa banyak cara membagi 8 buah buku yang berbeda kepada 3 orang
mahasiswa jika masing-masing Billy mendapat 4 buku, Andy dan Toni mendapat 2
buku.
Jawab:
KOMBINASI DENGAN PERULANGAN
Misal terdapat r buah bola yang warnanya sama dan n buah kotak (r > n).
(i) jika masing –masing kotak hanya boleh diisi paling banyak satu kotak maka
banyaknya cara memasukan bola ke dalam kotak ada C(n,r).
(ii) Jika masing – masing kotak tidak ada batasan jumlah bola, maka jumlah cara
memasukan bola tersebut ada C(n + r – 1 , r ) atau C(n + r – 1 , n – 1).
Contoh:
1. Persamaan: x1 + x2 + x3 + x4 = 12 dengan xi bilangan bulat nonnegatif. Berapa
jumlah kemungkinan solusinya.
Jawab:
Kasus diatas analog dengan 12 bola kedalam 4 kotak, maka banyaknya cara ada:
C(4 + 12 – 1, 12) = C(15,12) = 455 buah.
2. Tiga buah dadu dilempar. Berapa banyak hasil yang berbeda yang mungkin.
Jawab:
n = 3, r = 6 sehingga banyaknya hasil yang mungkin ada:
C(3 + 6 – 1 , 6) = C(8,6) = 56 buah.
DAFTAR PUSTAKA
Munir, R. (2014). Kombinatorial. Bandung:
Program Studi Teknik Informatika ITB.
Tidak ada komentar:
Posting Komentar