Materi MatDis (Matematika Diskrit) : Pohon Part 2

1. Pohon Berakar 

          adalah pohon yang sebuah simpulnya diperlukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar.

Terminologi pada pohon berakar

Anak(Child atau children) dan Orangtua (parent)

Misalkan Xx adalah sebuah simpul di dalam pohon berakar. Simpul y dkatakan anak simpul x jika ada sisi dari simpul x ke y. Dalam hal demikian, x disebut orangtua (parent)  y. Pada gambar dibawah, b, c dan d adalah anak-anak simpul a, dan a adalah orangtua dari anak-anak itu. e dan f adalah anak-anak simpul b dan b adalah orangtua dari e dan f. g adalah anak simpul d dan d adalah orangtua g. Simpul h,i, j, l dan m tidak mempunyai anak.

2. Pohon Berakar Terurut

    adalah pohon berakar yang urutan anak-anaknya penting.

3. Pohon Ekspresi
   adalah pohon biner dengan daun menyatakan operand dan simpul dalam (termasuk akar) menyatakan operator. Perhatikan bahwa tanda kurang tidak lagi diperlukan bila suatu ekspresi aritmetik diprsentasikan sebagai pohon biner.
contoh :
(a+b) * c/(d+e) Infix
Prefix : *+ ab/c + de
Posfix : ab + cde +/*


INFIX, POSTFIX dan PREFIX

1. Infix
    Digunakan manusia sebagai input di komputer
2. Postfix
    Digunakan komputer sebagai proses
3. Prefix
    Sama Seperti Postfix yaitu digunakan komputer sebagai proses.

• Konversi Infix ke Postfix

ada 3 cara yaitu :
1. Cara Manual
    Caranya adalah dengan menyederhanakan  notasi menjadi dua operand (variabel) da satu operator, seperti A + B

2. Cara Stack
    Stack adalah tumpukan (jadi, memori diibaratkan dengan tumpukan) yang memiliki cara kerja yang pertama masuk ke kotak, maka akan terakhir kali diambil kembali atau first in last out atau sebaliknya, yang terakhir masuk ke kotak akan diambil yang pertama kali, atau last in first out.

3. Cara Binary Tree

• Konversi Infix ke Prefix

Ada 2 cara :
1. Cara Manual
    Sama seperti mengonversi notasi infix ke prefix
2. Cara Binary Tree
    Sama seperti mengonversi notasi infix ke prefix

• Konversi Prefix ke Infix dan/atau Postfix

Bisa dilakukan melalui bantuan manual dan pohon binar.

• Konversi Postfix ke Infix dan/atau Prefix

Sama seperti Konversi Prefix ke Infix dan/atau Postfix

Materi MatDis (Matematika Diskrit) : Pohon

DEFINISI POHON

Pohon adalah graf tak berarah terhubung yang tidak mengandung sirkuit.
Beberapa pohon dapat membentuk hutan. Hutan adalah kumpulan pohon yang saling lepas. Atau hutan adalah graf tak terhubung yang tidak mengandung sirkuit, dalam hal ini setiap komponen graf terhubung adalah pohon.
Pohon juga seringkali didefinisikan sebagai graf tak berarah dengan sifat bahwa hanya terdapat sebuah lintasan unik antara setiap pasang simpul.


POHON MERENTANG

adalah semua simpul pada pohon T sama dengan semua simpul pada graf G.
Pohon merentang didefinisikan hanya untuk graf terhubung, karena pohon selalu terhubung. Pada graf terhubung terdapat setidaknya satu buah pohon merentang.Graf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri. Pada graf yang mengandung sirkuit, pohon merentangnya diperoleh dengan cara memutuskan sirkuit yang ada.
Sisi pada pohon merentang disebut cabang. Sedangkan sisi dari graf yang tidak terdapat di dalam pohon merentang disebut tali hubung.Himpunan tali hubung beserta simpul yang bersisian disebut komplemen pohon. Rumus menghitung jumlah cabang dan jumlah tali hubung :

                                Jumlah cabang = n - 1
                                Jumlah tali hubung = m - n + 1

dan pada graf tidak terhubung dengan k komponen, m buah sisi dan n buah simpul,

                                Jumlah cabang = n - k
                                Jumlah tali hubung = m - n + k

Sirkuit yang terbentuk dengan penambahan sebuah tali hubung pada pohon merentang disebut sirkuit fundamental.


POHON MERENTANG MINIMUM

adalah pohon merentang yang berbobot minimum dimana pohon merentang ini merupakan pohon merentang yang paling penting karena mempunyai terapan yang luas dalam praktik.
Terdapat dua buah algoritma dalam membuat pohon merentang minimum :

1. Algoritma Prim

          Algoritma Prim membentuk pohon merentang minimum langkah per langkah. 

          1. Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T

          2. Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e                        tidak  membentuk sirkuit di T. Masukkan e ke dalam T

          3. Ulangi langkah 2 sebanyak n - 2 kali

         Jumlah langkah seluruhnya di dalam algoritma prim adalah 1 + (n - 2) = n - 1, yaitu sebanyak             jumlah sisi di dalam pohon merentang dengan n buah simpul.

     2. Algoritma Kruskal

         Pada algoritma kruskal, sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari           kecil ke besar. Perbedaan prinsip antara algoritma prim dan algoritma kruskal adalah : jika pada           algoritma prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T,               maka pada algoritma kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T             asalkan penambahan sisi tersebut tidak membentuk sirkuit.

         

         Algoritma Kruskal :

1. T Masih Kosong
2. Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T. Masukkan e ke dalam T
3. Ulangi langkah 2 sebanyak n - 1 kali

Materi MatDis (Matematika Diskrit) : Graf Part 2

GRAF PLANAR dan GRAF BIDANG

Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong. Reprsentasi dari graf planar disebut dengan graf bidang. Sisi-sisi pada graf graf bidang membagi bidang datar menjadi beberapa wilayah atau muka.

RUMUS EULER

Rumus euler sebagai berikut:

             n - e + f = 2
atau
            f = e - n + 2
keterangan:
e = jumlah sisi
n = jumlah simpul



TEOREMA KURATOWSKI

Sifat graf kuratowski :

1. Kedua graf kuratowski adalah graf teratur
2. Kedua graf kuratowski adalah graf tidak planar
3. Penghapusan sisi atau simpul dari graf kuratowski menyebabkannya menjadi graf planar
4. Graf kuratowski pertama adalah graf tidak planar dengan jumlah simpul minimum dan graf kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. Keduanya adalah graf tidak planar paling sederhana

HOMEOMORFIK

adalah jika salah satu dari kedua graf dapat diperoleh dari graf yang lain dengan cara menyisipkan dan/atau membuang secara berulang-ulang simpul berderajat 2.

LINTASAN dan SIRKUIT EULER

Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit euler.

Graf yang mempunyai sirkuit euler disebut graf euler. Graf yang mempunyai lintasan euler dinamakan graf semi euler.

LINTASAN dan SIRKUIT HAMILTON

Lintasan hamilton adalah lintasan yang melalui tiap simpul di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit hamilton.

Graf yang memiliki sirkuit hamilton disebut graf hamilton sedangkan graf yang hanya memiliki lintasan hamilton disbeut graf semi hamilton.

Materi MatDis (Matematika Diskrit) : Graf

1. Definisi Graf
    Graf adalah tidak adanya sisi satu buah pun namun memiliki simpul, minimal adanya simpul satu.

2. Jenis-jenis Graf
    Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara urutan graf dapat          digolongkan menjadi dua jenis :

•      Graf Sederhana

               adalah graf yang tidak mengandung gelang maupun sisi-ganda. Pada graf sederhana, sisi                     adalah pasangan terurut. Jadi menuliskan sisi (u, v) sama saja dengan (v, u). Graf sederhana                 dapat juga diartikan himpunan tidak kosong simpul-simpul dan himpunan pasangan tak                       terurut yang disebut sebagai sisi.

• Graf Tak Sederhana

           adalah graf yang mengandung sisi ganda atau gelang. Ada dua macam graf tak sederhana,                   yaitu

1.          Graf Ganda

                   adalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang                           simpul bisa lebih dari dua buah. Sisi ganda dapat diasosiasikan sebagai pasangan tak                           terurut yang sama. Serta dapat juga diartikan yang terdiri dari himpunan tidak kosong                           simpul-simpul dan himpunan ganda yang mengandung sisi ganda. Setiap graf sederhana                       juga adalah graf ganda tetapi tidak setiap graf ganda merupakan graf sederhana.

     

       2.         Graf Semu

               

                   adalah graf yang mengandung gelang. Graf semu lebih umum daripada graf ganda                               karena  sisi pada graf semu dapat terhubung ke dirinya sendiri.

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :

1. Graf Tak Berarah 

          adalah graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak berarah, urutan                        pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi (u, v) = (v, u) adalah sisi              yang sama.

  

       2. Graf Berarah

           adalah graf yang setiap sisinya diberikan orientasi arah. Sisi berarah disebut dengan busur.                 Pada graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda. Untuk busur (u,             v), simpul v dinamakan simpul asal dan simpul v dinamakan simpul terminal.

TERMINOLOGI DASAR

1. Bertetangga

          Duah buah simpul dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah                  sisi.

       2. Bersisian

           Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u dan simpul v.

       3. Simpul Terpencil

           adalah simpul yang tidak mempunyai sisi yang bersisian dengannya ataupun tidak satupun                   bertetangga dengan simpul-simpul lainnya.

        4. Graf Kosong

            adalah graf yang himpunan sisinya merupakan himpunan kosong.

         5. Derajat

             Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul                 tersebut.

             Notasi : d(v) menyatakan derajat simpul v
             Simpul yang berderajat satu disebut anting-anting. Dengan kata lain, anting-anting hanya                     bertetangga dengan sebuah simpul.

         6. Lintasan

             adalah barisan berselang-seling simpul-simpul dan sisi-sisi. Istilah lain untuk lintasan adalah               jalur. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan                           dikatakan lintasan sederhana jika semua simpulnya berbeda. Lintasan yang berawal dan                     berakhir pada simpul yang sama disebut lintasan tertutup sedangkan lintasan yang tidak                     berawal dan berakhir pada simpul yang sama disebut lintasan terbuka. Panjang lintasan                     adalah jumlah sisi dalam lintasan tersebut.

       7. Siklus atau Sirkuit

            adalah lintasan yang berawal dan berakhir pada lintasan yang sama. Panjang sirkuit adalah                  jumlah sisi di dalam sirkuit tersebut.

        8. Terhubung

             Dikatakan terhubung jika terdapat lintasan dari u ke v diantara dua buah simpul u dan simpul               v. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai dari simpul               yang kedua. Jika setiap pasang simpul di dalam graf terhubung maka graf tersebut dikatakan               graf terhubung.

          9. Upagraf dan Komplemen Upagraf

          10. Upagraf Merentang

          11. Cut-Set

                Cut-Set atau jembatan adalah himpunan sisi yang apabila dibuang dari graf menyebabkan                    graf tersebut tidak terhubung.

          12. Graf Berbobot

                adalah graf yang setiap sisinya diberi sebuah harga (bobot).

             
BEBERAPA GRAF SEDERHANA KHUSUS

1. Graf Lengkap

          adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.

       2. Graf Lingkaran

           adalah graf sederhana yang setiap simpulnya berderajat dua.

       3. Graf Teratur

            adalah graf yang setiap simpulnya mempunyai derajat yang sama.

        4. Graf Bipartit

            adalah himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian.


REPRESENTASI GRAF

1. Matriks Ketetanggaan

          Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan matriks              nol-satu. Selain dengan angka 0 dan , elemen matriks dapat juga dinyatakan dengan nilai false            (menyatakan 0) dan true (menyatakan 1). Matriks ketetanggaan untuk graf sederhana dan tidak            berarah selalu simetri sedangkan untuk graf berarah matriks ketetanggaannya belum tentu                    simetri. Selain itu, diagonal utamanya selalu nol karena tidak ada sisi gelang.

      2. Matriks Bersisian

          Matriks bersisian menyatakan kebersisian simpul dengan sisi. Baris menunjukkan label simpul sedangkan kolom menunjukkan label sisinya. Matriks bersisian dapat digunakan untuk mempresentasikan graf yang mengandung sisi ganda atau sisi gelang.

      3. Senarai Ketetanggaan

          Senarai ketetanggaan menganumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam graf.


GRAF ISOMORFIK

adalah dua buah graf yang sama tetapi secara geometri berbeda. Syarat-syarat dua buah graf isomorfik :

1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama.
3. Mempunyai jumlah simpul yang sama berderajat tertentu.

           

Materi MatDis (Matematika Diskrit) : Aljabar Boolean

1. Definisi Aljabar Boolean
    Yang disebut aljabar boolean adalah <B, +, ., ',  0, 1>

• Identitas

         (i) a + 0 = a
         (ii) a + 1 = a

• Komutatif

          (i) a + b = b + a
          (ii) a . b = b . a

• Distributif

          (i) a . (b +c) = (a . b) + (a . c)
          (ii) a + (b . c) = (a + b) . (a + c)

• Komplemen

          (i) a + a' = 1
          (ii) a . a' = 0


2. Prinsip Dualitas
    Misalkan S adalah kesamaan (identify) di dalam aljabar boolean yang melibatkan operator +, ., dan komplemen, maka jika pernyataan S* diperoleh dari S dengan cara mengganti
   
     . dengan +
     + dengan .
     0 dengan 1
     1 dengan 0
dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S


Hukum-hukum Aljabar Boolean
1. Hukum Identitas:
    (i) a + 0 = a
    (ii) a . 1 = a

2. Hukum Idempoten:
    (i) a + a = a
    (ii) a . a = a

3. Hukum Komplemen:
    (i) a + a' = 1
    (ii) aa' = 0

4. Hukum Dominansi:
    (i) a . 0 = 0
    (ii) a + 1 = 1

5. Hukum Involusi:
    (i) (a')' = a

6. Hukum Penyerapan:
    (i) a + ab = a
    (ii) a(a + b) = a

7. Hukum Komutatif:
    (i) a + b = b + a
    (ii) ab = ba

8. Hukum Asosiatif
    (i) a + (b + c) = (a + b) + c
    (ii) a (b c) = (a b) c

9. Hukum Distributif:
    (i) a + (b c) = (a + b)(a + c)
    (ii) a (b + c) = a b + a c

10. Hukum De Morgan
      (i) (a + b)' = a'b'
      (ii) (ab)' = a' + b'

11. Hukum 0/1
      (i) 0' = 1
      (ii) 1' = 0


Contoh Soal :
1. Bentuk baku SOP dan POS dari f (x, y, z) = xy + x'z

    SOP:
    xy = xy(z + z')
         = xyz + xyz'
    dan
    x'z = x'z (y +y')
          = x'yz + x'y'z
    Jadi f(x, y, z) = xy + x'z
                          = xyz + xyz' + x'yz + x'y'z
   Atau f(x, y, z) = m7 + m6 + m3 + m1
                          = (1, 3, 6, 7)

    POS:
    f(x, y, z) = xy +x'z
                   = (xy + x')(xy + z)
                  = (x + x')(y + x')(x + z)(y + z)
                   = (x' + y)(x + z)(y + z)
   
     x' + y = x' + y + zz' = (x' + y + z)(x' + y + z')
     x + z  = x + z + yy'  = (x + y + z)(x + y' + z)
     y + z   = xx' + y + z  = (x + y +z)(x' + y + z)

     Jadi f(x, y, z) = (x + y + z)(x + y' + z)(x' + y + z)(x' + y + z')

     Atau f(x, y, z) = M0 M2 M4 M5
                            = (0, 2, 4, 5)

2. Bentuk Baku SOP dan POS dari f(x, y, z) = x + yz'
   
     SOP:
     x = x(y + y')
        = xy + xy'
        = xy (z + z') + xy' (z + z')
        = xyz + xyz' + xy'z + xy'z'
    dan
    yz' = yz' (x + x')
          = yz'x + yz'x' = xyz' + x'yz'
 
     Jadi f(x, y, z) = x + yz'
                           = xyz + xyz' + xy'z + xy'z' + x'yz'
                           = x'yz' + xy'z' + xy'z + xyz' + xyz
     
     Atau f(x, y, z) = m2 + m4 + m5 + m6 + m7
                            = (2, 4, 5, 6, 7)


    POS:
    f(x, y, z) = x + yz'
                   = (x + y)(x + z')
 
    x + y = x + y + zz'
             = (x + y + z)(x + y + z')

    x + z' = x + z' + yy'
              = (x + y + z')(x + y' + z')

   Jadi f(x, y, z) = (x + y + z)(x + y + z')(x + y + z')(x + y' + z')
                         = (x + y + z)(x + y + z')(x + y' + z')

   Atau f(x, y, z) = M0 M1 M3
                          = (0, 1, 3)

Materi MatDis (Matematika Diskrit) : Permutasi dan Kombinasi

PERMUTASI Permutasi adalah jumlah urutan berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi aturan perkalian. Misalkan jumlah objek adalah n, maka urutan pertama dipilih dari n objek, urutan kedua dipilih dari n – 1 objek, urutan ketiga dipilih dari n – 2 objek, begitu seterusnya dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian, permutasi dari n objek adalah n(n – 1) (n – 2) . . . (2)(1) = n! Menurut kaidah perkalian, ada sebanyak n(n – 1) (n – 2) . . . (n – (r – 1)) buah susunan berbeda dari penyusunan r objek yang dipilih dari n objek. Jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek disebut permutasi-r, dilambangkan dengan P(n, r), yaitu P(n, r) = n(n – 1)(n – 2). . . (n – (r – 1)) = n!/(n-r)! Menurut persamaan tersebut, jumlah cara memasukkan 6 buah bola yang berbeda warnanya ke dalam 3 buah kotak adalah P(6, 3) = 6!/(6 - 3)! = 120 dan jumlah kemungkinan urutan 2 dari 3 elemen himpunan A = {a, b, c} adalah P(3, 2) = 3!/(3 – 2)! = 6. Permutasi r dari n objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤ n, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada objek yang sama. Bila r = n, maka P(n, n) = n!/(n-n)! = n!/0! = n!/1 = n! Contoh : Berapa banyak “kata” yang terbentuk dari kata “BOSAN”? Penyelesaian : Anggap setiap huruf di dalam kata “BOSAN” sebagai bola yang berbeda warnanya dan 5 buah kotak yang akan diisi dengan 1 bola pada setiap kotak. Cara 1 : (5)(4)(3)(2)(1) = 120 buah kata Cara 2 : P(5, 5) = 5! = 120 buah kata Berapa banyak cara mengurutkan nama 25 orang mahasiswa? Penyelesaian : Analogikan dengan mengisi 25 kotak dengan 25 bola huruf berbeda, setiap kotak diisi dengan 1 bola. Jadi, jumlah cara pengurutan nama mahasiswa sama dengan jumlah susunan 25 bola ke dalam 25 kotak, yaitu P(25, 25) = 25! Tiga buah ujian dilakukan dalam suatu periode enam hari (Senin sampai Sabtu). Berapa banyak pengaturan jadwal yang dapat dilakukan sehingga tidak ada dua ujian atau lebih yang dilakukan pada hari yang sama. Penyelesaian : Cara 1 (dengan kaidah perkalian) : sama seperti menempatkan 3 bola (ujian) berbeda ke dalam enam kotak (hari). Ujian pertama dapat ditempatkan pada salah satu dari enam hari; Ujian kedua dapat ditempatkan pada salah satu dari lima hari; Ujian ketiga dapat ditempatkan pada salah satu dari empat hari; Jumlah pengaturan jadwal ujian = (6)(5)(4) = 120 Cara 2 (dengan rumus permutasi) : P(6, 3) = 6! / (6 – 3)! = 120 Sebuah bioskop mempunyai jajaran kursi yang disusun per baris. Tiap baris terdiri dari 6 tempat kursi. Jika dua orang akan duduk, berapa banyak pengaturan tempat duduk yang mungkin pada suatu baris? Penyelesaian : Orang pertama mempunyai 6 pilihan kursi dan orang kedua mempunyai 5 pilihan kursi. Jadi, jumlah pengaturan tempat duduk = (6)(5) = 30 atau P(6, 2) = 6! / 4! = (6)(5) = 30 cara Berapa banyak string yang dapat dibentuk yang terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka yang berbeda pula? Penyelesaian : Ada P(26, 4) cara mengisi posisi 4 huruf dan P(10, 3) cara untuk mengisi posisi 3 buah angka. Karena string disusun oleh 4 huruf dan 3 angka, maka jumlah string yang dapat dibuat adalah P(26, 4) x P(10, 3) = 258.336.000 KOMBINASI Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Urutan acb, bca dan acb dianggap sama dan dihitung sekali. 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)! Rumus n!/r!(n-r)! Disebut rumus kombinasi-r dan dilambangkan dengan C(n, r) atau (n¦r). Jadi, C(n, r) = n!/r!(n-r)! C(n, r) sering dibaca “n diambil r”, artinya r objek diambil dari n buah objek. Kombinasi r elemen dari n elemen adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen. Dapat juga dibuktikan dengan cara membentuk permutasi-r dari n elemen. Mula-mula hitung kombinasi-r , yaitu C(n , r), kemudian urutkan elemen-elemen di dalam setiap kombinasi-r. Pengurutan ini dapat dilakukan dengan P(r, r) cara. Dengan demikian, permutasi-r dari n elemen adalah P(n, r) = C(n, r) P(r, r) Dari persamaan di atas kita peroleh C(n, r) = (P(n,r))/(P(r,r)) = (n!/(n-r)!)/r!(r-r)! = n!/r!(n-r)! Contoh : Berapa banyak cara menyusun menu nasi goreng tiga kali seminggu untuk sarapan pagi? Penyelesaian : Bayangkan tiga kali menu nasi goreng sebagai tiga buah bola dan tujuh hari dalam seminggu sebagai 7 buah kotak. Persoalan ini sama dengan menempatkan 3 buah bola ke dalam 7 buah kotak. Banyaknya pengaturan jadwal menu nasi goreng adalah C(7, 3) = 7!/3!4! = 35 cara. String biner yang panjangnya 32 bit disusun oleh angka 1 atau 0. Berapa banyak string biner yang tepat berisi 7 buat bit 1? Penyelesaian : Analogikan 7 bit 1 sebagai 7 buah bola dan 32 posisi bit sebagai 32 buah kotak. Persoalan ini sama dengan memasukkan 7 bola ke dalam 32 kotak, sisanya kosong (0). Banyak string biner yang terbentuk adalah C(32, 7). Sebuah koin yang mempunyai sisi A dan sisi B dilempar ke atas sebanyak empat kali. Berapakah jumlah kemungkinan munculnya sisi A sebanyak tiga kali? Penyelesaian : Ini adalah persoalan dari kombinasi karena kita tidak mementingkan kapan sisi A tersebut muncul. Jadi, jumlah kemungkinan munculnya sisi A sebanyak tiga kali adalah C(4, 3) = 4. Tiga buah apartemen A, B dan C disewakan untuk mahasiswa. Tiap unit apartemen dapat menampung 3 atau 4 orang mahasiswa. Berapa jumlah cara menyewakan apartemen kepada 10 orang mahasiswa? Penyelesaian : Andaikan apartemen A, B, C ditempati masing-masing oleh 4, 3 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 4) x C(6, 3) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 4 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 4) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 3 dan 4 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 3) x C(4, 4) Total seluruh cara menyewakan = C(10, 4)C(6, 3) + C(10, 3)C(7, 4) + C(10, 3)C(7, 3) = 3C(10, 4)C(6, 3). PERMUTASI DAN KOMBINASI BENTUK UMUM P(n;n_1,n_2, ... , n_k) = (P(n,n))/(n_1 !n_(2!…n_k !) ) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini diterapkan untuk menghitung pengaturan (atau pengurutan) n buah objek dari himpunan ganda S (himpunan S terdiri dari n buah objek yang tidak perlu semuanya berbeda). Persamaan tersebut dinamakan permutasi bentuk umum (generalized permutation) terhadap S. C(n;n_1,n_2, ... , n_k) = C(n, n_1) C(n - n_1, n_2) C(n - n_1 - n_2, n_3) . . . C(n - n_1 - n_2 - . . . - n_(k-1), n_k) = n!/(n_(1 ) !(n- n_1 )!) (n-n_(1 ) )!/(n_2 !(n- n_1- n_2 )!) (n- n_1- n_2 )!/(n_3 !(n- n_1- n_2- n_k )!) . . . ((n- n_1- n_2- n_(k-1) )! )/(n_k !(n- n_1- n_2-…- n_(k-1)- n_k )!) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini dinamakan kombinasi bentuk umum (generalized combination). Kita dapat melihat bahwa tidak ada perbedaan antara permutasi bentuk umum dengan kombinasi bentuk umum. Keduanya dapat dihitung dengan rumus yang sama. Jadi, apabila S adalah himpunan ganda dengan n buah objek yang di dalamnya terdiri atas k jenis objek berbeda dan tiap objek memiliki multiplisitas n_1, n_2, . . ., n_k (jumlah objek seluruhnya n_1 + n_2 + . . . + n_k = n), maka jumlah cara menyusun seluruh objek adalah : P(n;n_1,n_2, ... , n_k) = C(n;n_1,n_2, ... , n_k) = n!/(n_1 !n_(2!…n_k !) ) Contoh : 12 lembar karton akan diwarnai sehingga 3 diantaranya berwarna hijau, 2 berwarna merah, 2 berwarna kuning dan sisanya berwarna biru. Berapa jumlah cara pengecatan? Penyelesaian : Diketahui n_1 = 3, n_2 = 2, n_3 = 2, n_4 = 5 dan n_(1 )+ n_2 + n_3 + n_4 = 3 + 2 + 2 + 5 = 12 Jumlah cara pengecatan = P(12; 3, 2, 2, 5) = (P(12,12))/((3!)(2!)(2!)(5!)) = 12!/((3!)(2!)(2!)(5!)) = 166320 cara 12 buah lampu berwarna (4 merah, 3 putih dan 5 biru) dipasang pada 18 buah soket dalam sebuah baris (sisanya 6 buah soket dibiarkan kosong). Berapa jumlah cara pengaturan lampu? Penyelesaian : Diketahui, n = 18; n_1 = 4, n_2 = 3, n_3 = 5 dan n_(4 )= 6 (socket kosong) Jumlah cara pengaturan lampu = P(18; 4, 3, 5, 6) = 18!/((4!)(3!)(5!)(6!)) cara Berapa banyak cara membagikan delapan buah buku berbeda kepada 3 orang mahasiswa, bila Billy mendapat empat buah buku dan Andi serta Toni masing-masing memperoleh 2 buah buku. Penyelesaian : Diketahui n = 8, n_1 = 4, n_2 = 2, n_3 = 2 dan n_(1 )+ n_2 + n_3 = 4 + 2 + 2 = 8 Jadi, jumlah cara membagi seluruh buku = 8!/((4!)(2!)(2!)) = 420 cara KOMBINASI DENGAN PENGULANGAN Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak. Jika masing – masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkan bola ke dalam kotak adalah C(n, r). Jika masing -masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola ke dalam kotak adalah C(n + r – 1, r). C(n + r – 1, r) adalah jumlah kombinasi yang membolehkan adanya pengulangan elemen, yaitu dari n buah objek kita akan mengambil r buah objek, dengan pengulangan diperbolehkan. Pembuktian rumus kombinasi dengan pengulangan tidak disertakan di sini. Perhatikan bahwa C(n + r – 1, r) = C(n + r – 1, n – 1). Contoh : Toko roti ”Enak” menjual 8 jenis roti. Berapa jumlah cara mengambil 1 lusin roti (1 lusin = 12 buah) Penyelesaian : Analogikan 8 jenis roti sebagai 8 kotak. Kita akan mendistribusikan 12 roti itu ke dalam 8 kotak. Setiap kotak mungkin berisi lebih dari 1 buah roti. Di sini n = 8 dan r = 12, maka jumlah cara memilih 12 buah roti itu sama dengan jumlah cara memasukkan 12 buah roti ke dalam 8, yaitu sebanyak C(8 + 12 – 1, 12) = C(19, 12) cara. Andaikan terdapat kumpulan bola yang berwarna merah, biru dan hijau. Jumlah bola dari masing – masing warna paling sedikit jumlahnya 8 buah. Berapa banyak cara memilih 8 buah bola (tanda ada batasan warna)? Berapa banyak cara memilih 8 buahbola jika paling sedikit 1 bola dari masing – masing warna terwakili? Penyelesaian : n = 3, r = 8, maka C(n + r – 1, r) = C(3 + 8 – 1, 8) = C(10, 8) = 45 Ambil terlebih dulu 1 bola dari masing – masing warna, kemudian ambil 5 boal sisanya. Jumlah cara seluruhnya adalah C(3 + 5 – 1, 5) = C(7, 5) = 21 cara. Tiga buah dadu dilempar bersamaan. Berapa banyaknya hasil berbeda yang mungkin? Penyelesaian : C(6 + 3 – 1, 3) = C(8, 3) = 56.

Materi MatDis (Matematika Diskret) : Induksi Matematika

Metode pembuktian untuk proposisi perihal bilangan bulat adalah induksi matematika. Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika. Melalui induksi matematika kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas. Proposisi Perihal Bilangan Bulat Proposisi ini mengkaitkan suatu masalah yang dihubungkan dengan bilangan bulat. Contoh : Kita ingin menemukan rumus jumlah dari n buah bilangan ganjil positif yang pertama. Misalnya untuk n = 1, 2, 3, 4, 5, kita mengamati jumlah n bilangan ganjil positif pertama adalah n = 1 → 1 = 1 n = 2 → 1 + 3 = 4 n = 3 → 1 + 3 + 5 = 9 n = 4 → 1 + 3 + 5 + 7 = 16 n = 5 → 1 + 3 + 5 + 7 + 9 = 25 Setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Untuk semua n ≥ 1, n3 + 2n adalah kelipatan 3. Untuk membayar biaya pos sebesar n sen dolar (n ≥ 8) selalu dapat digunakan hanya perangko 3 sen dan 5 sen dolar. Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali. Jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah n(n – 1)/2 . Banyaknya himpunan bagian yang dapat dibentuk dari sebuah himpunan yang beranggotakan n elemen adalah 2n. Proposisi – proposisi semacam di ataslah yang dapat dibuktikan dengan induksi matematika. Cara pembuktian dengan induksi matematika : Prinsip Induksi Sederhana Prinsip induksi sederhana berbunyi sebagai berikut : Misalkan p(n) adalah proposisi perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan proposisi ini, kita hanya perlu menunjukkan bahwa : p(1) benar, dan jika p(n) benar, maka p(n + 1) juga benar untuk setiap n ≥ 1. Sehingga p(n) benar untuk semua bilangan bulat positif n. Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi. Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar. Asumsi tersebut dinamakan hipotesis induksi. Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Basis induksi digunakan untuk memperlihatkan bahwa pernyataan tersebut benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil. Kemudian kita harus memperlihatkan bahwa implikasi p(n) → p(n + 1) benar untuk setiap bilangan bulat positif. Untuk membuktikan implikasi tersebut benar untuk setiap bilangan bulat positif n, kita perlu menunjukkan bahwa p(n + 1) tidak mungkin salah bila p(n) benar. Hal ini diselesaikan dengan cara memperlihatkan bahwa berdasarkan hipotesis p(n) benar maka p(n + 1) juga harus benar. Perhatikan bahwa dalam induksi matematika kita tidak mengasumsikan bahwa p(n) benar untuk semua bilangan bulat positif. Kita hanya memperlihatkan bahwa jika diasumsikan p(n) benar, maka p(n + 1) juga benar untuk setiap n positif. Pembuktian dengan induksi matematika mirip dapat kita ilustrasikan dengan fenomena yang dikenal dengan efek domino. Sejumlah batu domino diletakkan berdiri dengan jarak ruang yang sama satu sama lain. Untuk merebahkan semua batu domino, kita hanya perlu mendorong domino 1 ke kanan. Jika domino 1 di dorong ke kanan, ia akan mendorong domino 2, domino 2 mendorong domino 3, begitu seterusnya sehingga semua batu domino rebah ke kanan. Contoh : Tunjukkan bahwa untuk n ≥ 1, 1 + 2 + 3 + ... + n = n (n + 1) / 2 melalui induksi matematika. Penyelesaian : Andaikan bahwa p(n) menyatakan proposisi bahwa untuk n ≥ 1, jumlah n bilangan bulat positif pertama adalah n (n + 1) / 2, yaitu 1 + 2 + 3 + ... + n = n (n + 1) / 2. Kita harus membuktikan kebenaran proposisi ini dengan dua langkah induksi sebagai berikut : Basis induksi : p(1) benar, karena untuk n = 1 kita peroleh 1 = 1 (1 + 1) / 2 = 1 (2) / 2 = 2/2 = 1 Langkah induksi : Misalkan p(n) benar, yaitu mengasumsikan bahwa 1 + 2 + 3 + ... + n = n(n + 1)/2 Adalah benar (hipotesis induksi). Kita harus memperlihatkan bahwa p(n + 1) juga benar, yaitu 1 + 2 + 3 + ... + n + (n + 1) = (1 + 2 + 3 + ... + n) + (n + 1) = [n (n + 1)/2 ] + (n + 1) = [ (n2 + n)/2 ] + (n + 1) = [ (n2 + n )/2 ] + [ (2n + 2)/2 ] = (n2 + 3n + 2)/2 = (n + 1)(n + 2)/2 = (n + 1) [ (n + 1) + 1]/2 Karena langkah (a) dan (b) tealh dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ≥ 1, 1 + 2 + 3 + ... + n = n (n + 1)/2. Prinsip Induksi yang Dirampatkan Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n0 . Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa : p(n0) benar, dan jika p(n) benar maka p(n + 1) benar untuk setiap n ≥ n0, sehingga p(n) benar untuk semua bilangan bulat n ≥ n0. Contoh : Buktikan dengan induksi matematika bahwa 3n < n! Untuk n bilangan bulat positif yang lebih besar dari 6. Penyelesaian : Misalkan p(n) adalah proposisi bahwa 3n < n! Untuk n bilangan bulat positif yang lebih besar dari 6. Basis induksi : p(7) benar, karena 37 = 2187 dan 7! = 5040 Langkah induksi : Misalkan bahwa p(n) benar, yaitu asumsikan bahwa 3n < n! Adalah benar. Kita harus menunjukkan bahwa p(n + 1) juga benar, yaitu 3n+1 < (n + 1)!. Hal ini ditunjukkan sebagai berikut : 3n+1 < (n+1)! 3.3n < (n+1) . n! 3n . 3/(n+1) < n! Menurut hipotesis induksi, 3n < n!, sedangkan untuk n > 6, nilai 3?(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan. Efek nettonya, 3n . 3/(n+1) < n! Jelas benar. Karena langkah (a) dan (b) sudah ditunjukkan benar, maka terbukti bahwa 3n < n! untuk n bilangan bulat positif lebih besar dari 6. Prinsip Induksi Kuat Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n0. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa : p(n0) benar, dan jika p(n0), p(n0+1), ..., p(n) benar, maka p(n+1) juga benar untuk setiap bilangan bulat n ≥ n0, sehingga p(n) benar untuk semua bilangan bulat n ≥ n0. Versi induksi yang lebih kuat ini mirip dengan induksi sederhana, kecuali bahwa pada langkah 2 kita mengambil hipotesis induksi yang lebih kuat bahwa semua pernyataan p(1), p(2), ..., p(n) adalah benar daripada hipotesis yang menyatakan bahwa p(n) benar (pada induksi sederhana). Prinsip induksi kuat memungkinkan kita mencapai kesimpulan yang sama meskipun memberlakukan andaian yang lebih banyak. Contoh : Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih ) bilangan prima. Buktikan dengan prinsip induksi kuat. Penyelesaian : Misalkan p(n) adalah proposisi bahwa setiap bilangan bulat positif n (n ≥ 2 ) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Basis induksi : p(2) benar, karena 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri. Langkah induksi. Misalkan p(n) benar, yaitu asumsikan bahwa bilangan 2, 3, ..., n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima (hipotesis induksi). Kita perlu menunjukkan bahwa p(n + 1) benar, yaitu n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Hal ini ditunjukkan sebagai berikut : jika n + 1 sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Jika n + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa. Dengan kata lain, (n + 1)/ a = b atau (n + 1) = ab yang dalam hal ini, 2 ≤ a ≤ b ≤ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab. Karena langkah (a) dan (b) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Bentuk Induksi Secara Umum Bentuk induksi secara umum dapat dituliskan sebagai berikut : Misalkan X terurut dengan baik oleh “<”, dan p(x) adalah pernyataan perihal elemen x dari X. Kita ingin membuktikan bahwa p(x) benar untuk semua x ∈ X. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa: p(x0) benar, yang dalam hal ini x0 adalah elemen terkecil di dalam X, dan jika p(y) benar untuk y < x, maka p(x) juga benar untuk setiap x > x0 di dalam X, sehingga p(x) benar untuk semua x ∈ X. TUGAS : Buktikan bahwa : 1. p(n) : 1 + 4 + 7 + ... + (3n – 2) = (n (3n-1))/2 2. p(n) : 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 3. p(n) : 1.2 + 2.3 + 3.4 + ... + n (n+1) = ([n(n+1)(n+2)])/3 Penyelesaian : 1. p(n) : 1 + 4 + 7 + ... + (3n – 2) = (n (3n-1))/2 p(n+1) : 1 + 4 + 7 + ... + (3n – 2) + (3(n+1)-2) = ((n+1)(3(n+1)-1))/2 (n (3n-1))/2 + (3n+3-2) = ((n+1)(3n+3-1))/2 (n (3n-1))/2 + (3n +1) = ((n+1)(3n+2))/2 (n (3n-1)+2(3n+1))/2 = ((n+1)(3n+2))/2 (3n^2-n+6n+2)/2 = ((n+1)(3n+2))/2 (3n^2+5n+2)/2 = ((n+1)(3n+2))/2 ((3n+2)(n+1))/2 = ((n+1)(3n+2))/2 TERBUKTI 2. p(n) : 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 p(n+1) : 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = (1 + 2 + 22 + 23 + ... + 2n ) + 2n+1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2n+1 – 1 ) + 2n+1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2n+1 + 2n+1 ) - 1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2 . 2n+1 ) - 1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = 2n+2 -1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = 2(n+1)+1 - 1 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 TERBUKTI 3. p(n) : 1.2 + 2.3 + 3.4 + ... + n (n+1) = ([n(n+1)(n+2)])/3 p(n+1) : 1.2 + 2.3 + 3.4 + ... + n (n+1) + (n+1)+(n+1+1) = ([(n+1)(n+2)(n+3)])/3 ([n(n+1)(n+2)])/3 + (n+1)(n+2) = ([(n+1)(n+2)(n+3)])/3 (n[(n+1)(n+2)]=3[(n+1)(n+2)])/3 = ([(n+1)(n+2)(n+3)])/3 ((n+1)(n+2)(n+3))/3 = ([(n+1)(n+2)(n+3)])/3 TERBUKTI