Kombinatorik

BAB III KOMBINATORIK

Persoalan kombinatorik bukan merupakan persoalan yang baru dalam kehidupan nyata.   Banyak   persoalan   kombinatorik   yang   sederhana   telah   diselesaiakan   dalam masyarakat. Misalkan, saat pemilihan pemain untuk tim sepak bola yang terdiri dari 11 pemain.  Apabila  ada  20  orang  ingin  membentuk  suatu  tim  sepak  bola,  ada  berapa kemungkinan  komposisi  pemain  yang  dapat  terbentuk?  Contoh  lain  adalah  dalam menentukan sebuah password panjangnya 6 sampai 8 karakter. Karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan password yang dapat dibuat ?                       Tetapi selain itu para ilmuwan pada berbagai bidang juga kerap menemukan sejumlah persoalan yang  harus  diselesaikan.  Pada  Bab  ini,  kita  akan  membahas  tentang  kombinatorik, permutasi dan apa yang terkait dengan itu.  Kombinatorik merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.

3.1  Prinsip Dasar Menghitung

Dua  prinsip  dasar  yang  digunakan  dalam menghitung  (counting)  yaitu   aturan pejumlahan dan aturan perkalian.

Prinsip Penjumlahan

Jika suatu himpunan A terbagi kedalam himpunan bagian A1, A2, …, An, maka jumlah unsur pada himpunan A akan sama dengan jumlah semua unsur yang ada pada setiap himpunan bagian A1, A2, …, An.

Secara tidak langsung, pada prinsip penjumlahan, setiap himpunan bagian A1, A2, …, An tidak saling tumpang tindih (saling lepas). Untuk himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan  ini harus diselesaikan dengan prinsip inklusi- eksklusi yang akan dibahas kemudian.

Contoh 1 :

Seorang guru SD di daerah, mengajar murid kelas 4, kelas 5 dan kelas 6. Jika jumlah murid kelas 4 adalah 25 orang dan                                        jumlah murid kelas 5 adalah 27 orang serta jumlah murid kelas 6 adalah 20 orang, maka jumlah murid yang diajar guru tersebut adalah 25 + 27 + 20 = 72 murid.

Contoh 2 :

Seorang    mahasiswa ingin membeli sebuah motor. Ia dihadapkan untuk memilih pada satu jenis  dari  tiga  merk  motor,  Honda 3  pilihan,  Suzuki  2  pilihan,  dan Yamaha 2 pilihan. Dengan demikian, mahasiswa tersebut mempunyai  mempunyai pilihan sebanyak 3 + 2 + 2 = 7 pilihan.

Adiwijaya

Sekolah Tinggi Teknologi Telkom

Prinsip  Perkalian

Misalkan  sebuah  prosedur  dapat  dipecah  dalam  dua  penugasan.  Penugasan pertama dapat dilakukan dalam  n1 cara, dan tugas kedua dapat dilakukan dalam n2  cara setelah tugas pertama dilakukan. Dengan demikian, dalam mengerjakan prosedur tersebut ada (n1 x n2) cara.

Secara tidak langsung, pada prinsip perkalian, bisa terjadi  saling tumpang tindih (tidak saling lepas).

Contoh  1 :

Berapa  banyak  string dengan panjang tujuh yang mungkin terbentuk dari dua bit

(0 dan 1)

Jawab  :

Setiap suku pada string tersebut mempunyai dua cara pemilihan, yaitu  0 atau 1. Dengan demikia, pada pemilihan string dengan panjang tujuah dapat dilakukan dengan :

2 x 2 x 2 x 2 x 2 x 2 x 2  = 27

= 128 cara.

Contoh 2 :

Seorang guru SD di daerah, mengajar murid kelas 4, kelas 5 dan kelas 6. Misalkan, jumlah murid kelas 4 adalah 25 orang dan  jumlah murid kelas 5 adalah 27 orang serta jumlah murid kelas 6 adalah 20 orang. Jika guru tersebut ingin memilih tiga orang murid dari anak didiknya, dimana seorang murid dari setiap kelas, maka guru tersebut mempunyai 25 x 27 x 20 = 13.500 cara dalam memilih susunan tiga murid tersebut.

Contoh 3 :

Berapa banyak bilangan ganjil antara 1000 dan 9999 (termasuk 1000 dan 9999 itu sendiri) dimana

(a)   semua angkanya berbeda

(b)  boleh ada angka yang berulang.

Jawab :

(a) posisi satuan:   5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9);

posisi ribuan:   8 kemungkinan angka (1 sampai 9 kecuali angka yang telah dipilih)

posisi ratusan:  8 kemungkinan angka posisi puluhan: 7 kemungkinan angka

maka banyak bilangan ganjil seluruhnya adalah  (5)(8)(8)(7) = 2240 buah.

(b)  posisi satuan:   5 kemungkinan angka (yaitu 1, 3, 5, 7 dan 9);

posisi ribuan:   9 kemungkinan angka (1 sampai 9) posisi ratusan:  10 kemungkinan angka (0 sampai 9) posisi puluhan: 10 kemungkinan angka (0 sampai 9)

maka banyak bilangan ganjil seluruhnya adalah  (5)(9)(10)(10) = 4500

Contoh 5 :

Password  suatu  login  pada  sistem  komputer     panjangnya  lima  sampai  tujuh karakter.  Tiap  karakter  boleh  berupa  huruf (huruf besar dan huruf kecil tidak dibedakan) atau angka. Berapa banyak password  yang dapat dibuat untuk suatu login ?

Jawab :

Banyaknya   huruf  alfabet  adalah 26 (A –  Z) dan banyak angka adalah 10 (0 – 9), jadi seluruhnya 36 karakter.

Untuk  password    dengan  panjang  5  karakter,  jumlah  kemungkinan  password

adalah

(36)(36)(36)(36)(36) = 365  = 60.466.176

untuk password dengan panjang 6 karakter, jumlah kemungkinan password  adalah

(36)(36)(36)(36)(36)(36)(36) = 366 = 2.176.782.336

dan untuk  password dengan  panjang  8  karakter,  jumlah  kemungkinan

password adalah

(36)(36)(36)(36)(36)(36)(36)(36) = 367 = 78.364.164.096

Jumlah seluruh password yang mungkin  adalah

60.466.176 + 2.176.782.336 + 78.364.164.096 = 80.601.412.608 buah. Jadi, untuk suatu login akan mempunyai  80.601.412.608 buah kemungkinan

password.

Prinsip Inklusi-Eksklusi

Ketika   dua   proses   dikerjakan   dalam   waktu   yang   sama,   kita   tidak   bisa menggunakan prinsip penjumlahan untuk menghitung jumlah cara untuk memilih salah satu dari dua proses tersebut. Untuk menghitung proses tersebut, kita harus mengenal prinsip inklusi-eksklusi.

Contoh :

Berapa banyak byte yang dapat disusun oleh 8-bit,  yang dimulai dengan ‘11’ atau berakhir dengan ‘00’?

Jawab :

Misalkan,

A adalah  himpunan byte yang dimulai dengan ‘11’,

B adalah  himpunan byte yang diakhiri dengan ‘00’,

A ∩ B adalah  himpunan byte yang berawal dengan ‘11’ dan berakhir dengan ‘00’, dan

A ∪ B adalah  himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘00’

Maka jumlah kemungkinan byte yang dapat disusun pada himpunan A adalah

(1)(1)(2)(2)(2)(2)(2)(2) =  26

Tulis,  ⏐A⏐ = 26

= 64

Sementara itu, jumlah kemungkinan byte yang dapat disusun pada himpunan B

adalah  (2)(2)(2)(2)(2)(2)(1)(1) =  26

Jadi,  ⏐B⏐ = 26 = 64,

Dengan  cara  yang  sama,     jumlah  kemungkinan  byte  yang  dapat  disusun  pada himpunan A ∩ B   adalah (1)(1)(2)(2)(2)(2)(1)(1) =  24

Sehingga  ⏐A ∩ B⏐ = 24 = 16. maka

⏐A ∪ B⏐ = ⏐A⏐ + ⏐B⏐ – ⏐A ∩ B⏐

= 64 + 64 – 16

= 112.

Dengan demikian,    jumlah byte yang dapat disusun oleh 8-bit,    yang dimulai dengan ‘11’ atau berakhir dengan ‘00’  adalah  112 buah.

3.2  Permutasi dan Kombinasi

Permutasi

Suatu permutasi merupakan susunan yang mungkin dibuat dengan memperhatikan urutan. Dengan kata lain, permutasi merupakan bentuk khusus aplikasi prinsip perkalian. Misalkan diberikan suatu himpunan A dengan jumlah anggota adalah n, maka susunan terurut yang terdiri dari r buah anggota dinamakan permutasi-r   dari A, ditulis P(n, r). Agar lebih jelas dalam perhitungannya, perhatikan penjelasan berikut ini :

•                  Jika r > n, jelas bahwa  P(n, r)  = 0, karena tak mungkin menyusun r anggota dari

A yang hanya terdiri dari n buah anggota dimana n < r.

•                  Jika r ≤ n,

Dari n  anggota A maka urutan pertama yang dipilih dari n objek adalah dengan n

cara.  Urutan kedua dipilih dari n – 1 objek, adalah dengan n – 1  cara, karena satu anggota telah terpilih. Urutan ketiga dipilih dari n – 2 objek, adalah dengan n – 2 cara, karena dua anggota telah terpilih. Hal ini dilakukan terus menerus sehingga urutan terakhir dipilih dari n – r + 1 objek yang tersisa. Menurut kaidah perkalian, pemilihan objek dalam susunan r buah objek dari n buah objek dapat dilakukan dengan :

n(n – 1) (n – 2) … (n – r + 1) cara

Dengan demikian, permutasi r objek dari n buah objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤  n, pada setiap kemungkinan penyusunan r buah objek tidak ada urutan objek yang sama, yaitu :

P(n, r) = n(n – 1) (n – 2) … (n – r + 1)

n!

=

(n − r)!

Contoh 1 :

Misalkan S = {p, q, r}. Berapa cara yang mungkin dalam penyusunan dua huruf pada S sehingga tidak ada urutan yang sama ?

Jawab :

Susunan dua huruf yang mungkin adalah :

pq, pr, qr, qp, rp, rq

Jadi penyusunan tersebut dapat dilakukan dengan enam buah cara. Dalam penyusunan ini, dapat menggunakan definisi permutasi, yaitu :

P(3, 2) =

3 !

(3 − 2) !

= 3 . 2.1

1

= 6

Dengan menggunakan definisi permutasi, penyusunan tersebut dapat dilakukan dengan enam buah cara.

Contoh 2 :

Misalkan kita mempunyai lima buah bola dengan warna yang berbeda satu sama lain dan 3 buah kotak. Kita akan memasukan bola tersebut kedalam kotak. Masing- masing kotak hanya boleh diisi 1 buah bola. Berapa jumlah urutan bola  dengan warna berbeda yang mungkin dibuat dari penempatan bola ke dalam kotak-kotak tersebut?

Jawab :

kotak 1 dapat diisi oleh salah satu dari 5 bola  (ada 5 pilihan); kotak 2 dapat diisi oleh salah satu dari 4 bola  (ada 4 pilihan); kotak 3 dapat diisi oleh salah satu dari 3 bola  (ada 3 pilihan). Jumlah urutan berbeda dari penempatan bola = (5)(4)(3)

= 60

Jika menggunakan definisi permutasi maka :

P(5, 3) =

5 !

(5 − 3) !

= 5.4.3 . 2.1

2.1

Kombinasi

= 60

Misalkan r  merupakan unsur bilangan bulat tak negatif. Yang dimaksud dengan kombinasi r                       dari suatu himpunan B yang terdiri dari n anggota (objek) yang berbeda adalah jumlah himpunan bagian dari B yang memiliki anggota r buah objek. Interpretasi yang lain tentang kombinasi adalah menyusun (memilih) objek sejumlah r dari n buah objek yang ada.

Contoh 1 :

Misalkan A = {p, q, r }, tentukan semua himpunan bagian dari A yang memiliki kardinalitas dua.

Jawab :

Himpunan bagian tersebut antara lain : {p, q},  {p, r}, dan {q, r}. Jadi kita mempunyai empat kombinasi :

pq,  pr, dan  qr

Pada  himpunan,  urutan  unsur  pada  himpunan  tidak  diperhatikan.  Dengan  demikian, kombinasi 2 dari himpunan A (penyusunan dua huruf tanpa memperhatikan urutan) adalah

3, yaitu  pq,  pr, dan  qr.  Ini berbeda, pada saat kita mendefinisikan permutasi (urutan diperhatikan),  penyusunan tersebut dapat dilakukan dengan enam buah cara, yaitu pq, pr, qr, qp, rp,dan  rq.

Contoh 2 :

Misalkan ada 2 buah bola yang berwarna sama dan 3 buah kotak. Bola akan dimasukan ke dalam kotak sehingga setiap kotak hanya boleh berisi paling banyak

1 bola. Berapa jumlah cara memasukkan bola ke dalam kotak tersebut ?

Jawab :

Misalkan ketiga kotak tersebut ditaruh memanjang, maka ada 3 cara memasukan dua bola tersebut kedalam kotak, yaitu :

Cara I  : kedua bola masing-masing ditaruh pada dua kotak pertama (kotak I dan kotak II).

Cara II : kedua bola masing-masing ditaruh pada dua kotak yang paling ujung

(kotak I  dan  kotak III) .

Cara III: kedua bola masing-masing ditaruh pada dua kotak terakhir (kotak II  dan

Kotak III) .

Secara umum, jumlah cara memasukkan r buah bola yang berwarna sama ke dalam n buah kotak adalah :

n(n − 1)(n − 2)...(n − (r − 1)) =

r!

n!

r!(n − r )!

⎛ n ⎞

Ini merupakan rumus umum kombinasi yang dinotasikan oleh  C(n, r) atau ⎜  ⎟

⎝ r ⎠

Diketahui  ada  n  buah  bola  yang  tidak  seluruhnya  berbeda  warna  (jadi,  ada beberapa bola yang warnanya sama) akan dimasukan kedalam n buah kotak.   Misalnya komposisi bola tersebut adalah :

n1 bola diantaranya berwarna 1, n2 bola diantaranya berwarna 2, M

nk bola diantaranya berwarna k, jadi n1 + n2 + … + nk = n.

Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimum satu buah bola) ?

Jika   n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n

buah bola ke dalam n buah kotak adalah

P(n, n) = n!.

Dari pengaturan n buah bola itu,

ada n1! cara memasukkan bola berwarna 1

ada n2! cara memasukkan bola berwarna 2

M

ada nk! cara memasukkan bola berwarna k

Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …, nk

bola berwarna k adalah:

P(n; n1

, n2

,..., nk ) =

P(n, n)    =

n1!n2 !...nk !

n!

n1!n2 !...nk !

Cara lain:

Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1. Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.

Ada C(n – n1 – n3, n3) cara untuk menempatkan n3 buah bola berwarna 3.

M

Ada C(n – n1  – n2  – … –  nk-1, nk  ) cara untuk menempatkan nk  buah bola berwarna k.

Jumlah cara pengaturan seluruh bola kedalam kotak adalah:

C(n; n1, n2, …, nk) = C(n, n1) C(n – n1, n2) C(n – n1 – n2 , n3)

… C(n – n1 – n2 – … –  nk-1, nk)

=         n!

n1!(n − n1 )!

(n − n1 )!

n2 !(n − n1 − n2 )!

(n − n1 − n2 )!

n3!(n − n1 − n2 − nk )!

…         (n − n1 − n2 − ... − nk −1 )!

nk !(n − n1 − n2 − ... − nk −1 − nk )!

=            n!

Kesimpulan:

n1!n2!n3!...nk !

P(n; n1

, n2

,..., nk

) = C (n; n1

, n2

,..., nk ) =

n!

n1!n2 !...nk !

Kombinasi Dengan Pengulangan

Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak. (i)   Masing-masing kotak hanya boleh diisi paling banyak satu buah bola.

Jumlah cara memasukkan bola: C(n, r).

(ii)   Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola)

Maka Jumlah cara memasukkan bola:  C(n + r – 1, r).

C(n + r – 1, r) = C(n + r –1, n – 1).

Contoh :

20 buah apel dan 15 buah jeruk dibagikan kepada 5 orang anak, tiap anak boleh mendapat lebih dari 1 buah apel atau jeruk, atau tidak sama sekali. Berapa jumlah cara pembagian yang dapat dilakukan?

Jawab :

n = 5, r1 = 20 (apel) dan r2 = 15 (jeruk)

Membagi 20 apel kepada 5 anak: C(5 + 20 – 1, 20) cara,

Membagi 15 jeruk kepada 5 anak: C(5 + 15 – 1, 15) cara. Jumlah cara pembagian kedua buah itu adalah

C(5 + 20 – 1, 20) × C(5 + 15 – 1, 15) = C(24, 20) × C(19, 15)

Koefisien Binomial

Misalkan n merupakan bilangan bulat positif,  dengan teorema binomial, perpangkatan berbentuk  (x + y)n  dapat dijabarkan dalam bentuk segitiga Pascal berikut ini :

(x + y)0 = 1						1
(x + y)1 = x + y					1		1
(x + y)2 = x2 + 2xy + y2				1		2		1
(x + y)3 = x3 + 3x2y + 3xy2 + y3			1		3		3		1
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4		1		4		6		4		1
(x + y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5	1		5		10		10		5		1
Secara umum, diperoleh rumus sebagai berikut :

(x + y)n = C(n, 0) xn + C(n, 1) xn-1 y1 + … + C(n, k) xn-k yk + … +  C(n, n) yn

n

= ∑ C(n, k ) xn-k yk

k =0

Bilangan C(n, k) merupakan koefisien untuk xn-kyk dinamakan  koefisien binomial.

Contoh :

Jabarkan (2x + y)3.

Jawab :

Misalkan a = 2x dan b = y,

(a + b)3   = C(3, 0) a3 + C(3, 1) a2b1 + C(3, 2) a1b2 + C(3, 3) b3

= 1 (2x)3 + 3 (2x)2 (y) + 3 (2x) (y)2 + 1 (y)3

= 8 x3 + 12x2 y  + 6x y2 – y3

Contoh :

Jabarkan (2x – 3)3.

Jawab :

Misalkan a = 2x dan b = –3,

(a + b)3   = C(3, 0) a3 + C(3, 1) a2b1 + C(3, 2) a1b2 + C(3, 3) b3

= 1 (2x)3 + 3 (2x)2 (–3) + 3 (2x) (–3)2 + 1 (–3)3

= 8x3 – 36x2 + 54x – 27

Contoh :

Tentukan suku kelima dari penjabaran perpangkatan (x – y)5.

Jawab :

(x – y)5 = (x + (–y))5.

Suku kelima  dari hasil penjabaran adalah:

C(5, 4) x 5 – 4 (–y)4 = –10 x y4.

Latihan :

1.   Tentukan nilai :

a.   P(6, 3)

b.   C(5, 1)

2.   Berapa kali akan muncul string yang terdiri dari unsur pada abcdefgh yang memuat string abc pada string tersebut.

3.   Berapa  banyak  string dengan panjang sepuluh yang mungkin terbentuk dari dua bit (0 dan 1), yang memuat angka satu tepat tujuh buah.

4.   Dalam  suatu  pacuan  kuda  dengan  12  peserta  (diasumsikan  semuanya  dapat mencapai  finish),  Berapa  jumlah  kemungkinan   susunan   pemenang   (pertama, kedua, dan ketiga)  dalam pacuan tersebut.

5.   Pada toko ‘duny donut’ menyediakan empat jenis donat dengan rasa yang berbeda (stok  masing-masing  rasa  10  buah).                                          Berapa  jumlah  cara  pengambilan,  jika seseorang membeli donat tersebut enam buah.

6.   Dengan menggunakan teorema binomial, tentukan :

a.   koefisien x5y8 dalam (x + y)13 b.   koefisien x7   dalam (1 + x)11 c.   koefisien x9 dalam (1 – x)19