Kombinatorik

A. DASAR PERHITUNGAN

Dalam kehidupan sehari-hari, kita sering dihadapkan dengan masalah perhitungan. Sebagai contoh, sebuah Warung Tegal menyediakan menu yang terdiri dari 4 jenis makanan, yaitu Nasi Rawon (R), Nasi Soto (S), Nasi Pecel (P) dan Bakso (B) serta 3 jenis minuman, yaitu Es Jeruk (J), Es Teh (T) dan

Es Degan (D).

Masalahnya, berapa banyak macam hidangan yang berbeda jika dipilih dari satu jenis makanan dan satu jenis minuman? Masalah di atas merupakan salah satu contoh masalah diskrit yang biasa dipecahkan dengan cara mendata semua kemungkinan hidangan yang berbeda yang terdiri dari satu jenis makanan dan satu jenis minuman, yaitu: RJ,RT,RD, SJ, ST, SD, PJ, PT, PD,BJ,BT,BD

Sehingga terdapat 12 macam hidangan yang berbeda. Total jenis hidangan tersebut bisa diperoleh dengan cara mengalikan banyaknya jenis makanan dengan banyaknya jenis minuman. Teknik perhitungan yang demikian disebut dengan Prinsip Perkalian. Selain prinsip perkalian, terdapat teknik perhitungan lain yang bisa digunakan untuk memecahkan masalah-masalah diskrit, yaitu Prinsip Penambahan.

B. ATURAN PEMNJUMLAHAN

Definisi

Misalkan terdapat t himpunan X1,X2, …, Xt yang masing-masing mempunyai n1, n2, …, nt anggota. Jika himpunan-himpunan tersebut saling lepas, yaitu Xi Ç Xj = Æ untuk i ≠ j, maka banyaknya anggota yang bisa dipilih dari masing-masing himpunan tersebut adalah

n1 + n2 + … + nt

Contoh

Berapa banyak untai 4 bit yang diawali dengan digit 10 dan 11?

Untuk menyusun untai 4 bit yang diawali dengan 10 ada dua langkah. Langkah pertama adalah memilih digit ketiga yang bisa dilakukan dalam 2 cara (memilih 0 atau 1) dan langkah kedua adalah memilih digit yang keempat yang juga bisa dilakukan dalam 2 cara. Sehingga banyaknya untai 4 bit yang diawali dengan digit 10 adalah 2x2 = 4. Dengan cara yang sama dapat diperoleh banyaknya untai 4 bit yang diawali dengan digit 11, yaitu ada 4 untai. Jadi banyaknya untai 4 bit yang diawali dengan digit 10 dan 11 adalah 4 + 4 = 8

C. ATURAN PERKALIAN

Definisi

Jika terdapat aktivitas yang terdiri dari t langkah berurutan, dimana langkah 1 bisa dilakukan dalam n1 cara, langkah 2 bisa dilakukan dalam n2 cara, dan seterusnya sampai langkah ke-t yang bisa dilakukan dalam nt cara, maka banyaknya aktivtas yang berbeda adalah n1.n2…nt

Contoh

Gunakan prinsip perkalian untuk menghitung masalah banyaknya macam hidangan yang terdiri satu jenis makanan dan satu jenis minuman diatas.

Masalah perhitungan banyaknya macam hidangan yang terdiri satu jenis makanan dan satu jenis minuman diatas merupakan aktivitas yang terdiri dari 2 langkah, dimana langkah pertama adalah memilih makanan yang bias dilakukan dalam 4 cara, dan langkah kedua adalah memilih minuman yang bisa dilakukan dalam 3 cara, sehingga banyaknya macam hidangan adalah 4x3 = 12.

D. PENGHITUNG TAK LANGSUNG

Selain perhitungan-perhitungan langsung, kadang-kadang masalah kombinatorika akan lebih mudah diselesaikan secara tidak langsung, yaitu dengan menghitung komplemennya.

Contoh

Suatu kartu bridge lengkap diambil satu per satu dengan pengembalian. Berapa banyak cara yang mungkin untuk mengambil 10 kartu sedemikian hingga kartu ke-10 adalah perulangan dari kartu yang telah diambil sebelumnya?

Penyelesaian

Soal di atas akan diselesaikan dengan cara menghitung, komplemennya, yaitu mengambil 10 kartu sedemikian sehingga kartu ke-10 bukanlah kartu yang pernah diambil sebelumnya.

Mulai-mula, ambil kartu ke-10 (ada 52 cara).

Kartu ke-1 hingga kartu ke-9 haruslah berbeda dengan kartu ke-10 tersebut. Jadi, ada (52-1)⁹ = 51⁹ cara untuk mendepatkan ke-9 kartu pertama. Dengan demikian, ada (51⁹) (52) cara untuk mengambil 10 kartu sedemikian hingga kertu ke-10 berbeda dengan kartu-kartu ke 1 hingga ke-9.

Padahal jika tidak ada syarat apapun untuk mengambil ke-10 kartu, maka ada 52¹⁰ cara.

Jadi, banyak cara untuk mengambil 10 kartu sedemikian hingga kartu ke-10 adalah perulangan dari kartu yang telah diambil sebelumnya adalah 52¹⁰ – (51⁹)(52) cara.

E. KORESPONDENSI SATU-SATU

Suatu teknik lain untuk menghitung dilakukan dengan cara mengganti masalah yang sedang diselesaikan dengan masalah lain yang diketahui memiliki jumlah objek yang sama. Tentu saja masalah pengganti tersebut haruslah lebih sederhana dan mudah dihitung.

Contoh

Suatu pertandingan bola basket dengan sistem gugur diikuti oleh 101 regu. Dalam sistem tersebut, regu yang kalah akan langsung gugur dan regu yang menang akan maju ke babak berikutnya. Jika jumlah regu dalam suatu babak tertentu ganjil, maka ada 1 regu yang mendapatkan bye (menang tanpa bertanding). Berapa banyak keseluruhan pertandingan yang harus dilakukan untuk mendapatkan satu regu yang menjadi juara?

Penyelesaian

Soal di atas akan diselesaikan dengan cara langsung dan dengan korespondensi satu-satu.

·         Dengan cara langsung

Babak I diikuti 101 regu sehingga harus dilakukan 50 kali pertandingan (1 regu mendapatkan bye). Pemenang akan masuk ke babak II.

Babak II diikuti oleh 51 regu (50 regu pemenang dan 1 regu yang mendapatkan bye) sehingga jumlah pertandingan yang harus dilakukan adalah 25 kali (1 regu mendapatkan bye).

Babak III dikiuti oleh 26 regu sehingga jumlah pertandingan yang harus dilakukan adalah 13 kali.

Babak IV diikuti oleh 13 regu sehingga jumlah pertandingan adalah 6 kali.

Babak V diikuti oleh 7 regy sehingga harus dilakukan 3 kali pertandingan.

Babak VI diikuti oleh 4 regu sehingga jumlah pertandingan 2 kali.

Babak VII (final)diikuti oleh 2 regu dan dilakukan 1 kali pertandingan untuk mendapatkan regu yang menjadi juara. Jadi jumlah total pertandingan yang harus dilakukan adalah 50+25+13+6+3+2+1=100 kali.

·         Dengan membuat korespondensi satu-satu

Jika diperhatikan dalam setiap babak, jumlah pertandingan yang harus dilakukan selalu sama dengan jumlah regu yang kalah. (Babak I ada 50 regu yang kalah, babak II ada 25 regu, dst). Ada 101 regu yang mengikuti pertandingan dan hanya 1 regu yang menjadi juara. Oleh karena digunakan sistem gugur, berarti ada (100-1)=100 regu yang kalah. Untuk itu, jumlah pertandingan yang harus dilakukan adalah 100 kali.

F. KOMBINASI DAN PERMUTASI

Sebuah permutasi dari sebuah himpunan obyek-obyek berbeda adalah penyusunan berurutan dari obyek-obyek tersebut.

Contoh

Misalkan S = {1, 2, 3}. Susunan  3 1 2 adalah sebuah permutasi dari S. Susunan   3 2   adalah sebuah  permutasi-2  (2-permutation)  dari S.

Banyak  permutasi-r  dari himpunan dengan n obyek berbeda dinyatakan sebagai P(n,r) dimana  

P(n,r) = n . (n - 1) . (n - 2) . (n - 3) . ... . (n – r + 1).

Jika  r  =  n , maka

P(n,n) = n . (n - 1) . (n - 2) . (n - 3) . ... . (n – n + 1).

            = n . (n - 1) . (n - 2) . (n - 3) . ... . 1

            = n !

atau ditulis         Pn = n !

Contoh

P(8,3)   =   8. 7. 6   =   336

                        =            =             

Rumus umum     :          n . (n-1) . (n-2)  = 

            P(n,r) =

Sebuah kombinasi-r elemen-elemen dari sebuah himpunan adalah pemilihan tak berurutan (tanpa memperhatikan urutan)  r  elemen dari himpunan tersebut.

Contoh

Jika S = {1, 2, 3, 4}, susunan { 1, 3, 4 } adalah sebuah kombinasi-3 dari S.

            Banyaknya kombinasi-r (r-combinations) dari sebuah himpunan dengan n obyek berbeda dinyatakan sebagai  C(n,r)   atau     atau   .

Rumus umum     :                     

                        Jika  r = n,    maka      

G. FAKTORIAL

Misalkan n adalah bilangan bulat positif. Besaran n faktorial (simbol n!) didefinisikan sebagai hasil kali semua bilangan bulat antara 1 hingga n. Untuk n = 0, nol faktorial didefinisikan=1.

            n! = 1.2.3 ... (n-1).n

            0! = 1.

Contoh

Tulislah 5 faktorial pertama!

Penyelesaian

0! = 1

1! = 1

2! = 1.2 = 2                  

3! = 1.2.3          = 6

4! = 1.2.3.4       = 24

5! = 1.2.3.4.5    = 120

Terlihat bahwa pertumbuhan faktorial sangat cepat. Komputer yang memiliki pertumbuhan algoritma dalam skala faktorial sangatlah tidak logis untuk dijalankan.

Dari definisi faktorial:

n!         = 1.2.3. ... (n-2) (n-1) n

(n-1)!    = 1.2.3. ... (n-2) (n-1)

Sehingga

Didapatkan persamaan n! = n(n-1)!

H. KOMBINASI

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 :

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.

I. 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)

=

Contoh:

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

           

                       

                        =6

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

J. KOMBINASI DAN PERMUTASI DENGAN ELEMEN BERULANG

Sebuah himpunan disebut himpunan ganda (himpunan dengan pengulangan) jika setiap anggotanya berulang.

Contoh 2.5.

1.     A = { 3.a,  2.b,  5.c } adalah sebuah himpunan dari 3 elemen berbeda dengan pengulangan hingga.

2.     B = { ~.3,  ~.5,  ~.7, ~.9 } adalah sebuah himpunan dari empat elemen berbeda dengan pengulangan tak hingga.

3.     C =  { ~.p,  10.q,  3.r, ~.s } adalah sebuah himpunan dari empat elemen berbeda dengan pengulangan.

                                   

            Misalkan A sebuah himpunan ganda berpengulang tak hingga dengan k  anggota berbeda. Banyaknya kombinasi-r  pada  A  dinyatakan sebagai :

Contoh

Diketahui  S = { ~.a } . Banyaknya kombinasi-5 pada S adalah :

K. PETUNJUK DALAM PERHITUNGAN

Pertama, bacalah pertanyaan baik-baik. Perhatikanlah apakah masalah tersebut mengandung 2 macam perhitungan yang berbeda. Jika demikian, pikirkan aturan manakah yang dipakai untuk menggabungkan bagian-bagian tersebut. Apabila bagian-bagian tersebut merupakan suatu proses yang berurutan, maka aturan perkalian digunakan untuk menggabungkannya. Akan tetapi, bila bagian-bagian tersebut merupakan pecahan-pecahan dari masalah utama di mana masing-masing bagian terpisah satu sama lain, maka aturan penjumlahan digunakan untuk menggabungkan bagian-bagian tersebut.

Kedua, bacalah dengan teliti permasalahannya. Carilah kata-kata kuncinya. Kata kunci penggunaan kombinasi adalah pemilihan objek-objek yang tidak diperhatikan urutannya, sedangkan kata kunci untuk permutasi adalah pengaturan objek-objek yang urutannya diperhatikan.

L. KOEFISIEN BINOMIAL

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

(x + y)⁰ = 1                                                                   1

(x + y)¹ = x + y                                                  1          1

(x + y)² = x² + 2xy + y²                                                               1          2          1

(x + y)³ = x³ + 3x²y + 3xy² + y³                                                     1          3          3          1

(x + y)⁴ = x⁴ + 4x³y + 6x²y² + 4xy³ + y⁴                                      1          4          6          4          1

(x + y)⁵ = x⁵ + 5x⁴y + 10x³y² + 10x²y³ + 5xy⁴ + y⁵   1          5          10         10         5          1

Secara umum, diperoleh rumus sebagai berikut :

(x + y)ⁿ = C (n, 0) xⁿ + C (n, 1) x^n-1 y¹ + … + C (n, k) x^n-k y^k + … + C (n, n) yⁿ

=

Bilangan C (n, k) merupakan koefisien untuk x^n-ky^k dinamakan koefisien binomial.

Contoh :

Jabarkan (2x + y)³.

Jawab :

Misalkan a = 2x dan b = y,

(a + b)³ = C (3, 0) a³ + C (3, 1) a²b¹ + C (3, 2) a¹b² + C (3, 3) b³

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

= 8 x³ + 12x² y + 6x y² – y³

M. IDENTITAS-IDENTITAS DALAM KOMBINASI DAN PERMUTASI

1.     Sifat simetri :

2.     Identitas Newton:  untuk bilangan bulat  n ≥ r ≥ k ≥ 0

N. SEGITIGA PASCAL

Segitiga pascal merupakan salah satu persamaan yang sangat penting dam kombinatorika. Segita pascal memberikan jalan untuk menghitung kombinasi suatu suku berdasarkan kombinasi suku-suku yang lebih rendah. Jika harga  diketahui untuk semua r, maka harga dapat dihitung untuk semua r (0 <r ≤ n).

Secara formal, identitas pascal dapat dinyatakan dalam persamaan:

O. TEOREMA BINOMIAL DAN MULTINOMIAL

Binomial

Sebelum kita membahas tentang Teorema Binomial, akan diperkenalkan dulu tentang Koefisien Binomial. Koefisien Binomial disusun berdasarkan definisi kombinatorik. Hasil susunan dari kombinatorik yang bersesuaian dalam tingkat orde tertentu dalam koefisien binomial akan menyusun segitiga Pascal. Selanjutnya konsep segitiga Pascal tersebut dipakai untuk menyelesaikan kasus yang lebih kompleks.

Teorema Binomial

Misalkan x dan y adalah bilangan-bilangan riil dan n adalah bilangan bulat tak negative, maka

Teorema Multinomial

Multinomial merupakan perluasan dari Binomial. Multinomial adalah jumlahan t buah suku berbda, yaitu x₁+ x₂+…+ x_t. Binomial adalah kasus khusus dari multinomial, yaitu untuk t=2.

Teorema multinomial adalah rumus penjabaran (x₁+ x₂+…+ x_t)ⁿ. secara formal, teorema multinomial adalah sebagai berikut:

Misalkan x₁+ x₂+…+ x_t adalah bilangan-bilangan riil dan n adalah bilangan bulat positif.

Dengan demikian,

Penjumlahan dilakukan terhadap semua q1,q2,…qt dengan q1+q2+…+qt=n

Banyaknya suku pada (x₁+ x₂+…+ x_t)ⁿ adalah

P. PRINSIP INKLUSI DAN EKSKLUSI

Misalkan A dan B sembarang himpunan. Penjumlahan ½A½+½B½ menghitung banyaknya elemen A yang tidak terdapat dalam B dan banyaknya elemen B yang tidak terdapat dalam A tepat satu kali, dan banyaknya elemen yang terdapat dalam   A Ç B sebanyak dua kali. Oleh karena itu, pengurangan banyaknya elemen yang terdapat dalam A Ç B  dari ½A½+½B½ membuat banyaknya anggota A Ç B dihitung tepat satu kali. Dengan demikian,

½A È B½=  ½A½+½B½ - ½A Ç B½.

            Generalisasi dari hal tersebut bagi gabungan dari sejumlah himpunan dinamakan prinsip inklusi-eksklusi.

Contoh

            Dalam sebuah kelas terdapat 25 mahasiswa yang menyukai matematika diskrit, 13 mahasiswa menyukai aljabar linier dan 8 orang diantaranya menyukai matematika diskrit dan aljabar linier. Berapa mahasiswa terdapat dalam kelas tersebut ?

Jawab :

Misalkan A himpunan mahasiswa yang menyukai matematika diskrit dan B himpunan mahasiswa yang menyukai aljabar linier. Himpunan mahasiswa yang menyukai kedua mata kuliah tersebut dapat dinyatakan sebagai himpunan A Ç B. Banyaknya mahasiswa yang menyukai salah satu dari kedua mata kuliah tersebut atau keduanya dinyatakan dengan ½A È B½. Dengan demikian           ½A È B½            =  ½A½+½B½ - ½A Ç B½

            =  25 + 13 – 8

            =  30.

Jadi, terdapat 30 orang mahasiswa dalam kelas tersebut. 

Contoh

            Berapa banyak bilangan bulat positif yang tidak melampaui 1000 yang habis dibagi oleh 7 atau 11 ?

Jawab :

Misalkan P himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan Q himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 11. Dengan demikian P È Q adalah himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11, dan      P Ç Q  himpunan bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 dan habis dibagi 11.

½P½ =

½Q½ =

½P Ç Q½ =

½P È Q½ =  ½P½ + ½Q½ -½P Ç Q½ = 142 + 90 – 12 = 220.

            Jadi, terdapat 220 bilangan bulat positif tidak melampaui 1000 yang habis dibagi 7 atau habis dibagi 11. Ilustrasi dari penghitungan tesebut dapat dilihat pada diagram di bawah ini.

 

Q. BEBERAPA APLIKASI KOMBINATORIKA DALAM ILMU KOMPUTER

Kebanyakan program mengandung loop di dalamnya. Biasanya statement dalam loop inilah yang paling sering dieksekusi sehingga lama waktu eksekusi sedikit banyak tergantung dari berapa kali loop-loop dalam program dieksekusi.

Contoh

1.     For i = 1 to n Do

Statement-statement dalam loop. Tidak ada perintah di dalamnya yang menyebabkan eksekusi melompat keluar loop.

{End For – i}

2.   For i = 1 to n Do

            For j = 1 to n Do

                        Statement-statement dalam loop. Tidak ada perintah di dalamnya              yang menyebabkan eksekusi melompat keluar loop.

                        {End For – j}

            {End For – i}