BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

Pada bab ini akan dibahas beberapa konsep dasar seperti teorema dan beberapa definisi yang akan penulis gunakan sebagai landasan berpikir dalam melakukan penelitian ini sehingga mempermudah penulis untuk menunjang pencarian rumus untuk menghitung subgraf dari suatu graf. Adapun konsep dasar yang dimaksud adalah yang berkaitan dengan penelitian ini seperti definisi dan konsep dasar graf, jenis – jenis graf, kaidah – kaidah dasar menghitung, serta mengenai konsep permutasi dan kombinasi. 2.1

Definisi dan Konsep Dasar Graf

Suatu graf adalah sebuah objek matematika yang terdiri dari: (1) Himpunan titik – titik tak kosong V yang unsur – unsurnya disebut titik atau verteks, dan (2) himpunan garis E yang menghubungkan verteks – verteks dan disebut rusuk (edge). Dengan perkataan lain, suatu graf adalah sebuah himpunan berhingga yang terdiri dari verteks dan rusuk yang setiap ujung rusuk tersebut menghubungkan verteks – verteks. Suatu graf dapat ditulis sebagai G (V,E) atau graf G saja. Verteks – verteks dalam graf G ditulis dengan huruf kecil seperti u, v, atau vi, vj. Rusuk – rusuk dalam graf G dapat dipresentasikan sebagai e1,e2,e3,…,en. Suatu rusuk dapat juga ditulis sebagai sebuah pasangan verteks – verteks ujung seperti (v1,v2), (v2,v3,),…,(vi,vj). Jika e = (vi,vj) ∈ E (G) maka vi dan vj disebut verteks bertetangga (adjacent vertices), maksudnya adalah apabila 2 buah verteks dihubungkan oleh

sebuah rusuk maka kedua verteks itu disebut bertetangga. Jika rusuk ei dan ej

keduanya bertemu pada satu verteks yang sama maka kedua rusuk itu disebut rusuk terhubung (incident edges). Selain itu pada verteks bertetangga (adjacent vertices) vi dan vj yang dihubungkan oleh rusuk e maka rusuk e dikatakan terhubung (incident)

Universitas Sumatera Utara

pada vi dan vj, dan begitu juga sebaliknya vi dan vj dikatakan terhubung (incident) pada e. Contoh 2.1.1 : Berikut adalah contoh graf G (6,10), yaitu graf dengan 6 verteks dan 10 rusuk. Himpunan verteksnya adalah V = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 } dan himpunan

rusuknya adalah E = {𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 , 𝑒6 , 𝑒7 , 𝑒8 , 𝑒9 , 𝑒10 } = {(𝑣2 , 𝑣3 ),( 𝑣2 , 𝑣3 ),( 𝑣2 , 𝑣5 ),

(𝑣3 , 𝑣4 ),( 𝑣1 , 𝑣1 ),( 𝑣1 , 𝑣4 ),( 𝑣4 , 𝑣4 ),( 𝑣4 , 𝑣6 ),( 𝑣5 , 𝑣6 ),(𝑣5 , 𝑣6 )}. Jika A adalah himpunan

dua verteks yang bertetangga (adjacent vertices) 𝑣𝑖 dan 𝑣𝑗 maka A = {(𝑣𝑖 , 𝑣𝑗 )} =

{(𝑣2 , 𝑣3 ),( 𝑣2 , 𝑣3 ),( 𝑣2 , 𝑣5 ),( 𝑣3 , 𝑣4 ),( 𝑣1 , 𝑣1 ),( 𝑣1 , 𝑣4 ),( 𝑣4 , 𝑣4 )( 𝑣4 , 𝑣6 ),( 𝑣5 , 𝑣6 ),(𝑣5 , 𝑣6 )}

Hal ini menunjukkan bahwa 𝑣2 bertetangga dengan 𝑣3 , 𝑣2 bertetangga dengan 𝑣5 , dan seterusnya seperti yang ditunjukkan oleh unsur – unsur di himpunan A. Namun 𝑣1

tidak bertetangga dengan 𝑣2 karena tidak ada rusuk yang menghubungkan kedua verteks tersebut, begitu juga yang terjadi dengan verteks – verteks lainnya jika tidak ada rusuk yang menghubungkan mereka. Selain itu dapat pula dikatakan bahwa 𝑒1

terhubung (incident) pada 𝑣2 dan 𝑣3 , sebaliknya juga 𝑣2 dan 𝑣3 terhubung (incident) pada 𝑒1 . Selanjutnya apabila himpunan I adalah himpunan rusuk – rusuk terhubung

(incident edges) 𝑒𝑖 ,𝑒𝑗 ,𝑒𝑘 ,… maka I = {(𝑒1 ,𝑒2 ,𝑒3 ),( 𝑒1 ,𝑒2 ,𝑒4 ),(𝑒3 ,𝑒9 ,𝑒10 ),( 𝑒4 ,𝑒6 ,𝑒7 ,𝑒8 ),

( 𝑒5 ,𝑒6 ),( 𝑒8 ,𝑒9 ,𝑒10 )}. Pada himpunan I ditunjukkan bahwa rusuk – rusuk yang saling terhubung pada satu verteks bisa saja lebih dari dua rusuk. 𝒗𝟐

𝒆𝟓 𝒗𝟏 𝒗𝟔 𝒆𝟏𝟎

𝒆𝟏

𝒆𝟔

𝒆𝟗

𝒆𝟐

𝒆𝟑

𝒗𝟑 𝒆𝟒

𝒆𝟖

𝒗𝟒 𝒗𝟓

𝒆𝟕

Gambar 2.1 : Graf dengan 6 verteks dan 10 rusuk

Universitas Sumatera Utara

2.2

Jenis-Jenis Graf

Pada dasarnya setiap peristiwa di alam nyata dapat dipresentasikan dalam bentuk graf. Hal ini mengakibatkan setiap orang dapat menggambar bermacam – macam graf yang dia perlukan bergantung pada situasi ataupun kegiatan yang dia lakukan. Adapun secara umum graf dapat digolongkan kepada beberapa jenis yaitu dapat berdasarkan jenis rusuknya, ataupun dapat juga digolongkan berdasarkan ada atau tidaknya arah pada rusuk dari graf tersebut. Berdasarkan jenis rusuknya maka graf dibagi kepada 2 jenis yaitu graf sederhana (simple graph) dan graf tak sederhana (unsimple graph). Adapun graf sederhana adalah graf yang tidak mengandung gelang (loop) maupun rusuk ganda (multiple edge). Gelang (loop) adalah suatu rusuk yang terhubung (incident) dari suatu verteks dan kembali lagi ke verteks yang sama, atau dengan kata lain rusuk tersebut terhubung (incidents) dengan verteks tunggal saja serta dinotasikan menjadi e = ( 𝑣𝑖 , 𝑣𝑖 ).

Sedangkan rusuk ganda (multiple edge) adalah beberapa buah rusuk yang terhubung (incident) pada pasangan verteks yang sama, atau dengan kata lain kedua verteks tersebut terhubung (incident) pada lebih dari satu rusuk. Kemudian graf tak sederhana adalah graf yang mengandung rusuk ganda dan dapat saja juga mengandung gelang. Adapun graf tak sederhana dapat dibagi 2 yaitu graf ganda (multi graph) dan graf semu (pseudo graph). Graf ganda adalah graf yang memiliki rusuk ganda tanpa memiliki gelang. Sedangkan graf semu adalah graf yang memiliki gelang dan bisa juga sekalian memiliki rusuk ganda atau hanya memiliki gelang tanpa rusuk ganda. Contoh 2.2.1 : Berikut adalah contoh graf sederhana G (5,5) 𝒗𝟏 𝒆𝟏 𝒗𝟑

𝒆𝟐

𝒗𝟐 𝒗𝟓

𝒆𝟒

𝒆𝟑

𝒆𝟓 𝒗𝟒

Gambar 2.2 : Graf sederhana dengan 5 verteks dan 5 rusuk

Universitas Sumatera Utara

Contoh 2.2.2 : Berikut adalah contoh graf ganda G (6,9) 𝒗𝟏 𝒆𝟒

𝒗𝟐

𝒆𝟓

𝒆𝟑

𝒆𝟏

𝒆𝟐

𝒗𝟑 𝒆𝟕

𝒆𝟔

𝒗𝟒 𝒆𝟖

𝒗𝟓

𝒆𝟗

𝒗𝟔

Gambar 2.3 : Graf ganda dengan 6 verteks dan 9 rusuk Pada gambar graf 2.3 di atas, rusuk ganda diperlihatkan oleh pasangan rusuk (𝑒1 , 𝑒3 ), (𝑒4 , 𝑒5 ), dan (𝑒8 , 𝑒9 ). Dengan adanya rusuk ganda di dalam graf tersebut

menunjukkan bahwa graf itu adalah graf ganda.

Contoh 2.2.3 : Berikut adalah contoh graf semu G (8,12) 𝒆𝟏

𝒗𝟏 𝒆𝟐 𝒗𝟑 𝒆𝟏𝟏

𝒗𝟐

𝒆𝟑

𝒆𝟒

𝒆𝟔

𝒗𝟒

𝒆𝟕 𝒆𝟗 𝒗𝟕

𝒗𝟓

𝒆𝟓

𝒆𝟖 𝒆𝟏𝟎 𝒗𝟖

𝒗𝟔

𝒆𝟏𝟐

Gambar 2.4 : Graf semu dengan 8 verteks dan 12 rusuk Pada gambar graf 2.4 di atas, gelang diperlihatkan oleh rusuk 𝑒11 dan 𝑒12 . Pada

graf semu di atas juga terdapat rusuk ganda yaitu pasangan rusuk (𝑒4 , 𝑒5 ), namun suatu graf dikatakan graf semu tidak harus memiliki juga rusuk ganda melainkan graf tersebut minimal harus ada memiliki 1 gelang sehingga apabila suatu graf semu tidak memiliki rusuk ganda namun memiliki gelang maka graf tersebut tetap dinamakan

Universitas Sumatera Utara

graf semu. Dengan adanya gelang di dalam graf tersebut menunjukkan bahwa graf itu adalah graf semu. Selanjutnya berdasarkan ada atau tidaknya arah pada rusuk, maka graf dapat terbagi 2 yaitu graf tak berarah (undirected graph) dan graf berarah (directed graph) yang biasa disebut juga digraf. Graf tak berarah adalah graf yang setiap rusuknya tidak memiliki arah sehingga setiap rusuknya hanya digambarkan berupa garis saja tanpa ada penunjuk arah. Adapun contoh dari graf tak berarah adalah seperti graf pada gambar 2.2, 2.3, dan 2.4. Sedangkan graf berarah adalah graf yang setiap rusuknya memiliki arah tertentu sehingga rusuk – rusuknya digambarkan berupa garis beserta tanda panah sebagai penunjuk arah tertentu. Contoh 2.2.4 : Berikut adalah contoh graf berarah G (6,13) 𝒆𝟏

𝒗𝟏 𝒆𝟐

𝒗𝟑 𝒆𝟏𝟎

𝒗𝟓

𝒆𝟑 𝒆𝟏𝟏

𝒆𝟓

𝒆𝟒 𝒆𝟏𝟑

𝒆𝟕 𝒆𝟔

𝒗𝟔

𝒗𝟐 𝒆𝟖

𝒗𝟒

𝒆𝟗

𝒆𝟏𝟐

Gambar 2.5 : Graf berarah dengan 6 verteks dan 13 rusuk

2.3

Kaidah – Kaidah Dasar Menghitung

Materi pembahasan dalam bidang matematika diskrit dan kombinatorial biasanya dimulai dari pembahasan mengenai kaidah – kaidah dasar dalam menghitung. Adapun kaidah dasar ini terbagi 2 yaitu kaidah penjumlahan (rule of sum) dan kaidah perkalian (rule of product). Di dalam percobaan – percobaan ataupun aplikasi – aplikasi matematika yang berhubungan dengan matematika diskrit baik yang sederhana maupun yang kompleks maka kedua kaidah ini sering dipakai untuk mencari solusi

Universitas Sumatera Utara

dalam menghitung banyaknya jumlah kemungkinan dari percobaan tersebut. Jadi misalnya pada percobaan memasukkan sebuah kelereng ke dalam sebuah kantung, percobaan memasukkan beberapa kelereng ke dalam beberapa kantung, memilih wakil dari beberapa kelompok mahasiswa, memasang taruhan pada lomba pacuan kuda, percobaan melemparkan sekeping koin, percobaan menggulirkan sepasang dadu, membagi kartu pada permainan poker, dan masih banyak lagi percobaan – percobaan matematika lainnya.

2.3.1

Kaidah Penjumlahan (Rule of Sum)

Ketika melakukan suatu percobaan matematika, bisa saja unsur – unsur di dalam percobaan tersebut tidak saling memiliki hubungan. Dalam terminologi Himpunan, unsur – unsur tersebut dapat dianggap sebagai unsur – unsur yang tidak beririsan (intersection) ataupun tidak memiliki unsur bersama. Pada situasi inilah Kaidah Penjumlahan dipakai untuk menghitung banyaknya jumlah kemungkinan dari percobaan tersebut. Secara sederhana Kaidah Penjumlahan (rule of sum) dapat didefinisikan sebagai cara menghitung jumlah total kemungkinan dari cara suatu pekerjaan itu dilakukan yang melibatkan beberapa unsur kegiatan yang tidak saling berhubungan / tidak beririsan sedemikian hingga jumlah total dari kemungkinan – kemungkinan tersebut adalah penjumlahan dari setiap kemungkinan dari setiap unsur. Misalkan suatu pekerjaan mempunyai m cara untuk melakukannya dan sebuah pekerjaan lainnya mempunyai n cara untuk melakukannya. Jika kedua pekerjaan itu tidak dapat dilakukan secara bersamaan ataupun juga tidak bisa dilakukan secara berturut yang berarti harus dipilih salah satu dan meninggalkan yang lainnya, maka total keseluruhan cara untuk melakukan pekerjaan itu adalah sebanyak m + n cara. Contoh 2.3.1 : Berikut adalah contoh persoalan yang memakai Kaidah Penjumlahan dalam penyelesaiannya :

Universitas Sumatera Utara

Ada 2 cara untuk pergi dari Jakarta ke Pontianak, yaitu dengan menggunakan kapal terbang atau kapal laut. Untuk kapal terbang ada 4 penerbangan, sedangkan kapal laut ada 3 kapal. Ada berapa banyak cara untuk bepergian dari Jakarta ke Pontianak ? Jawaban : Karena cara bepergian dari Jakarta ke Pontianak dengan kapal terbang atau kapal laut adalah merupakan dua hal yang terpisah sehingga harus dipilih salah satunya saja. Maka total banyaknya cara untuk bepergian dari Jakarta ke Pontianak adalah sebanyak 4 + 3 = 7 cara. Yaitu dalam persoalan ini dipakailah Kaidah Penjumlahan untuk penyelesaiannya. (Budhi, 2003:145)

2.3.2

Kaidah Perkalian (Rule of Product)

Ketika melakukan suatu pekerjaan, adakalanya pekerjaan tersebut memiliki beberapa tahap pengerjaan. Dalam hal ini tahap – tahap pengerjaan tersebut adalah saling lepas yaitu tidak saling bergantung/tidak mempengaruhi satu sama lain. Pada situasi seperti inilah Kaidah Perkalian dipakai untuk menghitung banyaknya jumlah total kemungkinan dari urutan tahapan – tahapan pekerjaan itu. Secara sederhana Kaidah Perkalian (rule of product) dapat didefinisikan sebagai cara menghitung jumlah total kemungkinan dari kemungkinan – kemungkinan urutan – urutan pengerjaan dari suatu pekerjaan yang memiliki tahapan – tahapan di dalam pengerjaannya. Misalkan suatu pekerjan dapat dilakukan dengan 2 tahap pengerjaan yang saling lepas, tahap pertama memiliki m cara pengerjaan sedangkan tahap kedua memiliki n cara pengerjaan. Maka pekerjaan tersebut dapat dilakukan dengan total kemungkinan – kemungkinan urutan tahapan pengerjaannya adalah sebanyak m.n cara. Contoh 2.3.2 : Berikut adalah contoh persoalan yang memakai Kaidah Perkalian dalam penyelesaiannya :

Universitas Sumatera Utara

Misalkan seseorang akan pergi dari kota A ke kota C dan harus melalui kota B. Dari kota A menuju ke kota B terdapat 3 jalan, dan dari kota B menuju ke kota C terdapat 2 jalan. Ada berapa banyak kemungkinan cara untuk pergi dari kota A ke kota C melalui kota B ? Jawaban : Persoalan ini adalah mengenai suatu pekerjaan yang dilakukan secara bertahap yaitu di soal ini ada 2 tahapan. Tahapan pertama adalah memilih jalan dari kota A ke kota B, kemudian dilanjutkan dengan tahapan kedua yaitu memilih jalan dari kota B ke kota C. Maka pertama sekali hal yang harus dilakukan adalah memilih jalan dari kota A ke kota B, adapun pilihan jalan dari kota B ke kota C tidak tergantung pada pilihan jalan dari kota A ke kota B yang berarti keduanya saling lepas. Dengan demikian Kaidah Perkalian dapat diterapkan pada persoalan ini. Maka menurut Kaidah Perkalian, banyaknya kemungkinan cara perjalanan dari kota A ke kota C melalui kota B adalah sebanyak 3 × 2 = 6 cara. Apabila jalanan dari kota A ke kota B diberi lambang a, b, c sedangkan jalanan dari kota B ke kota C diberi lambang 1 dan 2. Maka pemilihan jalanan ini adalah sama halnya dengan memasangkan lambang – lambang tadi yaitu a1, a2, b1, b2, c1, c2 yang dapat dihitung berjumlah 6 cara pemilihan jalan. (Budhi, 2003:149-150)

2.4

Permutasi dan Kombinasi

Ada beberapa ide dan pemikiran matematika yang dapat dikembangkan dari Kaidah – Kaidah Dasar Menghitung. Beberapa diantaranya adalah yang berkaitan erat dengan Kaidah Perkalian yaitu Permutasi dan Kombinasi. Adapun konsep Kombinasi didapat dari pengembangan konsep Permutasi. Secara sederhana Permutasi dapat didefinisikan sebagai penyusunan n unsur yang berbeda menjadi berbagai bentuk / ukuran susunan dengan memperhatikan urutan unsur – unsur pada susunan tersebut. Dari definisi tersebut dapat dipahami bahwa urutan unsur – unsur di setiap susunan tersebut adalah penting untuk diperhatikan dan tidak boleh diabaikan sehingga apabila ada beberapa susunan yang

Universitas Sumatera Utara

seluruh unsur – unsurnya sama namun urutannya berbeda maka susunan – susunan tersebut tetap dianggap berbeda satu sama lain. Contoh 2.4.1 : Berikut adalah contoh persoalan yang memakai konsep Permutasi dalam penyelesaiannya : Misalkan ada 3 angka 5, 6, dan 7. Berapakah jumlah susunan yang dapat dibentuk dari 3 unsur angka tersebut dimana setiap susunan juga terdiri dari 3 angka serta tanpa pengulangan unsur ? Jawaban : Karena unsur – unsur dari susunan tersebut berupa angka – angka maka tentu dapat dipahami bahwa urutan adalah hal yang penting dan tidak bisa diabaikan di dalam susunan itu karena tentunya 657 dengan 576 adalah dianggap susunan yang berbeda meskipun seluruh unsur – unsurnya adalah sama. Maka di dalam persoalan ini dapat diterapkan konsep Permutasi untuk menyelesaikannya, selain juga dipakai Kaidah Perkalian. Untuk urutan pertama ada 3 kemungkinan unsur, untuk urutan kedua ada 2 kemungkinan unsur karena satu unsur telah dipakai di urutan pertama serta karena tidak boleh ada pengulangan unsur, terakhir untuk urutan ketiga ada 1 kemungkinan unsur. Dengan memakai Kaidah Perkalian maka total kemungkinan susunannya adalah 3 × 2 × 1 = 6 macam susunan. Adapun susunan tersebut adalah 567, 576, 657, 675, 756, 765. Selanjutnya karena persoalan ini adalah persoalan Permutasi dimana urutan unsur adalah faktor yang penting, maka jawaban ini adalah benar. Pada contoh 2.4.1 di atas diketahui bahwa terdapat 3 unsur yang kemudian disusun menjadi beberapa susunan yang masing – masing susunan tersebut terdiri dari 3 unsur juga tanpa pengulangan unsur. Hal ini berarti contoh 2.4.1 menunjukkan mengenai suatu n unsur yang disusun menjadi susunan – susunan yang masing – masing susunan tersebut terdiri dari sebanyak n unsur juga, atau dengan kata lain n unsur yang berbeda dipermutasikan kepada n unsur juga. Lalu bagaimana jika dari n unsur disusun menjadi susunan-susunan yang terdiri kurang dari n unsur ? Katakanlah jika dari n unsur akan dibentuk beberapa susunan yang masing – masing susunannya terdiri dari r unsur, dimana 1 ≤ r ≤ n.

Universitas Sumatera Utara

Contoh 2.4.2 : Di dalam suatu kelas terdapat 10 orang siswa yang dicalonkan untuk menjadi ketua kelas, wakil ketua kelas, sekretaris, dan bendahara. Ada berapakah semua susunan yang mungkin untuk jabatan – jabatan tersebut dimana setiap siswa dari 10 orang itu tidak boleh menduduki dua jabatan sekaligus ? Jawaban : Untuk menjawab persoalan ini maka perlu disusun dulu jumlah kemungkinan dari masing – masing jabatan. Adapun susunannya adalah : Jabatan

: Ketua Kelas Wakil Ketua Sekretaris Bendahara

Jumlah Kemungkinan :

10

9

8

7

Masing – masing jabatan jumlah kemungkinannya berkurang 1 dari jumlah sebelumnya karena tidak boleh ada seorang siswa yang merangkap lebih dari satu jabatan sehingga ketika seseorang sudah terpilih untuk suatu jabatan maka pada pemilihan jabatan yang lain dia tidak diikut – sertakan. Selanjutnya karena persoalan ini pada dasarnya adalah mengenai suatu pekerjaan yang bertingkat – tingkat yaitu pekerjaan yang dilakukan bertahap dimana tahap pertama adalah pemilihan ketua kelas selanjutnya tahap kedua adalah pemilihan wakilnya dan begitu seterusnya, maka jelaslah bahwa persoalan ini dapat diselesaikan dengan Kaidah Perkalian. Maka jumlah total semua susunan yang mungkin untuk jabatan – jabatan tersebut adalah 10 × 9 × 8 × 7 = 5040 kemungkinan susunan. Apabila contoh 2.4.2 diperhatikan dengan seksama, maka dapat diketahui bahwa persoalan pada contoh tersebut adalah suatu persoalan Permutasi. Hal ini karena pada persoalan tersebut salah satu unsur yang penting dan tidak dapat diabaikan adalah urutan unsur – unsur dalam susunan tersebut yaitu urutan pertama untuk ketua kelas kemudian urutan kedua untuk wakilnya dan seterusnya. Tentu saja pada suatu susunan tertentu dimana seorang siswa berada di urutan ke-3 yaitu menjadi sekretaris dengan apabila di kemungkinan susunan lainnya siswa yang sama tersebut berada di urutan ke-2 yaitu menjadi wakil ketua kelas, maka tentu saja susunan – susunan tersebut akan dianggap berbeda walaupun mungkin seluruhnya dari keempat orang siswa yang

Universitas Sumatera Utara

terpilih tersebut adalah kumpulan siswa yang sama di susunan – susunan tersebut. Sehingga apabila merujuk pada konsep Permutasi maka persoalan di contoh 2.4.2 adalah persoalan Permutasi dari 10 unsur yang berbeda kepada 4 unsur. Maka berdasarkan hasil yang telah didapat sebelumnya, hasil tersebut dapat diolah menjadi sebagai berikut : 10 × 9 × 8 × 7 =

10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 6×5×4×3×2×1

=

10! 6!

10!

= (10−4)!

Dari hasil ini dapat diketahui bahwa permutasi dari 10 unsur kepada 4 unsur dapat dituliskan menjadi

10! (10−4)!

. Apabila hasil ini diperumum maka menunjukkan

bahwa permutasi dari n unsur yang berbeda kepada r unsur adalah merupakan notasi untuk n faktorial yang didefinisikan dengan :

𝑛! (𝑛−𝑟)!

, dengan n!

0! = 1 n! = n.(n - 1).(n - 2). … .(3).(2).(1) , untuk n ≥ 1. Dari definisi ini maka bisa diketahu bahwa 1! = 1, 2! = 2.1 = 2, 3! = 3.2.1 = 6, 4! = 4.3.2.1 = 24, … dan seterusnya. Secara umum, jika ada n unsur yang dinotasikan 𝑎1 , 𝑎2 , 𝑎3 , … , 𝑎𝑛 , dan ada

sebuah bilangan asli r dengan 1≤

r ≤ n, maka berdasarkan Kaidah Perkalian,

banyaknya jumlah susunan permutasi berukuran r unsur yang diambil dari n unsur adalah : n urutan I

×

(n – 1) urutan II

×

(n – 2) urutan III

×

…

×

(n – r + 1 ) = urutan ke – r

�𝑛 – 𝑟��𝑛 – 𝑟 − 1� … (3)(2)(1)

n × (n – 1) × (n – 2) × … × (n – r + 1 ) × �𝑛 – 𝑟��𝑛 – 𝑟 − 1� … (3)(2)(1) =

𝑛! (𝑛−𝑟)!

.

Kemudian Permutasi dari n unsur kepada r unsur dinotasikan dengan P (n,r) 10!

dimana 0 ≤ r ≤ n. Pada contoh 2.4.2, permutasinya dinotasikan P(10,4) = (10−4)! =

10! 6!

Universitas Sumatera Utara

=

10 × 9 × 8 × 7 × 6! 6!

= 10 × 9 × 8 × 7 = 5040. Sehingga secara umum, banyaknya

Permutasi n unsur yang berbeda kepada r unsur dinotasikan dengan 𝑛!

P (n,r) = (𝑛−𝑟)! Selanjutnya, konsep Kombinasi dapat didefinisikan sebagai penyusunan n unsur yang berbeda menjadi berbagai bentuk/ukuran susunan tanpa memperhatikan urutan unsur – unsur pada susunan itu. Dari definisi ini dapat dipahami bahwa pada Kombinasi, urutan unsur adalah hal yang tidak penting sehingga dapat diabaikan. Hal yang dapat membedakan antara suatu susunan dengan susunan lainnya adalah hanya unsur – unsur pada susunan itu sedangkan apabila semua unsur – unsur dari beberapa susunan adalah sama maka susunan – susunan itu dianggap sama walaupun mungkin urutan unsur – unsur antara satu susunan dengan susunan lainnya berbeda. Secara umum, banyaknya Kombinasi n unsur yang berbeda kepada r unsur dinotasikan dengan 𝐶 (𝑛, 𝑟) =

𝑃 (𝑛,𝑟) 𝑟!

𝑛!

= 𝑟! × (𝑛−𝑟)!

Contoh 2.4.3 : Di dalam suatu kelas terdapat 10 orang siswa yang akan dipilih sebanyak 4 orang untuk diutus menjadi peserta olimpiade matematika. Ada berapakah semua susunan yang mungkin untuk keempat peserta tersebut?

Jawaban : Untuk menjawab persoalan ini maka perlu disusun dulu jumlah kemungkinan dari keempat peserta yang akan dipilih. Adapun susunannya adalah : 10 siswa

9 siswa

8 siswa

7 siswa

urutan I

urutan II

urutan III

urutan IV

Universitas Sumatera Utara

Persoalan ini sekilas mirip dengan persoalan Permutasi pada contoh 2.4.2, namun persoalan ini adalah persoalan yang berbeda karena merupakan soal Kombinasi karena pada persoalan ini susunan unsur – unsur menjadi tidak penting dan dapat diabaikan. Dengan pengabaian ini maka susunan – susunan yang keseluruhan unsur – unsurnya sama maka susunan – susunan tersebut dianggap sama. Maka jumlah kemungkinan susunan Kombinasi ini adalah 𝐶 (10,4) =

kemungkinan susunan.

𝑃 (10,4) 4!

=

10! 4! × (10−4)!

=

10!

4! × 6!

= 210

Teorema 2.1 Andaikan x dan y adalah variabel – variabel dan n adalah bilangan bulat positif, maka : (𝑥 + 𝑦)𝑛 = 𝐶 (𝑛, 0)𝑥 0 𝑦 𝑛 + 𝐶 (𝑛, 1)𝑥1 𝑦 𝑛−1 + 𝐶 (𝑛, 2)𝑥 2 𝑦 𝑛−2 + … + 𝐶 (𝑛, 𝑛 − 1)𝑥 𝑛−1 𝑦1 + 𝐶 (𝑛, 𝑛)𝑥 𝑛 𝑦 0

=�

𝑛

�𝑛𝑘�𝑥 𝑘 𝑦 𝑛−𝑘

𝑘=0

(Grimaldi, 1985:14)

Selanjutnya apabila pada teorema binomial diatas dimasukkan nilai – nilai x = 1 dan y = 1 maka akan menghasilkan : (𝑥 + 𝑦)𝑛 = 𝐶 (𝑛, 0)10 1𝑛 + 𝐶 (𝑛, 1)11 1𝑛−1 + 𝐶 (𝑛, 2)12 1𝑛−2 + … + 𝐶 (𝑛, 𝑛 − 1)1𝑛−1 11 + 𝐶 (𝑛, 𝑛)1𝑛 10

= 𝐶 (𝑛, 0). 1.1 + 𝐶 (𝑛, 1). 1.1 + 𝐶 (𝑛, 2). 1.1 + … + 𝐶 (𝑛, 𝑛 − 1). 1.1 + 𝐶 (𝑛, 𝑛). 1.1

= 𝐶 (𝑛, 0) + 𝐶 (𝑛, 1) + 𝐶 (𝑛, 2) + … + 𝐶 (𝑛, 𝑛 − 1) + 𝐶 (𝑛, 𝑛) = ∑𝑛𝑘=0 𝐶 (𝑛, 𝑘)

= (1 + 1)𝑛 = 2n

(Budhi, 2003:221)

Atau persamaan tersebut secara sederhana dapat ditulis : ∑𝑛𝑘=0 𝐶 (𝑛, 𝑘) = 𝐶 (𝑛, 0) + 𝐶 (𝑛, 1) + 𝐶 (𝑛, 2) + … + 𝐶 (𝑛, 𝑛 − 1) + 𝐶 (𝑛, 𝑛) = 2n

Universitas Sumatera Utara