KOMBINATORIAL

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. Contoh:
1. Melempar dadu.
2. Melempar koin uang logam.
3. Memilih 5 orang wakil dari 100 orang.
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     U
n
i
Ai
=1
 =
(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
6
 = 64 ( 2 posisi pertama sudah diisi),
sehingga A = 64.
Jumlah byte yang diakhiri dengan 11 ada : 2
6
 = 64, sehingga B = 64.
Jumlah byte yang berawal dan berakhir dengan 11 ada : 2
4
 = 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:
P(n,r) = n . (n-1) . ( n-2) . . . (n - (r-1)) =
!( )
!
n r
n
−
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:
a. n = 8, r = 8 maka P(8,8) = 8!
b. n = 8, r = 4 maka P(8,4) =
8( )!4
!8
−
 = 8 . 7 . 6 . 5 = 1680 cara.
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:
n = 6, r = 3 maka P(6,3) =
!3
!6
6( )!3
!6
=
−
 = 6.5.4 = 120 cara 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,
C(n,r) =
!
( , )
r
P n r
 =
!( !)
!
r n r
n
−
Contoh:
1. Sekelompok anak terdiri dari 4 anggota. Berapa cara memilih 2 anak dari 4 anak
tersebut.
Jawab:
n = 4, r = 2 maka C(4,2) =
!.2 !2
!4
4(!2 )!2
!4
=
−
= 6 cara
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:
C(n,n1). C(n-n1,n2). C(n-n1-n2,n3) . . . C(n-n1-n2-…-nk,nk) =
! ...! .!
!
1 2 k
n n n
n
Jadi, Banyaknya permutasi dengan perulangan:
! ...! .!
!
1 2 k
n n n
n
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.
Jadi jumlah string yang dapat dibentuk =
1!.4!.4!.2!
11!
= 34650 buah
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:
n1 = 4, n2 = 2, n3 = 2, n = 4 + 2 + 2 = 8
Banyaknya cara membagi buku =
4!.2!.2!
!8
 = 420 cara.
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.

Sumber: http://file.upi.edu/Direktori/FPMIPA/JUR._PEND._MATEMATIKA/KHUSNUL_NOVIANIGSIH/KOMBINATORIAL.pdf