matematika diskrit · iii prakata alhamdulillahirabbil'aalamin, penulis panjatkan sebagai rasa...

iii

PRAKATA

Alhamdulillahirabbil'aalamin, penulis panjatkan sebagai rasa puji dan syukur kepada Allah SWT atas rahmat dan karunia-Nya, Buku Ajar ini dapat terselesaikan mengingat tugas dan kewajiban lain yang bersamaan hadir. Penulis berusaha maksimal untuk bisa menyelesaikan Buku Ajar ini dengan harapan untuk membantu mahasiswa dalam menempuh matakuliah Matematika Diskrit. Buku Ajar ini berisi mengenai materi Matematika Diskrit disertai dengan contoh-contoh mulai dari contoh konsep, contoh soal penalaran dan komunikasi sampai dengan contoh kontekstual yang mudah dipahami oleh mahasiswa. Penulis juga menyajikan soal-soal yang bervariasi dimulai dari soal pemahaman konsep, soal penalaran dan komunikasi hingga soal kontekstual.

Terselesaikannya penulisan Buku Ajar ini juga tidak terlepas dari bantuan berbagai pihak. Penulis mengucapkan banyak terima kepada LPPM Universitas Wisnuwardhana Malang yang telah memberikan dukungan secara moral dan material sehingga penulis termotivasi untuk menyelesaikan Buku Ajar ini. Buku Ajar ini penulis persembahkan untuk suami (Handri Wibowo) dan kedua anak tercinta (Iqbar Aflahans Havilah dan Karima Azzahrahans Aqilasha) yang selalu memberikan doa, motivasi dan telah memberikan banyak inspirasi sehingga terselesaikannya Buku Ajar ini. Meskipun telah berusaha untuk menghindarkan kesalahan, penulis menyadari juga bahwa buku ini masih banyak kelemahan dan kekurangannya. Dengan segala pengharapan dan keterbukaan, penulis menyampaikan rasa terima kasih dengan setulus-tulusnya. Bagi penulis, kritik dan saran pembaca merupakan perhatian agar dapat menuju kesempurnaan.

iv

Akhir kata, penulis berharap agar Buku Ajar ini dapat membawa manfaat kepada pembaca. Secara khusus, penulis berharap semoga Buku Ajar ini dapat menginspirasi mahasiswa agar menjadi generasi yang tanggap, tangguh, bermartabat, kreatif, disiplin dan mandiri.

Malang, November 2018

Penulis

v

DAFTAR ISI

PRAKATA .................................................................................................... iii

DAFTAR ISI................................................................................................. v

KERANGKA BUKU AJAR MATEMATIKA DISKRIT ............... vii

TINJAUAN MATA KULIAH MATEMATIKA DISKRIT ........... xiii

BAB I INDUKSI MATEMATIKA ........................................................ 1

1. Pendahuluan ......................................................................................... 1

2. Notasi Jumlah dan Notasi Kali ...................................................... 1

3. Prinsip Induksi Matematika .......................................................... 4

4. Prinsip Induksi Matematika Kuat ............................................... 7

5. Kesimpulan 1.5 Komponen Graph ............................................. 8

6. Latihan Soal ........................................................................................... 9

BAB II PRINSIP DASAR MEMBILANG.......................................... 14

1. Pendahuluan ......................................................................................... 14

2. Prinsip Dasar Perkalian (The Product Rule and The

Rule Of Product).................................................................................. 14

3. Prinsip Dasar Penjumlahan ........................................................... 15

4. Prinsip Inklusi – Eksklusi ............................................................... 16

5. Prinsip Kandang Merpati (The Pigeonhole Principle,

The Dirichlet Box Principle) .......................................................... 18

6. Kesimpulan ............................................................................................ 20

7. Latihan Soal ........................................................................................... 21

BAB III KOMBINATORIK .................................................................... 24

1. Pendahuluan ......................................................................................... 24

2. Konsep Faktorial ................................................................................. 25

3. Konsep Permutasi dan Kombinasi ............................................. 26

4. Koefisien Bionominal dan Koefisien Multinomial .............. 43

5. Kesimpulan ............................................................................................ 59

6. Latihan soal ........................................................................................... 60

vi

BAB IV FUNGSI PEMBANGKIT ........................................................ 65

1. Pendahuluan ......................................................................................... 65

2. Fungsi Pembangkit Biasa ................................................................ 66

3. Fungsi Pembangkit Eksponensial dan Penerapannya ...... 83

4. Kesimpulan ............................................................................................ 86

5. Latihan Soal ........................................................................................... 88

BAB V PENGANTAR DASAR TEORI GRAPH ............................. 92

1. Pendahuluan ......................................................................................... 92

2. Pengertian Dan Konsep Dasar Teori Graph ........................... 94

3. Jenis-Jenis Graph ................................................................................. 98

4. Keterkaitan Teori Graph dengan Dunia Nyata ..................... 101

5. Kesimpulan ............................................................................................ 104

6. Latihan Soal ........................................................................................... 105

BAB VI KETERKAITAN MATEMATIKA DISKRIT

DENGAN MATEMATIKA SEKOLAH ............................................. 110

1. Pendahuluan ......................................................................................... 110

2. Keterkaitan Materi Matematika Diskrit Dengan Materi

Di Sekolah............................................................................................... 111

3. Perbedaan Dan Persamaan Materi Matematika Diskrit

Dengan Materi Di Sekolah .............................................................. 115

4. Kesimpulan ............................................................................................ 122

5. Latihan Soal ........................................................................................... 123

DAFTAR PUSTAKA................................................................................. 124

SOAL DAN PENYELESAIAN 1 ............................................................. 125




vii

KERANGKA BUKU AJAR MATEMATIKA DISKRIT

Kemampuan Akhir yang

direncanakan Indikator Materi

1. Menerapkan dan membuktikan Prinsip Dasar Matematika (C3, A5)

1.1 Ketepatan penjelasan tentang perbedaan konsep notasi jumlah dan notasi kali

1.2 Ketepatan menyelesaikan masalah tentang notasi jumlah dan notasi kali

1.3 Ketepatan penjelasan tentang prinsip induksi matematika

1.4 Ketepatan langkah membuktikan pernyataan dengan prinsip induksi matematika

Bab I Induksi Matematika

1 Pendahuluan 2 Notasi Jumlah

dan Notasi Kali 3 Prinsip Induksi

Matematika 4 Prinsip Induksi

Matematika Kuat

5 Kesimpulan 6 Latihan Soal

2. Mengklasifikasikan dan mendiskusikan konsep Prinsip Dasar Membilang (C3,

2.1 Ketepatan menjelaskan konsep prinsip perkalian

2.2 Ketepatan

Bab II Prinsip Dasar Membilang

1 Pendahuluan 2 Prinsip

Perkalian

viii

A2) menyelesaikan dan mendiskusikan masalah yang berkaitan dengan prinsip perkalian

2.3 Ketepatan menjelaskan konsep prinsip penjumlahan

2.4 Ketepatan menyelesaikan masalah yang berkaitan dengan prinsip penjumlahan

2.5 Ketepatan menjelaskan konsep prinsip inklusi eksklusi

2.6 Ketepatan menyelesaikan masalah yang berkaitan dengan prinsip inklusi eksklusi

2.7 Ketepatan menjelaskan

3 Prinsip Penjumlahan

4 Prinsip Inklusi Eksklusi

5 Prinsip Sarang Merpati


ix

konsep prinsip sarang merpati

2.8 Ketepatan menyelesaikan masalah yang berkaitan dengan prinsip sarang merpati

3. Menganalisis dan menggunakan Konsep Kombinatorik (C4, P4)

3.1 Ketepatan Menerapkan konsep faktorial dalam pemecahan masalah dengan benar

3.2 Ketepatan Menerapkan konsep permutasi dan konsep kombinasi dalam pemecahan masalah dengan tepat

3.3 Ketepatan Mengklasifikasi konsep permutasi dan konsep kombinasi dalam pemecahan

Bab III Kombinatorik 1 Pendahuluan 2 Konsep

Faktorial 3 Konsep

Permutasi dan Kombinasi

4 Koefisien Binomial dan Teorema Multinomial


x

masalah 3.4 Ketepatan

Menentukan dan Ketepatan menggunakan Koefisien suku dua dan suku banyak dari suatu persamaan

4. Menganalisis dan Memecahkan permasalahan yang berkaitan dengan Fungsi Pembangkit Biasa (C4, A5)

4.1 Ketepatan Menjelaskan konsep Pembangkit Biasa dengan benar

4.2 Ketepatan Menentukan barisan yang dibangkitkan dari suatu fungsi pembangkit biasa

4.3 Kateapatan Menentukan fungsi pembangkit biasa dari barisan

4.4 Ketepatan Menerapkan koefisien dari suatu fungsi pembangkit

4.5 Ketepatan Menganalisis banyaknya

Bab IV Fungsi Pembangkit

1 Pendahuluan 2 Fungsi

Pembangkit Biasa

3 Fungsi Pembangkit Eksponensial dan Penerapannya


xi

cara pemilihan objek atau pengambilan objek dan banyaknya selesaian bilangan bulat

5. Menerapkan dan Menghubungkan Pengantar Teori Graph dengan benar (C3, A4)

5.1 Menjelaskan pengertian dan konsep dasar teori graph

5.2 Menjelaskan jenis-jenis graph

5.3 Mendeskripsikan dan menghubungkan istilah-istilah dalam teori graph dengan kehidupan nyata

Bab V Pengantar Dasar Teori Graph

1 Pendahuluan 2 Pengertian

Dan Konsep Dasar Teori Graph

3 Jenis-Jenis Graph

4 Keterkaitan Teori Graph dengan Dunia Nyata


6. Menganalisis

dengan mengkaitkan materi Matematika Diskrit dengan materi Matematika di Sekolah

6.1 Mengamati keterkaitan materi matematika diskrit dengan materi di sekolah

6.2 Menganalisis perbedaan dan persamaan

Bab VI Keterkaitan Matematika Diskrit dengan Matmatika Sekolah 1 Pendahuluan 2 Keterkaitan

Materi Matematika Diskrit Dengan Materi Di

xii

materi matematika diskrit dengan materi di sekolah

6.3 Membuat laporan

Sekolah 3 Perbedaan dan

persamaan materi matematika diskrit dengan materi di sekolah


xiii

TINJAUAN MATA KULIAH MATEMATIKA DISKRIT:

a. Desksripsi Mata Kuliah : Mata kuliah ini memberikan

dan mendiskusikan beberapa konsep dasar dan

penting dalam matematika diskrit. Matakuliah ini juga

juga memberikan wahana kepada mahasiswa untuk

berlatih berpikir kreatif dalam menyelesaikan suatu

permasalahan diskrit. Dengan mengacu sasaran di atas,

matakuliah ini diberikan dengan menekankan pada

pemberian waktu yang relatif banyak kepada

mahasiswa untuk melakukan problem-solving mulai

dari permasalahan sederhana hingga yang cukup

rumit. Walaupun penyajian matakuliah ini tidak harus

dituntut proof-like, akan tetapi satu atau dua teorema

perlu disajikan serta dibuktikan secara detail untuk

memberikan contoh berargumentasi secara verbal.

Adapun bahan matakuliah ini meliputi: Induksi

Matematika, Prinsip Dasar Membilang, Kombinatorik,

Fungsi Pembangkit, Pengantar Dasar Teori Graph dan

Keterkaitan Matematika Diskrit dengan Mata Pelajaran

Matmatika di SD, SMP dan SMA

b. Manfaat Mata Kuliah : Meningkatkan kemampuan

mahasiswa dalam bereksplorasi, studi kasus per kasus,

berargumentasi, dan kemampuan problem-solving,

xiv

selain itu juga untuk memberikan kesempatan

mahasiswa berlatih menulis argumentasi atau

berargumentasi secara verbal.

c. Capaian Pembelajaran : Mahasiswa Mampu

Menyimpulkan Konsep Fungsi Pembangkit Biasa Dan

Mahir Dalam Menyelesaikan Masalah Yang Berkaitan

Dengan Konsep Kombinatorik, Serta Mampu

Membuktikan Pernyataan Berdasarkan Prinsip Induksi

Matematika. (C6, P5, A5).

d. Kemampauan Akhir yang direncanakan :

1. Menerapkan dan membuktikan Prinsip Dasar

Matematika (C3, A5)

2. Mengklasifikasikan dan mendiskusikan konsep

Prinsip Dasar Membilang (C3, A2)

3. Menganalisis dan menggunakan Konsep

Kombinatorik (C4, P4)

4. Menganalisis dan Memecahkan permasalahan yang

berkaitan dengan Fungsi Pembangkit Biasa (C4, A5)

5. Menerapkan dan Menghubungkan Pengantar Teori

Graph dengan benar (C3, A4)

6. Menganalisis dengan mengkaitkan materi

Matematika Diskrit dengan materi Matematika di

Sekolah.

1

BAB I INDUKSI MATEMATIKA

1. Pendahuluan

Induksi matematika memiliki prinsip menjadikan

suatu alat berharga untuk membuktikan hasil-hasil yang

terkaik dengan bilangan bulat atau hubungan tertentu

yang dapat diperluas. Hal ini berlaku untuk semua

bilangan asli hasil-hasil yang terkait, terutama tentang

penjumlahan dan hubungan tertentu, dapat berupa

ketidaksamaan, keterbagian, atau diferensial.

Dalam kaitanya dengan hasil penjumlahan, prinsip

induksi matematika melibat notasi jumlah (summation)

dan notasi kali (products). Kedua notasi ini sangat

bermanfaat untuk menyederhanakan tulisan sehingga

menjadi lebih singkat dan lebih mudah dipahami.

Materi dalam modul ini meliputi konsep prinsip

induksi matematika, prinsip induksi matematika kuat,

dan disertai dengan soal-soal latihan untuk

mempermudah peserta didik memahami konsep.

2. Notasi Jumlah dan Notasi Kali

Notasi jumlah adalah notasi yang di lambangkan ∑,

dan notasi kali adalah notasi yang dilambangkan dengan

∏, dan didefinisikan sebagai :

2

∑ =x1 + x2 +.....xt

∏

Huruf dari indeks jumlah notasi atau notasi kali

disebut variabel dummy karena dapat diganti oleh

sebarang huruf,misalnya :

∑

∑

∑

∏

∏

∑

i = 1 di sebut batas bawah (lower limit) dan i = r disebut

batas atas (upper limit).

Contoh 1.1

a. ∑ =1+2+3+4 = 10

b. ∏ =1.2.3.4 = 24

c. ∑ =3+3+3+3+3 = 15

d. ∏ =3.3.3.3.3 = 243

e. ∑ =12+22+32 = 14

f. ∏ =12.22.32 = 36

Selanjutnya, indeks jumlah tidak harus.dimulai

dari 1,artinya dapat dimulai dari bilangan bulat selain

3

dari bilangan bulat selain 1 asalkan batas bawah tidak

melebihi batas atas.

Contoh 1.2

a. ∑ =3+4+5=12

b. ∑ = (2.2-1)+(2.3-1)+(2.4-1)+ (2.5-

1)+(2.6-1)= 35

c. ∏ 2k = 22.23.24 = 4.8.16 = 572

d. ∏ (t-1) = (2-1) (3-1) (4-1) = 1.2.3 = 6

Berapa sifat yang terkait dengan notasi jumlah

adalah :

1) ∑ = tx1+tr+1+......+tx5

= t(x1xr+1+.......+x5)

= t∑ x1

2) ∑ (xi +y1) = (xr + yr)+(xr+1 + yr+1)4

= (xr + xt=1 +.........x1) + (yt + yt+1

+........+y5)

= ∑ x1 + ∑

yi

3) ∑ ∑

x1y1 = ∑ (xi ∑

yi )

=∑ x1(yc + yc+1+.......+yd)

=xa(yc +yc+c....+yd) + x8+1(yc + yc+1

+.....+yd) +.....+ xb (yc

+yc+1+.......+ yd)

=[ ∑ x1 ] [ ∑

yj ]

4

4) ∑ ∑

xi yi =[ ∑ xj] [ ∑

y1]

=[ ∑ yj] [ ∑

xt]

=∑ yj ∑

yj

=∑ ∑

xi yj

Contoh 1.3

a. ∑ 2x1 =2x3 + 2 x4+ 2x5 =2(x3 + x4 +x5) =2 ∑

xi

b. ∑ (2a1 + 3b1) = (2a2 + 3b2) +(2a3 + 3b2) + (2a4 +

3b4)

= (2a2 + 2a3 + 2a4) + (3b2 + 3b3) +

(3a4 +3b4)

=2 (a2 +a3 + a4) + (b2 + b3 + b4)

=2 ∑ a1 + 3 ∑

b1

c. ∑ ∑

ij2 = ∑

(i.12 + i.22)

=∑ 5i = 5.1 + 5.2 +5.3 =30

d. ∑ ∑

ij2 =∑ (i.j2 + 2.j2 + 3.j2)

= ∑ 6j2= 6.12

3. Prinsip Induksi Matematika

Sebuah cara pembuktian yang sering dipakai,

simple, dan sangat anmpuh di dalam matematika

kombinatorial dan ilmu computer, dikenal dengan

5

prinsip induksi matematika. Dalam menggunakan

prinsip induksi matematika pada suatu pernyataan

tertentu yang melibatkan suatu bilangan asli n terdapat

dua langkah yang biasa digunakan.

a. Langkah pertama dinamakan basis induksi, yaitu

dimana kita memiliki pernyataan dasar seperti,

sebuah pernyataan benar untuk n = n0

b. Langkah kedua dinamakan langkah induksi, yaitu

sebuah pernyataan lanjutan yang membantu untuk

menyimpulkan seperti, sebuah pernyataan benar

untuk n = k+1

c. Selain itu terdapat hipotesis induksi, yaitu sebuah

asumsi terhadap langkah induksi bahwa pernyataan

tersebut benar dalam suatu kondisi tertentu semisal,

pernyataan

Dengan memperhatikan langkah-langkah tersebut

maka kita dapat menyimpulkan bahwa pernyataan

tersebut benar untuk semua bilangan asli .

Kita perhatikan bahwa prinsip induksi matematika

merupakan akibat langsung dari definisi bilangan asli.

Perhatikan suatu himpunan S yang mempunyai sifat

a. Bilangan asli n0 ada di dalam S

b. Jika bilangan asli k ada di dalam S, maka bilangan

asli k+1 juga ada di dalam S, (k ≥ n0)

6

Berdasarkan difinisi himpunan bilangan asli, kita

dapat menyimpulkan bahwa S, mengandung semua

bilangan asli yang lebih besar atau sama dengan n0. Akan

tetapi, sesungguhnya inilah yang dinyatakan oleh prinsip

induksi matematika ketika kita mengambil S sebagai

himpunan bilangan asli yang membuat pernyataan yang

diberikan tadi benar.

Contoh 1.4

Buktikan bahwa 12 + 22 + 32 + … + n2 =

Untuk semua n ≥ 1

Solusi

a. Basis induksi, untuk n = 1, kita peroleh 12 =

adalah pernyataan yang benar

b. Langkah induksi, misalkan bahwa

12 + 22 + 32 + … + k2 =

adalah benar, maka

kita peroleh

( )

7

Bacalah dari pernyataan pertama hingga pernyataan

terakhir, rangkaian kesamaan ini merupakan pernyataan

untuk . Jadi kebenaran pernyataan untuk

secara tidak langsung menyatakan kebenaran pernyataan

untuk . Berdasarkan prinsip induksi

matematika, terbukti benar untuk setiap bilangan positif

.

4. Prinsip Induksi Matematika Kuat

Merupakan bentuk prinsip matematika yang lebih

kuat dimana di dalam langkah induksi, untuk

membuktikan bahwa pernyataan yang bersangkutan

benar untuk , kita dapat membuat asumsi

yang lebih kuat dengan memberlakukan asumsi yang

lebih banyak untuk mendapatkan kesimpulan.

Semisal kita akan memperlihatkan bahwa setiap

bilangan positif n yang lebih besar atau sama dengan 2

merupakan bilangan prima atau hasil kali beberapa

belangan prima.

a. Basis induksi, untuk , karena 2 adalah bilangan

prima, pernyataan tersebut benar

b. Langkah induksi, misalkan bahwa pernyataan

tersebut benar untuk sembarang bilangan bulat n,

8

. untuk bilangan bulat jika

bilangan prima, maka pernyataan itu benar. Jika

bukan bilangan prima, maka dapat ditulis

sebagai pq, dengan dan menurut

hipotesis induksi, p dan q merupakan bilangan prima

atau hasil kali beberapa bilangan prima. Ini berarti pq

adalah hasil kali beberapa bilangan prima

5. Kesimpulan

Dalam pembahasan BAB I ini mempelajari pokok-

pokok materi perkuliahan,yaitu :

1. Penggunaan notasi jumlah dan noptasi kali.

2. Penggunaan variabel dummy.

3. Sifat-sifat notasi jumlah.

4. Prinsip induksi matematika.

5. Pembuktian hubungan jumlah deret dengan induksi

matematika.

6. Pembuktian hubungan pertidaksamaan dengan

induksi matematika.

7. Pembuktian hubungan keterbuktian dengan induksi

matematika.

8. Pembukatian hubungan diferensial dengan induksi

matematika.

9

6. Latihan Soal

Buktikan dengan induksi matematika

1. n < 2n untuk semua Z+

2. n3 - n habis dibagi 3 untuk semua n Z+

3. 2n < ! untuk setiap bilangan bulat positif n ≥ 4

4. Di dalam baris harmonis :

1 +

+

+

+.....

Berlaku

112+ ≥ +

,untuk setiap bilangan bulat n ≥ 0

5.

= nxn-1 untuk setiap bilangan bulat n ≥ 0

6. ∑

=

+

+.....

=

7. ∑ t2 =12 + 22 + 32 +.....+ r2 =

r (r + 1)(2r +1)

untuk setiap r Z+

8. ∑

=

Dengan hubungan menggunakan hubungan :

)

Petunjuk jawaban latihan

1. S(n) : n < 2n

S(1) : benar sebab untuk n =1 :

, dan 1 < 2

10

Misalkan S(k) benar,yaitu

Haruskan dibuktikan bahwa benar, yaitu

Jadi untuk setiap n Z+

2. – habis dibagi oleh 3

S(1) benar sebab untuk :

– dan 0 habis dibagi

oleh 3.

Misalkan S(k) benar,yaitu habis dibagi oleh 3

Harus dibuktikan bahwa benar,yaitu

– habis dibagi oleh 3

– –

habis dibagi 3 sebab

mempunyai faktor 3

Jadi : habis dibagi 3 untuk setiap n Z+

11

3. Untuk setiap bilangan bulat positif

S(4) benar sebab untuk n = 4

2 - 24 = 16 ,n! = 14! = 24,dan 16 < 24

Harus dibuktikan bahwa benar yaitu :

Sebab untuk sebarang

Jadi : , Untuk setiap bilangan asli n

4. S(n) : H2n ≥ 1 +

untuk setiap bilangan bulat n ≥ 0

H1 =1 +

H4 =1 +

+

S(0) benar sebab untuk n=0

H2o – H1 = 1 + 1 +

= 1 + 0,dan 1 ≥ 0

Misalkan H2k benar yaitu untuk n = k :

H2k ≥ 1 +

Harus dibuktikan H2k+1 benar,yaitu untuk n = k + 1 :

H2k+1 ≥ 1 + (k+1)/2

H2k+1 = 1 +

12

= H2k +

≥ (1 +

) +

≥ (1 +

) +2k

Sebab terdapat 2n suku masing-masing tidak kurang

dari

≥ (1 +

) +

Jadi H2k+1 ≥ 1 +

(n+1) untuk sebarang bilangan

bulat

5. S(n) :

nxn-1 untuk sebarang bilangan bulat n ≥ 0

S(0) benar sebab

nxn-1 = 0.x4 = 0

Misalkan S(k) benar, yaitu

= kxk-1

Harus dibuktikan S(k+1) benar, yaitu

= (k + 1) xk

= lim

maka

△x→0

= lim

△x→0

= lim

△x→0

= lim – –

△x→0

13

= lim

△x→0

= xk xk.1 + xk

= kxk + xk

= (k + 1) x4

6. Cara 1 : Gunakan hubungan :

Untuk mengganti setiap suku deret,cara ini disebut

cara teleskopis

Cara 2 : Gunakan induksi matematika tunjukan :

7. Tunjukan bahwa

+ (k + 1)2 =

8. ∑

= ∑

(

∑

=

∑ ,

-

=

∑ (

∑ (

=

(

)

=

14

BAB II PRINSIP DASAR MEMBILANG

1. Pendahuluan

Membilang (enumerating, counting) bukan sekedar

aritmatika biasa karena sasaran yang dipelajari

memasuki berbagai bagian matematika, antara lain

probabilitas, statistika, analisis algoritma, dan aljabar.

Kejadian dalam kasus-kasus tertentu dicacah (dihitung)

berdasarkan cara-cara khusus untuk menyelesaikan

masalah yang beragam.

Beberapa masalah yang terkait dalam enumerasi

atau membilang antara lain adalah permutasi, kombinasi,

binomial, multinomial dan kandang merpati. Dalam

banyak hal, masalah enumerasi memerlukan prinsip-

prinsip khusus untuk membantu pengembangan teori-

teorinya, antara lain adalah prinsip penjumlahan, dan

perkalian, dan prinsip kandang merpati (pigeonhole

principle).

2. Prinsip Dasar Perkalian (The Product Rule, The

Rule Of Product)

Jika suatu pekerjaan dapat dipisah menjadi dua

pekerjaan, yaitu pekerjaan pertama yang dapat dilakukan

dalam n1 cara dan pekerjaan kedua yang dapat

15

dikerjakandalam n2 cara setelah pekerjaan pertama

dilakukan, maka seluruh pekerjaan dapat dilakukan

dalam n1 x n2 cara.

Contoh 2.1

Seorang pemuda mempunyai 4 baju dan 3 celana.

Banyaknya cara berpakaian pemuda itudapat dipisah

menjadi memakai baju, dilanjutkan dengan memakai

celana (atau sebaliknya) Jika baju pertama terpilih, maka

ada 3 cara memilih celana pasangannya, berarti ada 3

cara berpakaian. Jika baju kedua terpilih, maka ada 3

memilih celana pasangannya, berarti ada 3 cara

berpakaian.

Demikian seterusnya, sehingga banyaknya cara

berpakaian adalah cara.

3. Prinsip Dasar Penjumlahan (The Sum Rule, The

Rule Of Sum)

Jika suatu pekerjaan pertama dapat dilakukan

dalam n1 cara dan suatu pekerjaan kedua dapat dilakukan

dalam n2 cara, dan kedua pekerjaan tidak dapat terjadi

dalam waktu yang bersamaan, maka seluruh pekerjaan

dapat dilakukan dalam cara

16

Contoh 2.2

Suatu jurusan matematika harus mengirimseorang

wakil untuk mengikuti suatu pertemuan ilmiah yang

diambil dari kelompok dosen yang berjumlah 50 atau

kelompok mahasiswa yang berjumlah 400.

Dari masalah ini dapat diketahui bahwa pekerjaan

pertama adalah memilih 1 dosen, dan pekerjaan ini dapat

dilakukan dalam 50 cara, serta pekerjaan yang kedua

adalah memilih 1 mahasiswa dari 400 mahasiswa, dan

pekerjaan ini dapat dilakukan dalam 400 cara.

Pekerjaan yang pertama dan pekerjaan yang kedua

tidak dapat terjadi bersama-sama karena perwakilan

yang dikirim hanya 1 orang. Banyak cara memilih seorang

wakil adalah cara.

4. Prinsip Inklusi – Eksklusi

Prinsip penjumlahan digunakan untuk mencari

banyaknya unsur-unsur dari himpunan yang lepas. Untuk

mencari banyaknya unsur-unsur dari himpunan-

himpunan yang tidak lepas (disjoint, saling asing)

digunakan Prinsip Inklusi-Eksklusi

17

Teorema 2.3

Jika A dan B adalah himpunan-himpunan bagian

terhingga dari himpunan semesta S dan ., maka

: | | | | | | | |

Teorema 2.2

Jika A, B dan C adalah himpunan-himpunan bagian

terhingga dari himpunan semesta S dan ketiganya tidak

saling asing, maka: | | | | | | | |

| | | | | | | |

Contoh 2.3

Dari suatu kelas 6 SD diketahui bahwa terdapat 23 orang

siswa yang senang matematika, 13 orang siswa senang

IPA dan 8 orang siswa senang matematika dan IPA.

Berapa banyaknya siswa di kelas 6 SD tersebut?

Jawab:

Misalkan A adalah himpunan siswa yang senang

matematika dan B adalah himpunan siswa yang senang

IPA, maka | | | | | |

| | | | | | | |

Jadi banyaknya siswa kelas 6 SD tersebut adalah 30

orang.

18

5. Prinsip Kandang Merpati (The Pigeonhole

Principle, The Dirichlet Box Principle)

Prinsip kandang merpati merupakan prinsip yang

dapat digunakan untuk mengetahui perhitungan minimal

hasil membilang dari suatu keadaan yang sedang

berlangsung. Meskipun jawaban terdapat suatu masalah

dengan menggunakan prinsip ini dapat mengundang

keragu-raguan, jawaban itu merupakan estimasi yang

paling tepat terutama dalam menduga atau

memperkirakan nilai terkecil yang harus dipenuhi.

Secara sederhana peragaan dari prinsip kandang

merpati menyebutkan bahwa jika jumlah merpati lebih

banyak dari jumlah kandang mereka (semua merpati

masuk kandang, dan setiap kandang memuat setiap

merpati), maka paling sedikit ada satu kandang yang

berisi paling sedikit dua merpati.

Teorema 2.3

Jika atau lebih objek yang dimasukkan ke dalam

kotak, maka paling sedikit ada satu kotak yang berisi satu

atau lebih objek.

Contoh 2.4

Dari 8 orang yang tersedia, tentu paling sedikit ada 2

orang yang lahir pada hari yang sama. Keadaan ini dapat

19

dijelaskan sebagai 8 objek yang di masukkan ke dalam 7

kotak (nama-nama hari dalam 1 minggu).

Ini berarti paling sedikit ada 1 kotak (hari) yang berisi

paling sedikit 2 orang.

Sebelum membahas teorema berikutnya, marilah

kita lihat dua fungsi penting dalam matematika diskrit,

yaitu fungsi lantai dan fungsi atap.

⌊ ⌋ disebut fungsi lantai (floor function)= bilangan

bulat terbesar kurang dari atau sama dengan x.

⌈ ⌉ disebut fungsi atap (ceiling function) =

bilangan bulat terkecil lebih dari atau sama dengan x.

Contoh 2.5

⌊

⌋ bilangan bulat terbesar kurang dari atau sama

dengan

.

⌈

⌉ bilangan bulat terkecil lebih dari atau sama dengan

.

Teorema 2.4

Jika N objek dimasukkan dalam k kotak, maka paling

sedikit ada satu kotak yang berisi paling sedikit ⌈

⌉ objek.

20

Contoh 2.6

Terdapat 23 objek untuk dimasukkan dalam 10 kotak,

maka ⌈

⌉ ⌈ ⌉

⌈

⌉ ⁄ dan ⌈

⌉ ⌈

⌉

Anggaplah bahwa tidak satupun kotak yang berisi paling

sedikit ⌈

⌉ ⌈ ⌉=3 kotak, atau tidak satupun kotak

yang berisi lebih dari ⌈

⌉ .

Maka banyaknya seluruh objek maksimal adalah

⌈

⌉ ((⌈

⌉ ) )

Hal ini bertentangan karena banyaknya seluruh objek

adalah 23.

6. Kesimpulan

Pokok-pokok pembahasan dalam BAB II yang

perlu dipahami adalah

1. Pengertian prinsip perkalian

2. Pengertian prinsip penjumlahan

3. Penerapan prinsip perkalian untuk membilang

banyaknya cara untuk sesuatu yang dikerjakan

4. Penerapan prinsip perkalian untuk membilang

banyaknya cara untuk sesuatu yang dikerjakan

21

5. Penerapan prinsip penjumlahan dan perkalian untuk

membilang banyaknya cara sesuatu dikerjakan

7. Latihan Soal

1. Seorang siswa diminta untuk memilih 1 tugas untuk

dikerjakan, dari dua daftar tugas yang masing-masing

terdiri dari 15 soal dan 25 soal. Berapa banyak cara

untuk memilih tugas untuk dikerjakan?

2. Pada rak buku tersedia 5 buku geometri, 3 buku

aljabar dan 2 buku kalkulus. Berapa banyak cara

seseorang mengambil satu buku dari rak tersebut?

3. Kursi-kursi dalam suatu aula akan ditandai dengan

satu huruf dan satu bilangan asli yang tidak lebih dari

75. Berapa banyak seluruh kursi yang dapat ditandai?

4. Memori utama setiap computer disimpan dalam sel

memori yang disebut alamat (address). Setiap alamat

dinyatakan dalam daftar susunan lambing bilanga 0

dan 1, satu lambing 0 atau 1 disebut bit. Jika setiap

alamat mempunyai 8 lambang (8 bit atau 1byte),

maka berapa banyaknya alamat yang tersedia?

5. Mencari banyaknya fungsi yang dapat dibuat dari A

yang mempunyai 2 unsur, ke B yang mempunyai 3

unsur. Berapa banyak fungsi yang dapat dibuat?

22

6. Mencari banyaknya fungsi 1-1 (one-to-one, injektif)

dari A yang mempunyai 2 unsur, ke B yang

mempunya 3 unsur. Berapa banyaknya fungsi yang

dapat dibuat?

7. Seseorang akan membuat susunan angka-angka

menjadi bilangan bulat positif. Jika bilangan-bilangan

itu terdiri dari satu angka susunan dua angka, atau

sususnan tiga angka, dan untuk susunan dua atau tiga

angka tidak ada angka yang berulang dan tidak ada

susunan yang dimulai dengan nol, maka berapa

banyaknya seluruh susunan yang dapat dibuat?

8. Plat nomor kendaraan bermotor suatu Negara

dimulai dengan satu atau dua huruf, dan diikuti

dengan tiga angka. Berapa banyaknya plat nomor

yang tersedia?

9. Dari semua 200 orang siswa di suatu sekolah dasar,

terdapat 95 orang siswa yang suka olah raga bulu

tangkis, 85 orang siswa suka olah raga sepak bola,

dan 30 orang siswa suka olah raga keduanya. Berapa

banyaknya siswa yang yang tidak suka olah raga

keduanya?

10. Dalam suatu ujian, skor yang digunakan guru dalam

memeriksa pekerjaan siswa dengan menggunakan

skala 1 sampai 10. Jika paling sedikit ada dua orang

23

siswa yang mempunyai skor sama, maka minimal

berapa banyak banyak peserta ujian?

11. ⌊ ⌋ dan ⌈ ⌉ artinya?

12. ⌊

⌋ dan ⌈

⌉ artinya?

13. Dari 200 orang siswa sekolah dasar, paling sedikit

ada berapa orang siswa yang lahir pada bulan sama?

24

BAB III KOMBINATORIK

1. Pendahuluan

Kombinatorik memuat konsep dan aturan yang

terkait dengan membilang banyaknya seluruh susunan,

banyaknya seluruh cara dalam pengambilan unsur secara

berkelompok melalui suatu prosedur acak, atau pencarian

koefisien suku tertentu dalam binominal dan

multinominal.

Kombinatorik yang relevan dengan pengembangan

materi meliputi permutasi (linier dan melingkar dengan

pengulangan), kombinasi (tanpa pengulangan, dengan

pengulangan), dan koefisien binominal (yang kemudian

diperluas dengan koefisien multinominal).

Penjelasan materi dikaitkan dengan susunan

angka menjadi bilangan dengan menggunakan syarat

tertentu, susunan huruf atau obyek yang memuat unsur-

unsur sama, susunan melingkar yang memperhatikan

urutan tertentu, menjelaskan notasi faktorial, permutasi,

kombinasi, koefisien binominal, dan kombinasi dan

penerapannya.

25

Standar Kompetensi

Mahasiswa mampu memahami konsep dan

penerapan dari kombinatorik, serta keterkaitannya

dengan bagian matematika yang lain dan kehidupan

sehari-hari.

Notasi Faktorial

2. Konsep Faktorial

DefInisi: Untuk suatu bilangan bulat n , n! ( dibaca : n

faktorial ) didefenisikan sebagai berikut :

– –

Contoh 3.1

–

– –

– – –

– – – –

Contoh 3.2

7 . 6 . 5 = 7 . 6 . 5

( n + 1 )!= (n + 1) (n + 1 – 1 )( n + 1 – 2 ) ... 3 . 2 . 1

26

= ( n + 1 ) . n( n – 1 ) ... 3 . 2 . 1

= ( n + 1 ) . n!

3. Konsep Permutasi dan Kombinasi

3.1 Permutasi

Definisi: Susunan r unsur dari n unsur yang

memperhatikan ururtan ( 1 disebut permutasi

r unsur dari n unsur. Banyaknya permutasi r dari n unsur

dinyatakan dengan P(n, r).

Contoh 3.3

Beberapa permutasi 4 dari 1, 2, 3, dan 4 adalah 1234,

4231, 3142, dan 2413

27

Beberapa permutasi 3 dari 1, 2, 3, dan 4 adalah 312, 421,

432, dan 134

Beberapa permutasi 2 dari 1, 2, 3, dan 4 adalah 42, 34, 21,

dan 13

Contoh 3.4

Banyaknya bilangan tersusun dari 3 angka berbeda dari

angka – angka 1, 2, 3, 4, dan 5 adalah P(5,3)

P(5,3) dapat dicari dengan menggunakan prinsip

perkalian. Pekerjaan mencari banyaknya susunan tiga

angka dapat dipilih menjadi pekerjaan pertama memilih

angka pertama, pekerjaan kedua memilih angka kedua,

dan pekerjaan ketiga memilih angka ketiga.

Pekerjaan memilih angka pertama dapat dilakukan

dengan 5 cara, yaitu memilih angka 1, 2, 3, 4, atau 5

Pekerjaan memilih angka kedua dapat dilakukan dengan

4 cara, 1 angka dari angka – angka 1, 2, 3, 4, 5 yang telah

dipilih pada angka pertama tidak boleh dipilih kembali.

Pekerjaan memilih angka ketiga dapat dilakukan dengan

3 cara, 2 angka dari amgka – angka 1, 2, 3, 4, 5 yang telah

dipilih pada angka pertama dan angka kedua tidak boleh

dipilih lagi.

Dengan demikian :

28

P(5,3) = 5 . 4 . 3 =

Teorema 3.1

P ( n,r) =

Bukti :

P(n,r) dapat dicari dengan menggunakan prinsip

perkalian. Karena terdapat r unsur dalam setiap susunan,

maka mencari P(n, r) dapat dipilah menjadi r pekerjaan,

yaitu memilih unsur pertama, kedua, ... , ke – r

Pekerjaan pertama dapat dilakukan dalam n = n – 1 + 1

cara

Pekerjaan kedua dapat dilakukan dalam n – 1 = n – 2 + 1

cara

Pekerjaan ketiga dapat dilakukan dalam n – 2 = n – 3 + 1

cara

Pekerjaan ke – r dapat dilakukan dalam ( n – r + 1 ) cara

Jadi:

– – –

= n(n – 1)(n – 2) ... (n – r +1)

=

=

29

Catatan : jika n = r, maka P(n, r) = P(n, n) =

Contoh 3.5

a. Nilai n dari P(n, 1) = 5 dapat dicari sebagai berikut

P(n, 1) =

5, berarti n = 5

b. Nilai n dari P(n, 2) = 90 dapat dicari sebagai berikut :

P(n, 2) =

=

n(n – 1) = 90 atau atau (n – 10)(n +

9) = 0 atau n = 10 dan n = 9

karena n maka n = 10

c. Nilai n dari P(n, 4) = 42 P(n, 2) dapat dicari sebagai

berikut:

=

=

– – – –

– – atau

atau

– atau karena n

30

Contoh 3.6

Jika pengulangan angka tidak boleh dilakukan, maka

banyaknya bilangan tersusun dari 3 angka 3, 4, 5, 7, dan

8:

a. Adalah dicari sebagai berikut:

angka ke – 1 angka ke – 2 angka ke – 3

yaitu 5. 4. 3 = 60

b. Yang kurang dari 600 adalah dicari sebagai berikut:


yaitu 3 . 4 . 3 = 36

c. Yang habis dibagi 5 adalah dicari sebagai berikut:


yaitu 4 . 3 . 1 = 12

d. Yang habis dibagi 4 adalah dicari sebagai berikut:

Suatu bilangan habis dibagi 4 jika 2 angka terakhir

dari lambang bilangannya habis dibagi 4.

Dengan demikian kedua angka terakhir adalah 48

atau 84, sehingga tinggal mencari angka pertama.

Prinsip penjumlahan dan prinsip perkalian digunakan

bersama untuk memperoleh jawaban

Kotak angka pertama mempunyai 3 . 4 8

5

4 3

3 4 3

4 3 1

31

pilihan

Kotak angka pertama mempunyai 3

pilihan

Banyaknya bilangan yang habis dibagi empat adalah : 3 . 1

. 1. + 3 . 1 . 1 = 3 + 3 = 6

Contoh 3.7

Terdapat sejumlah 4 pria dan 3 wanita duduk dalam

sebaris 7 kursi

Banyaknya cara duduk adalah ( 4 + 3 ) = 7! = 5040

Banyaknya cara duduk jika pria berkumpul pria dan

wanita berkumpul wanita adalah dicari sebagai berikut:

Ada 2 kemungkinan cara duduk:

PPPP WWW dan WWWPPPP (P = Pria, W = Wanita)

Dengan menggunakan prinsip penjumlahan dan

perkalian, keadaan PPPP WWW terjadi dalam 4! 3! Dan

keadaan WWWPPPP terjadi dalam 3! 4! Sehingga

banyaknya seluruh keadaan duduk adalah

4! 3! + 3! 4! = 2 . 3! 4! = 288

Banyaknya cara duduk jika pria saja yang boleh duduk

ditepi dan semua wanita harus bergerombol dapat dicari

sebagai berikut :

PWWWPPP

PPWWWPP

. 8 4

32

PPPWWWP

Banyaknya seluruh keadaan duduk adalah 4!3! + 4!3! +

4!3! = 3 . 4!3! = 432 cara

Contoh 3.8

Banyaknya semua kata yang disusun dari huruf – huruf

kata ANDA dapat dicari sebagai berikut:

1. Jika semua huruf kata ANDA dianggap berbeda, maka

untuk membedakan A yang pertama dan A yang kedua

digunakan indeks yaitu A1 dan A2. Banyaknya semua

huruf yang dapat dibentuk adalah 24, yaitu :

A1NDA2 A1DA2N NA1A2D DA1A2N

A2NDA1 A2DA1N NA2A1D DA2A1N

A1A2D A1A2ND NA1DA2 DA1NA2

A2NA1D A2A1ND NA2DA1 DA2NA1

A1DNA2 A1A2DN NDA1A2 DNA1A2

A2DNA1 A2A1DN NDA2A1 DNA2A1

2. Jika sekarang indeks – indeks A dibuang, maka

terdapat sepasang – sepasang kata yang susunannya

sama. Dengan demikian banyaknya semua kata yang

dibentuk adalah 24/2 = 12, yaitu ANDA, ANAD, ADNA,

ADAN, AAND, AADN, NAAD, NADA, NDAA, DAAN,

DANA, dan DNAA .

33

Contoh 3.9

a. Banyaknya susunan dua huruf yang berbeda adalah 2

b. Banyaknya susunan dua huruf yang sama adalah 2/2

=1

c. Banyaknya susunan tiga huruf yang berbeda adalah 6

Banyaknya susunan tiga huruf yang sama adalah 6/6 =

1

Banyaknya susunan empat unsur yang berbeda adalah

24

Banyaknya susunan empat unsur, dua unsur pertama

sama dan dua unsur kedua sama, dapat diperagakan dari

susunan huruf – huruf kata NANA

Setiap kata NANA mewakili empat kata NANA berindeks,

yaitu: N1A1N2A2 N2A1N1A2 N1A2N2A1 dan N2A2N1A1

Keadaan ini berlaku untuk keadaan yang lain, misalnya

NAAN, ANNA, dan ANAN

Jadi banyaknya semua kata adalah 24/4 = 6, yaitu NANA,

NAAN, NNAA, ANNA, ANAN, dan AANN

Permutasi pada contoh 1.6 dan contoh 1.7 disebut

permutasi dengan unsur sama.

Contoh 3.10

Banyaknya cara 3 orang A, B, dan C duduk pada tiga kursi

dari meja yang melingkar dapat dicari sebagai berikut:

34

1. Jika hanya memperhatikan urutan orangnya ( tidak

memperhatikan kursinya ) maka cara duduk mereka

ada dua, seperti diagram:

Cara duduk 1, 3, dan 5 dipandang sama, yaitu cara

ABC, dan cara – cara duduk 2, 4, dan 6 dipandang

sama , yaitu ACB

2. Jika selain memperhatikan urutan orang juga

memperhatikan urutan kursi, maka cara duduk

mereka seperti diagram berikut:

Cara-cara duduk pada (1), (2), (3),(4), (5) dan (6)

adalah berbeda, sehingga banyaknya cara duduk

seharusnya adalah 6.

Permutasi pada contoh ini disebut permutasi

melingkar.

35

3.2 Kombinasi

Definisi: susunan r unsur dari n unsur yang tanpa

memperhatikan urutan ( 1≤ r ≤ n ) di sebut kombinasi r

unsur dari n unsur .

Banyaknya kombinasi r unsur dari n unsur di nyatakan

Contoh 3.11

a. Memilih 2 pria dari 5 pria.

b. Memilih 3 pria dari 7 pria , dan 5 wanita dari 8 wanita

c. Memilih 8 soal dari 10 soal untuk di kerjakan.

Jawab

a.

=

=

=

b.

c.

=

=

cara

Contoh 3.12

1. Seorang ingin melakukan pembicaraan melalui

telepon disebuah wartel. Ada 4 buah kamar bicara dan

6 buah nomor yang akan dihubungi. Banyak susunan

36

pasangan kamar bicara dan nomor telepon yang akan

dihubungi adalah.....

Jawab: pasangan

2. Dari 10 orang siswa pemenang OSN dibentuk satu tim

yang terdiri dari 4 orang untuk mewakili Indonesia

pada Olimpiade Sains International. Banyaknya tim

yang dapat dibentuk adalah…

Jawab: tim

3. Tentukan semua kombinasi 2 unsur dari unsur-unsur

{ }!

Jawab: { } { } { } { } { } { }

Contoh 3.13

Terdapat 8 titik berbeda pada lingkaran, termasuk A dan

B. Beberapa pertanyaan tentang kombinasi adalah

sebagai berikut

a) Ada berapa garis dapat dibuat?

b) Ada berapa segitiga dapat dibuat?

c) Ada berapa segi lima dapat dibuat?

d) Ada berapa segi lima dapat dibuat melalui A?

e) Ada berapa segi lima dapat dibuat melalui A dan B?

f) Ada berapa segiempat dapat dibuat tidak melaui A

maupun B?

g) Ada berapa segiempat dapat dibuat dengan sisi AB?

37

Teorema 3.2

Bukti:

Banyaknya permutasi n unsur dari n adalah:

Karena suatu permutasi n unsur dari n unsur memuat

Dari unsur-unsur yang sama, maka susunan dari

permutasi ini dihitung sebagai satu kombinasi karena

urutan tidak diperhatikan.

Dengan demikian,

Teorema 3.3

Jika n dan r adalah bilangan-bilangan bulat tidak negatif

dengan maka

Bukti:

{ }

Jadi :

38

Contoh 3.14

a. ( )

b. ( )

c. ( ) (

) ( )

Teorema 3.4

Banyaknya semua himpunan bagian dari himpunan A

yang mempunyai n unsur dicari sebagai berikut:

Himpunan kosong sebanyak : ( )

Himpunan dengan satu unsur sebanyak : ( )

Himpunan dengan dua unsur sebanyak : ( )

Himpunan dengan r unsur sebanyak : ( )

Himpunan dengan n unsur sebanyak : ( )

Banyaknya semua himpunan bagian adalah:

( ) (

) (

) (

) (

)

Dalil Identitas Pascal

( ) (

) ( ) untuk sebarang n,

dengan

39

Bukti:

(

) (

)

{ }

{ }

{ }

Hadi, (

) (

) (

)

Contoh 3.15

a) ( ) (

) (

) (

)

b) ( ) (

) (

) (

)

Contoh 3.16

Identitas Pascal adalah dasar penyusunan geometris dari

koefisien-koefisien binomial dalam bentuk segitiga

sehingga disebut Segitiga Pascal

40

( ) 0 1

( ) ( ) 1 1 1

( ) ( ) ( ) 2 1 2 1

( ) ( ) ( ) ( ) 3 1 3 3 1

( ) ( ) ( ) ( ) ( ) 4 1 4 6 4 1

Contoh penerapan segitiga Pascal dalam suku dua

(binomial) adalah

Teorema 3.5

Jika maka: ∑ ( )

Bukti:

Dengan menggunakan induksi matematika,

(i) Untuk , ∑ ( )

( ) (

)

(benar)

41

(ii) Dianggap benar untuk , yaitu:

∑ ( )

(iii) Akan dibuktikan benar untuk , diperoleh:

∑ ( )

∑ ( )

, ( ) (

)

(

) ( )

- ∑( )

,(

) (

)- ∑ (

)

Jadi, ∑ ( )

, untuk

Teorema 3.6

∑ ( )

untuk sebarang

Bukti:

∑ ( ) (

) (

) (

) (

)

( ) (

) (

)

( )

42

Teorema 3.7

Identitas Vandermonde (Abad 18)

( ) ∑ (

) ( )

Bukti:

Misalkan ada m unsur pada himpunan pertama dan n

unsur pada himpunan kedua. Banyaknya cara mengambil

n unsur dari unsur adalah ( )

Cara lain mengambil r unsur dari gabungan kedua

himpunan adalah mengambil k unsur dari himpunan

pertama, dilanjutkan mengambil unsur dari

himpunan kedua, dengan , yaitu:

( ) (

) ( ) (

)

Jadi ( ) ∑ (

) ( )

Ilustrasi:

Terdapat 3 pria dan 4 wanita

Dua orang diambil secara acak

Banyaknya cara mengambil dapat dilakukan dengan dua

cara

Cara 1: ( )

43

Cara 2: ( ) ( ) (

) ( ) (

) ( )

4. Koefisien Bionominal dan Koefisien Multinomial

4.1 Koefisien bionominal

Pembahasan tentang koefisien binomial merupakan

kelanjutan dari pembahasan tentang permutasi dan

kombinasi, serta merupakan dasar untuk pembahasan

berbagai permasalahan mencari koefisien suku dua dan

suku banyak.

Selanjutnya, penerapan dari pembahasan tentang

koefisien bionomial terkait dengan kombinasi berulang

dan menentukan banyaknya penyelesaian persamaan

atau pertidaksamaan linier banyak variabel yang

memenuhi syarat tertentu dan meminta penyelesaian

yang bulat dan tidak negatif.

Pengertian dan Sifat-Sifat Koefisien Bionomial

Defenisi lambang ( ), dibaca ‘’nCr, yang r dan n

adalah bilangan-bilangan bulat tidak negatif dan r n,

didefenisikan sebagai:

( ) =

( ) disebut sebagai koefisien bionomial

44

Contoh 3.17

a) ( ) =

=

=35

b) ( ) =

=

c) ( ) =

=

perhatikan bahwa ( ) dapat dinyatakan sebagai

pembagian yang mempunyai r faktor pada pembilang dan

r faktor pada penyebut.

Dalil 3.1

( ) =

Bukti: ( ) =

=

( ) =

Dalil 3.2

( ) =(

)

Bukti: ( ) =

( ) =

{ }

=

( ) =(

)

45

Dalil 3.3

Jika ( ) =(

)

Bukti: sehingga:

( ) =(

)

Menurut dalil 3.2 ( ) =(

) ,sehingga :

( )=(

)=(

)

Contoh 3.18

a) ( ) =

=

=

=10

b) ( ) =

=

=

=

=1

c) ( ) =

=

=

=1

Dalil 3.4

( ) + (

) = (

)

Bukti: ( ) + (

) =

+

{ }

=

+

=

= { }

{

=

{ }

46

( ) + (

) = (

)

Dalil 3.5

∑ ( )

Bukti: untuk , diperoleh ∑ ( )

∑ ( )

( ) (

)

----------

Sehingga ruas kiri sama dengan ruas kanan, misalkan

berlaku untuk yaitu

∑ ( )

, berarti harus dibuktikan

bahwa berlaku pula untuk , yaitu

∑ ( )

*( ) (

)

(

) ( )

( ) (

) +

47

Suku yang memuat dalam dicari sebagai

berikut:

*(

) +

*( ) +=(

) ( )

*(

) ( )+

Menurut Dalil 3.4, diketahui bahwa:

(

) ( ) (

), sehingga suku yang memuat

yaitu ( )

Jadi terbukti bahwa ∑ ( )

Contoh 3.19

Carilah :1) ( ) 2) (

) 3) (

)

Jawab sesuai dengan dalil 3.2 ( ) = (

),sehingga :

1) ( ) = (

) =(

) = 455

2) ( ) = (

) =(

) = 715

3) ( ) = (

) =(

) = 190

Contoh 3.20

Uraikan:

1) (x +

48

2) (x +

3) (x +

Jawab:

1) (x + =∑ ( )

=( ) +(

) (

) (

)

( )

=

+

+

+

+

= + + + +

2) (x + = ∑ ( )

=( ) +(

) +(

) +(

)

+( ) +(

) +(

)

= + + +

+ +

3) (x + = ∑ ( )

=( ) +(

) +(

)

+( ) +(

)

+ ( )

49

=

= + + + + +

Contoh 3.21

Carilah: 1). ( 2p+ 2).( 3a-

Jawab:

1. ( 2p+ =∑ ( )

=( ) +(

)

( ) (

)

=

= + + +

2. ( 3a- = ∑ ( )

=( ) +(

)

( ) (

)

( )

= + +

+ +

= - + -

+

50

Contoh 3.22

Carilah koefisien dari :

1) (x + 2) ( 2x +

Jawab:

1) Koefisien dari (x + adalah koefisien

dari berarti diperoleh dari ( )

yaitu ( ) =

=56

2) Koefisien dari ( 2x + adalah koefisien

,berarti diperoleh dari ( )(2 =56 .

8 (-243 ) =-108.864

Definisi 2 jika ,..., adalah bilangan-bilangan

bulat tidak negatif sedemikian hingga +...+ ,

maka:

(

) =

Contoh 3.23

a) (

) =

= 60

b) (

) =

= 210

c) (

) =

= 168

51

Dalil 3.6

Jika maka koefisien

pada

adalah

yang mana

adalah bilangan-bilangan bulat dengan

Sebelum kita membuktikan Dalil 3.6, lihatlah beberapa

kasus yang memuat tiga suku dan :

{ }

( )

(

)

(

)

( )

(

)

52

=

Ternyata dapat ditunjukkan bahwa:

∑ (

)

Sekarang kita buktikan Dalil 3.6

Seperti halnya cara pembuktian(kedua) Dalil 3.5,

koefisien

merupakan banyaknya seluruh

cara yang berbeda dapat memilih sebanyak kali dari

faktor ke 1 faktor ke 2 faktor ke 3

53

faktor, sebanyak kali dari dari factor,

…, dan memilih sebanyak kali dari

faktor. Dengan demikian banyaknya seluruh

cara adalah:

( ) (

) (

) (

)

Terbukti

Contoh 3.24

Carilah koefisien dari

a)

b)

Jawab

a) koefisien dari adalah

= 30

b) koefisien dari adalah

54

Dalil 3.7

Banyaknya permutasi n unsur dengan n1 unsur sama, n2

unsur sama, … , nr unsur sama, dan

adalah

Bukti:

Suatu susunan memuat susunan unsur yang sama. Jika

dianggap berbeda, maka banyaknya susunan dari posisi

unsur adalah:

Dengan pemikiran yang sama, susunan itu juga memuat

susunan unsur yang sama, yang posisinya terbentuk

dalam , dan seterusnya, sehingga unsur yang sama

mempunyai posisi yang terbentuk dalam . Jadi

banyaknya seluruh susunan adalah

Kombinasi Berulang dan Penerapannya

Di dalam suatu jamuan makan tersedia tiga macam buah,

yaitu pisang (P), jeruk (J), dan apel (A). Setiap orang

55

mendapat jatah menerima 4 butir buah. Ada berapa cara

orang dalam memilih buah?

1. Semua keadaan pemilihan buah adalah:

a. Mengambil satu macam buah sebanyak 4 butir,

sehingga terdapat 3 cara, yaitu

b. Mengambil satu macam buah pertama sebanyak 1,

dan satu macam buah lain sebanyak 3, sehingga

terdapat 6 cara, yaitu

c. Mengambil satu macam buah pertama sebanyak 2,

dan satu macam buah kedua sebanyak 2, sehingga


d. Mengambil satu macam buah pertama sebanyak 2,

satu macam buah kedua sebanyak 1, sehingga


Banyaknya seluruh cara memilih buah adalah

2. Beberapa contoh cara mengambil adalah

Keadaan-keadaan di atas dapat dipandang sebagai

susunan antara buah dan pemisah

| | | | | | | | yang maknanya sama

dengan menyusun 6 unsur dengan dua unsur.

56

Banyaknya susunan :

(

) (

)

Dalil 3.8

Banyaknya cara mengambil r unsur secara berulang dari

n unsur yang berbeda adalah (

)

Bukti:

Cara mengambil r unsur secara berulang dari n unsur

yang berbeda bersesuaian dengan cara menyusun x

sebanyak r dan menyusun1 sebanyak

Karena seluruh unsur x dan 1 adalah

unsur-unsur x yang sama sebanyak r, dan unsur-

unsur 1 yang sama sebanyak , maka banyaknya

seluruh susunan adalah

{ } (

)

Jadi banyaknya cara mengambil r unsur secara berulang

dari n unsur yang berbeda adalah (

)

57

Contoh 3.25

a. Suatu toko menjual 4 jenis roti dalam kaleng.

Seseorang membeli 6 kaleng roti. Banyaknya cara

memilih roti kaleng adalah (

) (

)

b. Berapa banyaknya penyelesaian bulat tidak negative

dari ?

Jawab:

Anggap ada unsur-unsur dengan tiga macam (tipe),

tipe 1 sebanyak , tipe 2 sebanyak , dan tipe 3

sebanyak .

Permasalahannya adalah mengambil 11 unsur dari

tiga macam unsur. Banyaknya cara mengambil adalah

(

) (

)

c. Sebuah toko mempunyai 20 macam donat dalam

wadah kotak-kotak. Seseorang membeli 12 kotak

donat. Banyaknya cara memilih donat kotakan adalah

(

) (

)

d. Ada 10 bola dimasukkan dalam 6 lubang. Setiap

lubang dapat memuat seluruh bola. Ada berapa cara

memasukkan bola-bola itu?

Jawab:

Masalah ini sama dengan mencari penyelesaian bulat

tidak negative persamaan

58

Banyak memilih adalah (

) (

)

Dari soal butir d, ada berapa banyak penyelesaian

bulat tidak negatif pertidaksamaan

Jawab:

Bilangan bulat terbesar kurang dari 10 adalah 9,

berarti yang dicari adalah banyaknya penyelesaian

bulat tidak negative persamaan

banyaknya penyelesaian adalah (

)

( )

4.2 Teorema Multinomial

Teorema multinomial merupakan perluasan dari

binomial. Multinomial adalah jumlah t buah suku berbeda

yaitu : x1+ x2+ x3+ ...+ xt

Teorema multinomial adalah rumus penjabaran

Misalkan : x1, x2, x3, ..., xt adalah bilangan-bilangan riil dan

n adalah bilangan bulat positif. Dengan demikian :

∑

59

Penjumlahan dilakukan terhadap semua

dengan

Banyak suku pada adalah

(

)

Contoh 3.26

Hitunglah koefisien dan banyaknya suku dari

a.

dalam

Jawab:

koefisien

adalah

=12600

banyak suku =(

) =1001

b. dalam

koefisien adalah

= -

3.024.000

banyak sukunya adalah (

) =

= 45

5. Kesimpulan

Pokok-pokok pembahasan dalam BAB III yang

perlu dipahami adalah

1. Pengertian factorial dan penerapannya

2. Pengertian permutasi dan penerapannya

3. Notasi factorial dan notasi permutasi

60

4. Permutasi dengan unsur-unsur yang sama

5. Permutasi melingkar

6. Pengertian kombinasi dan rumusnya

7. Hubungan permutasi dan kombinasi

8. Ientitas Pascal

9. Identitas Vandermonde

6. Latihan Soal

1. Carilah 6!

2. Carilah

3. Carilah

4. Carilah banyaknya seluruh permutasi tiga dari a, b, c,

dan d !

5. Carilah banyaknya seluruh permutasi dua dari p, q, r,

s, dan t !

6. Carilah P( 6,4 )

7. Carilah nilai n dari P( n – 1,2 ) = 30

8. Tentukan banyaknya semua bilangan yang terdiri dari

empat angka dan diambil dari angka – angka bilangan

9. Tentukan banyaknya semua susunan lima huruf dari

huruf–huruf kata KAKAK

61

10. Jika hanya memperhatikan urutan orangnya, bukan

urutan kursinya, maka carilah banyaknya cara empat

orang duduk pada empat kursi yang melingkar!

11. Dalam suatu ujian, setiap mahasiswa harus

mengerjakan 5 soal dari 8 soal yang disediakan.

Tentukan:

a. Banyaknya cara memilih soal

b. Banyaknya cara memilih soal jika 2 soal pertama

harus dikerjakan.

c. Banyaknya cara memilih soal jika 2 soal dari 4

soal pertama dan 3 soal dari 4 soal kedua harus

dikerjakan.

d. Banyaknya cara memilih soal jika paling sedikit

dari 4 soal pertama harus dikerjakan.

12. Berapa banyaknya cara memilih

a. 2 pria dari 5 pria,

b. 2 pria dari 5 pria, dan 3 wanita dari 6 wanita,

c. 8 soal dari 10 soal (untuk dikerjakan),

d. 3 orang dari 4 pria dan 3 wanita,

13. Terdapat 8 titik berbeda pada lingkaran, termasuk A

dan B

a. Berapa banyaknya garis dapat dibuat?

b. Berapa banyaknya segitiga dapat dibuat?

c. Berapa banyaknya segilima dapat dibuat?

62

d. Berapa banyaknya segiempat dapat dibuat

dengan sisi AB?

e. Berapa banyaknya segi lima dapat dibuat melalui

titik A?

14. Suatu panitia terdiri dari 4 mahasiswa, diambil atau

dipilih dari 12 mahasiswa, termasuk Rudi dan Rini.

a. Ada berapa cara menyusun panitia?

b. Ada berapa cara menyusun panitia jika Rudi dan

Rini tidak boleh terpilih bersama-sama?

c. Ada berapa cara menyusun panitia jika Rudi dan

Rini harus terpilih bersama-sama?

15. Buktikan bahwa (

) ( ) (

)

(

)

16. Buktikan bahwa ( ) ∑ (

)

,

17. Dari 5 orang calon pengurus organisasi akan dipilih

seorang ketua, wakil ketua dan bendahara. Berapa

banyaknya susunan pengurus yang mungkin?

18. Dari kelompok yang terdiri dari 8 orang akan memilih

3 orang untuk mewakili kelompok tersebut. Jika setiap

orang memiliki kemapuan yang sama maka berapa

banyaknya cara pemilihan?

19. Lima orang bermain bulu tangkis satu lawan satu

bergantian, banyaknya pertandingan adalah...

63

20. Dalam kejuaraan sepak bola, team nasional Indonesia

mengirim 13 orang pemain, berapa banyak kombinasi

pemain yang mungkin terbentuk?

21. Berapa banyaknya penyelesaian bulat tidak negatif

dari jika , , dan

22. Berapa banyaknya penyelesaian butat tidak negatif

dari untuk dan

(atau )

23. Berapa banyaknya suku dari :

a.

b.

24. Carilah banyaknya penyelesaian bulat

, , .

25. Carilah banyaknya cara menempatkan 15 bola dalam

5 kotak berbeda sehingga kotak pertama berisi paling

sedikit 1 bola dan paling banyak 3 bola, kotak kedua

berisi 2 bola sampai dengan 4 bola, dan kotak-kotak

yang lain paling sedikit berisi dua bola.

26. Tentukan koefisien dari

dalam ekspansi

(x_1+x_2+x_3+x_4+x_5 )^10

27. Tentukan koefisien dari x^5 y^10 z^5 w^5 dalam (x-

7y+3z-w)^25

28. Tentukan koefisien dari x^5 dalam (a+bx+cx^2 )^10

64

29. Carilah semua harga ∑▒8!/i!j!k! , jika i,j,k adalah

bilangan bulat positif yang menjalani semua harga

sedemikian hingga jumlahnya =8!

30. Gunakan teorema multinomial untuk menguraikan

(x+y+z)^3

65

BAB IV FUNGSI PEMBANGKIT

1. Pendahuluan

Sebagai kelanjutan BAB I, BAB II dan BAB III

memuat konsep dan penerapan dari fungsi pembangkit

biasa, yaitu bentuk deret fungsi yang koefisien-

koefisiennya merupakan barisan tak terhingga bilangan

real tertentu. Fungsi pembangkit biasa mempunyai

ketertiban dengan berbagai konsep matematika yang

membantu kajian menjadi lebih luas dan mendalam.

Bagian-bagian matematika yang mendukung

pengembangan kajian adalah binomial, pembagian

polynomial, pendeferensialan, penambahan suku dan

penderetan Maclarin. Bentuk-bentuk baku fungsi

pembangkit biasa dapat diperoleh dari pembahasan

secara rinci masing-masing bagian tersebut. Bentuk-

bentuk lain diturunkan dari bentuk baku dengan cara

menyelesaikan pola yang berlaku.

Beragam fungsi pembangkit biasa banyak

dikaitkan dengan distribusi barang, pengambilan atau

pemilihan objek dan penentuan banyaknya penyelesaian

persamaan linier yang mempunyai penyelesaian bulat.

Dalam prosedur menerapkan fungsi pembangkit,

beberapa cara dapat dikembangkan dengan

66

menggunakan tabel, menerapkan kombinasi berulang,

penerapan model persamaan linier dan penerapan

koefisien polynomial.

Kemampuan Akhir yang direncanakan

Dalam mempelajari BAB IV ini mahasiswa mampu

menganalisis dan memecahkan permasalahan yang

berkaitan dengan Fungsi Pembangkit Biasa dalam

kehidupan nyata.

2. Fungsi Pembangkit Biasa

Fungsi pembangkit biasa digunakan untuk membilang,

yaitu mencari banyaknya suatu pilihan dalam mengambil

objek atau banyaknya cara dalam melakukan kegiatan

tertentu.

2.1 Definisi

Suatu fungsi

∑

disebut fungsi pembangkit biasa dari barisan tak hingga

bilangan real

Contoh 4.1

a. Untuk sembarang n ∈ Z+

67

∑(

)

∑(

)

(

) (

) (

) (

)

Dengan demikian adalah fungsi

pembangkit dari barisan:

(

) (

) (

) (

)

b. Jika dibagi dengan dengan cara

pembagian biasa, maka diperoleh

Dengan demikian :

,

sehingga

adalah fungsi pembangkit biasa

dari barisan

68

c. Dengan cara yang sama, jika dibagi oleh

, maka akan diperoleh ,

sehingga:

adalah fungsi pembangkit

biasa dari barisan

d. Jika 1 dibagi dengan dengan cara pembagian

biasa, maka diperoleh :

Dengan demikian

sehingga

adalah fungsi pembangkit biasa dari

barisan

e. Dari hubungan pembagian

dapat ditentukan bahwa:

(

)

,

69

sehingga


biasa dari barisan 1, 2, 3, 4, . . .

f. Dari hubungan pada butir e:

dapat ditentukan bahwa:

Sehingga


biasa dari barisan 0, 1, 2, 3, 4, . . .

g. Dari hubungan pada butir f:

dapat ditentukan bahwa

,

-

Sehingga


biasa dari barisan

h. Dari hubungan pada butir e:

70

Dapat ditentukan bahwa:

Sehingga


biasa dari barisan 1, 1, 0, 1, 1, …

Demikian pula:

Sehingga


barisan 1, 1, 1, 3, 1, 1, …

Contoh 4.2

Fungsi pembangkit biasa dari barisan 2, 6, 12, 20, 30, 42, .

. . dapat dicari dengan menggunakan pola :

Dari:

71

Dapat diketahui bahwa : dengan n 0,

sehingga :

Dengan demikian :


barisan 2, 6, 12, 20, 30, 42, . . .

72

Dari pembahasan tentang binomial dapat ditentukan

bahwa :

(

)

Untuk n, r dan n 0, dengan demikian untuk n

, dapat ditentukan bahwa:

( )

( )

(

)

Contoh 4.3

Sesuai dengan pembahasan dalam kalkulus, Deret

Maclaurin dari adalah :

Jika maka :

,

( – )( – ) ,

Sehingga

73

∑

∑

∑

(

)

(

) (

) (

) (

)

∑

(

)

Berarti adalah fungsi pembangkit dari

barisan ( ) (

) (

)

2.2 Menerapkan Fungsi Pembangkit Biasa

Dalam menerapkan fungsi pembangkit biasa ini,

langsung saja kita lihat beberapa contoh di bawah ini

yang berkaitan dengan kehidupan sehari-hari.

Contoh 4.4

Seorang ibu mempunyai 2 jeruk yang akan dibagikan

kepada anak-anaknya yaitu Ani dan Budi. Ada berapa cara

74

yang bisa dilakukan ibu untuk membagikan jeruk kepada

anak-anaknya ?

Jawab :

Cara 1:

Dengan cara mendaftarnya secara rinci

No. Ani Budi

1.

2.

3.

2

1

-

-

1

2

Banyaknya cara membagi adalah tiga

Cara 2:

Dengan bantuan kombinasi dan persamaan linier,

permasalahan dapat dinyatakan dalam model

matematika.

=banyaknya jeruk yang diterima Ani

= banyaknya jeruk yang diterima Budi

Keadaan ini sesuai dengan kombinasi berulang 2 unsur

dari 2 unsur, sehingga banyaknya seluruh keadaan

adalah:

(

) (

)

75

Cara 3 :

Keadaan jumlah jeruk yang diterima Ani maupun Budi

adalah 0 jeruk, 1 jeruk, 2 jeruk. Jika dinyatakan dalam

bentuk polinomial, maka diperoleh atau

karena perkalian polinomial menghasilkan suku-suku

dari yang pangkatnya dijumlahkan, maka gabungan

keadaan jumlah jeruk yang diterima Ani dan Budi

Karena jumlah jeruk seluruhnya hanya dua, maka

gabungan keadaan-keadaan jumlah jeruk yang diterima

oleh Ani dan Budi tidak dalam bentuk suku maupun

tetapi suku

Koefisien dari f(x) adalah 3, jadi banyaknya seluruh

cara membagi jeruk adalah 3.

Contoh 4.5

Dari contoh 2.1, jika jumlah jeruk yang dibagi adalah 4,

maka banyaknya cara membagi dapat dijelaskan sebagai

berikut :

Cara 1: Mendaftarnya secara rinci

76

No. Ani Budi

1.

2.

3.

4.

5.

4

3

2

1

-

-

1

2

3

4

Banyaknya cara membagi adalah 5

Cara 2. : Model persamaan linier :

Nilai kombinasi berulang 4 unsur dari 2 unsur adalah :

(

) (

)

Cara 3: Fungsi pembangkit yang mewakili cara

pembagian adalah :

Karena jumlah jeruk yang dibagi ada 4, maka yang dicari

adalah koefisien , yaitu diperoleh dari:

Jadi banyaknya seluruh cara membagi jeruk adalah 5.

Berdasarkan contoh 4.4 dan contoh 4.5 dapat

diketahui bahwa model persamaan linier dengan

penyelesaian bulat mempunyai hubungan dengan

koefisien tertentu suatu suku dari suatu fungsi

pembangkit biasa. Fungsi pembangkit biasa ini mewakili

77

keadaan-keadaan dalam suatu distribusi unsur yang

dapat dilakukan dengan menggunakan tabel. Cara tabel

tentu menjadi kurang praktis, karena memerlukan waktu

lebih banyak dan tempat lebih panjang, jika jumlah unsur

yang didistribusikan bertambah banyak, dan penerima

distribusi juga bertambah banyak. Berikut ini berbagai

contoh yang memperjelas keterkaitan dari cara 1, cara 2,

dan cara 3.

Contoh 4.6

Sebutkan permasalahan fungsi pembangkit biasa dari

penyelesaian bulat persamaan-persamaan :

Jawab :

a) Mencari koefisien dari fungsi pembangkit biasa :

b) Mencari koefisien x20 dari fungsi pembangkit biasa :

78

Contoh 4.7

Sebutkan permasalahan fungsi pembangkit biasa dari:

a) Banyaknya memilih 10 permen dari 6 merek permen

b) Banyaknya cara mengambil r unsur dari n jenis unsur

Jawab :

a) Mencari koefisien dari :

b) Mencari koefisien dari :

Contoh 4.8

Carilah permasalahan fungsi pembangkit dari mencari

banyaknya penyelesaian bulat persamaan:

Jawab:

Misalkan , , , dan

, maka :

untuk , dapat ditentukan ,



79


Sehingga : ,

dapat diganti menjadi :

, , ,

,

, , , ,

Jadi permasalahan fungsi pembangkit yang dicari adalah

menentukan koefisien dari

Contoh 4.9

Seorang ibu membagikan 24 jeruk kepada 4 anaknya

sehingga masing-masing anak menerima paling sedikit 3

jeruk tetapi tidak lebih dari 8 jeruk. Ada berapa cara

membagikan jeruk ?

Jawab :

Permasalahan di atas dapat diubah menjadi

permasalahan fungsi pembangkit biasa, yaitu mencari

koefisien dari

(

)

Koefiaien dari adalah dari

80

{ (

) (

) } {(

) (

) (

) }

Koefisien dari adalah ( ) (

) (

) (

)( )

(

) (

) (

)

(

) (

)

(

) (

) (

) (

)(

)

–

Jadi banyaknya cara membagi jeruk adalah 125 cara

Contoh 4.10

Carilah banyaknya cara menempatkan 20 bola sejenis

dalam 6 kotak sehingga kotak pertama berisi 1 sampai

dengan 5 bola dan kotak-kotak yang lain paling sedikit

berisi 2 bola.

Jawab :

Masalah ini sama dengan mencari penyelesaian bulat :

, , ,

, Penyelesaian masalah ini adalah sebagai

berikut :

Pertama dicari penyelesaian yang memenuhi , dan

, yaitu sebanyak

(

) (

)

81

Kedua dicari penyelesaian yang memenuhi , ,

yaitu sebanyak

(

) (

)

Banyaknya penyelesaian bulat adalah

(

) (

)

Cara lain menyelesaikan masalah ini adalah mencari

koefisien dari suatu fungsi pembangkit biasa :

{ }

Koefisien dari f(x) adalah koefisien dari

[( ) (

) ][(

)

( ) ]

Koefisien dari adalah :

[(

) (

)] [ (

) (

)]

[ (

)] [ (

)]

[ (

)] [ (

)]

82

[(

)] [ (

)]

[(

)] [ (

)]

Contoh 4.11

Carilah barisan yang dibangkitkan oleh

Jawab :

Untuk , diperoleh , sehingga

Untuk , diperoleh , sehingga

[

∑(

)

] [

∑(

)

]

83

[

∑(

)

] [

∑(

)

]

∑(

)

Barisan yang dibangkitkan adalah : (

) (

) (

)

3. Fungsi Pembangkit Eksponensial dan

Penerapannya

Penerapan dari fungsi pembangkit Eksponensial

serupa dengan fungsi pembangkit biasa, yaitu mencari

banyaknya seluruh susunan unsure – unsure yyang

bersifat berulang. Cara mencarinya dengan mencari

koefisien suku yang memuat x^n/n! untuk sebarang n∈Z

dapat ditentukan bahwa :

(

) (

) (

) (

)

disebut fungsi pembangkit biasa

(ordinary)dari barisan:

(

) (

) (

) (

)

dapat dinyatakan dalam bentuk ini∶

84

Fungsi disebut fungsi pembangkit

eksponensial dari barisan

Definisi 1:

∑(

)

Disebut fungsi pembangkit eksponensial dari barisan :

Contoh 4.12

Berapa banyaknya susunan 4 huruf dari kata ENGINE ?

Jawab :

Keadaan pengambilan 4 huruf dari kata ENGINE dan

banyaknya susunan adalah

85

Banyaknya cara :

Contoh 4.13

Carilah fungsi pembangkit eksponensial dari barisan :

a.

b.

Jawab :

a)

b)

86

Contoh 4.14

Carilah banyaknya susunan 4 huruf dari huruf – huruf

kata SARASA

Jawab :

Kata SARASA menurut A sebanyak 3, memuat huruf S

sebanyak 2, dan memuat huruf R sebanyak 1, sehingga

fungsi pembangkit eksponensial yang sesuai adalah :

[

] [

]

Permasalahan banyaknya susunan 4 huruf ini sama

dengan mencari koefisien

dari

Suku – suku yang memuat adalah :

*

+ *

+ *

+ *

+ *

+ atau

atau

Koefisien dari

Jadi banyaknya susunan 4 huruf dari kata SARASA adalah

38

4. Kesimpulan

Dalam mempelajari BAB ini, mahasiswa harus

memahami dan menguasai fungsi pembangkit

87

eksponensial dan penerapannya, teruta,a dalam mencari

banyaknya susunan r unsur dari n unsud beragam.

1. Fungsi pembangkit eksponensial dari barisan

adalah,,,

∑

2. Fungsi pembangkit eksponensial dari barisan tak

hingga , adalah

∑

3. Fungsi pembangkit eksponensial dari barisan 1, 1, 1,

… adalah

4. Fungsi pembangkit eksponensial dari barisan 1, -1, 1,

-1, … adalah


0, … adalah


1, … adalah

88

7. Bentuk fungsi yang dapat digunakan untuk mengganti

sususnan unsur-unsur tergantung pada banyaknya

unsur sama dari ragam keadaan awal.

a. Satu unsur sama diganti

b. Dua unsur sama diganti

c. Tiga unsur sama diganti

d. n unsur sama diganti

8. Banyaknya susunan r unsur dapat diperoleh dari

koefisien

Terhadap fungsi pembangkit

eksponensial yang sesuai. Fungsi pembangkit

eksponensial yang sesuai dicari dari gabungan

perkalian bentuk-bentuk fungsi pengganti terhadap

keadaan unsur-unsur awal.

5. Latihan Soal

1. Carilah barisan yang dibangkitkan oleh

a.

b.

c.


89

a.

b.

c.


a.

b.

4. Carilah fungsi pembangkit biasa dari barisan 1, -4,

16, -64, …

5. Carilah fungsi pembangkit biasa dari barisan 2, 8,

32, 128, …

6. Carilah

a. ( )

b. ( )

c. ( )

7. Sebutkan permasalahan fungsi pembangkit biasa

dari penyelesaian bulat persamaan berikut:

a.

b. ,

genap dan ganjil

8. Carilah koefisien:

90

a. dari

b. dari

c. dari


10. Buktikan bahwa ( ) ∑ (

)

untuk semua

11. Carilah koefisien dari

12. Seorang Ibu mempunyai 12 jeruk, akan dibagikan

ke tiga anaknya, anak pertama paling sedikit

menerima 4 jeruk, anak kedua dan ketiga masing-

masing paling sedikit menerima 2 jeruk, tetapi

anak ketiga tidak boleh menerima lebih dari 5

jeruk. Ada berapa cara Ibu dalam membagikan

jeruk kepada anak-anaknya?

13. Sebutkan permasalahan fungsi pembangkit biasa

dari permasalahan berikut:

a. Ada 4 warna permen, yaitu merah, hijau, putih

dan kuning. Seorang anak mengambil 24

permen sedemikian hingga jumlah permen

91

putih genap, dan paling sedikit 6 permen adalah

kuning. Ada berapa cara mengambil permen?

b. Seorang direktur akan membagikan 25 lembar

sepuluh ribuan kepada 4 orang karyawannya.

Ada berapa cara membagi?

14. Ada berapa cara mendistribusikan 3000 amplop

dalam kotak-kotak yang berisi masing-masing 25

amplop, kepada empat kelompok siswa, sehingga

setiap kelompok menerima paling sedikit 150

amplop, tetapi tidak boleh lebih dari 1000 amplop.

92

BAB V PENGANTAR DASAR TEORI GRAPH

1. Pendahuluan

Teori graph lahir pada Tahun 1736 melalui tulisan

Euler yang berisi tentang upaya pemecahan masalah

jembatan Konigsberg yang sangat terkenal di Eropa.

Kurang lebih seratus tahun setelah lahirnya tulisan Euler

tersebut tidak ada perkembangan yang berarti berkenaan

dengan teori graph. Tahun 1847, G.R. Kirchoff (1824 –

1887) berhasil mengembangkan teori pohon (Theory of

trees) yang digunakan dalam persoalan jaringan listrik.

Sepuluh tahun kemudian, A. Coyley (1821 – 1895) juga

menggunakan konsep pohon untuk menjelaskan

permasalahan kimia yaitu hidrokarbon. Pada masa

Kirchoff dan Coyley juga telah lahir dua hal penting dalam

teori graph. Salah satunya berkenaan dengan konjektur

empat warna, yang menyatakan bahwa untuk mewarnai

sebuah atlas cukup dengan menggunakan empat macam

warna sedemikian hingga tiap negara yang berbatasan

akan memiliki warna yang berbeda. Para ahli teori graph

berkeyakinan bahwa orang yang pertama kali

mengemukakan masalah empat warna adalah A.F. Mobius

(1790 – 1868) dalam salah satu kuliahnya di Tahun 1840.

Sepuluh tahun kemudian, A. De Morgan (1806 – 1871)

93

kembali membahas masalah ini bersama ahli-ahli

matematika lainnya di kota London.

Dengan demikian tulisan De Morgan dianggap

sebagai referensi pertama berkenaan dengan masalah

empat warna. Masalah empat warna ini menjadi sangat

terkenal setelah Coyley mempublikasikannya Tahun 1879

dalam Proceedings of the Royal Geographic Society volume

pertama. Hal lain yang penting untuk dibicarakan

sehubungan dengan perkembangan teori graph adalah

apa yang dikemukakan oleh Sir W.R. Hamilton (1805 –

1865). Pada Tahun 1859 dia berhasil menemukan suatu

permainan yang kemudian dijualnya ke sebuah pabrik

mainan di Dublin. Permainan tersebut terbuat dari kayu

berbentuk dodecahedron beraturan yakni berupa sebuah

polihedron dengan 12 muka dan 20 pojok. Tiap muka

berbentuk sebuah pentagon beraturan dan tiap pojoknya

dibentuk oleh tiga sisi berbeda. Tiap pojok dari

dodecahedron tersebut dipasangkan dengan sebuah kota

terkenal seperti London, New York, Paris, dan lain-lain.

Masalah dalam permainan ini adalah, kita diminta untuk

mencari suatu rute melalui sisi-sisi dari dodecahedron

sehingga tiap kota dari 20 kota yang ada dapat dilalui

tepat satu kali. Walaupun saat ini masalah tersebut dapat

dikategorikan mudah, akan tetapi pada saat itu tidak ada

94

seorang pun yang bisa menemukan syarat perlu dan

cukup dari eksistensi rute yang dicari.

Kurang lebih setengah abad setelah masa

Hamilton, aktivitas dalam bidang teori graph dapat

dikatakan relatif kecil. Pada Tahun 1920-an kegiatan

tersebut muncul kembali yang dipelopori oleh D. Konig.

Konig berupaya mengumpulkan hasil-hasil pemikiran

para ahli matematika tentang teori graph termasuk hasil

pemikirannya sendiri, kemudian dikemasnya dalam

bentuk buku yang diterbitkan pada Tahun 1936. Buku

tersebut dianggap sebagai buku pertama tentang teori

graph. Tiga puluh tahun terakhir ini merupakan periode

yang sangat intensif dalam aktivitas pengembangan teori

graph baik murni maupun terapan. Sejumlah besar

penelitian telah dilakukan, ribuan artikel telah diterbitkan

dan lusinan buku telah banyak ditulis. Di antara orang

terkenal yang banyak berkecimpung dalam bidang ini

adalah Claude Berge, Oysten Ore, Paul Erdos, William

Tutte, dan Frank Harary.

2. Pengertian Dan Konsep Dasar Teori Graph

Suatu graph terdiri dari suatu himpunan tak

kosong yang masing- masing unsurnya disebut titik

95

(vertex) dan suatu himpunan pasangan tak berurutan dari

titik- titik tersebut yang disebut sisi (edge).

Di sini G melambangkan suatu graph. Himpunan

titik di graph G dinyatakan dengan dan himpunan

sisi di graph G dinyatakan dengan . Jika banyak titik

dan banyak sisi di G terhingga, maka G disebut graph

terhingga.

Dua sisi atau lebih yang menghubungkan satu

pasang titik disebut sisi rangkap (multiple edges). Suatu

sisi yang titik ujungnya sama disebut loop. Graph tanpa

sisi rangkap dan tanpa loop disebut graph sederhana

(simple graph).

Jika u dan v titik–titik di G dan suatu sisi di

G, maka dikatakan:

menghubungkan dan ,

dan terhubung langsung (adjacent),

terkait (incident) dengan ,

terkait (incident) dengan ,

dan di sebut titik ujung dari ,

96

Contoh 5.1.

Pada gambar 1.1 , graph G adalah sederhana, dengan

{ } { }| |

| |

graph H tidak sederhana karena memuat loop dan sisi

rangkap.

Contoh 5.2. jika di ketahui graph G mempunyai.

{ }

{ }

Maka graph G dapat di gambarkan seperti pada gambar 1.

G

Gambar 1.2

Misalkan G suatu graph dengan himpunan titik

dan himpunan sisi . Graph bagian (subgraph)

u

w

x

G H

v

k

97

dari G adalah suatu graph yang setiap titiknya adalah

anggota dan setiap sisinya adalah anggota . Jika

H suatu graph bagian dari G dan , maka H di

sebut graph bagian rentangan (spanning subgraph) dari G.

Contoh 5.3.

Dua graph yang titiknya sama dinamakan sub

graph rentangan

Pada gambar 1.3, terhadap G, adalah bagian rentangan,

adalah grap bagian tetapi bukan graph bagian

rentangan, dan bukan graph bagian.

98

3. Jenis-Jenis Graph

Sebuah jalan (walk) dalam graph G adalah sebuah

urutan tak nol ... ... , yang

suku-sukunya bergantian antara simpul dan sisi

sedemikian hingga ujung dari adalah

dan . disebut simpul awal (simpul asal).

disebut simpul akhir (simpul terminus). , 1 < i < k,

disebut simpul internal. Panjang sebuah jalan adalah

banyaknya sisi dalam jalan tersebut. Jika semua sisi pada

sebuah jalan berlainan, maka jalan tersebut disebut jejak

(trail). Jejak yang simpul awal dan simpul akhirnya

berlainan disebut jejak tertutup. Jika simpul-simpul dari

.... ...ek dari jalan W berlainan, maka

W disebut lintasan (path). Lintasan tertutup dinamakan

siklus. Siklus dengan banyaknya simpul n, dinotasikan

dengan Cn. Siklus : Jejak tertutup yang simpul awal dan

simpul internalnya berlainan.

Siklus : Jejak tertutup yang simpul awal dan simpul

internalnya berlainan.

Contoh :

99

Berdasarkan graph G di atas

1. Berilah contoh jalan yang bukan jejak.

2. Berilah contoh jejak yang bukan lintasan.

3. Berilah contoh empat buah lintasan yang

menghubungkan simpul b dan f.

4. Berilah contoh sirkuit yang bukan siklus.

5. Tentukan semua siklus yang ada di graph G.

merupakan contoh graph yang tidak terhubung.

a. Perjalanan (Walk)

Perjalanan atau walk pada suatu Graph G adalah

barisan simpul dan ruas berganti-ganti

ruas menghubungkan

dan dapat hanya ditulis barisan ruas atau

barisan simpul saja atau

.Dalam hal ini, disebut simpul

awal, dan disebut simpul akhir. Perjalanan disebut

perjalanan tertutup bila , sedangkan

Perjalanan disebut perjalanan tebuka yang

menghubungkan dan .

Panjang Perjalanan adalah

banyaknya ruas dalam barisan tersebut.

100

b. Jejak (Trail)

Jejak pada suatu graph adalah jalan yang sisi-sisinya

berbeda.

c. Lintasan (Path)

Lintasan pada suatu graph adalah jejak yang semua

titiknya berbeda.

d. Sirkuit (Cycle)

Lintasan yang berawal dan berakhir pada simpul

yang sama disebut sirkuit atau siklus. Panjang sirkuit

adalah jumlah ruas dalam sirkuit tersebut. Graph

yang tidak mengandung sirkuit disebut acyclic.

Contoh 5.4

Sebuah graph adalah terhubung jika setiap dua

buah titik di G dihubungkan oleh lintasan di G. Jika G

adalah graph terhubung, maka dikatakan bahwa

komponen dari G adalah 1, dinotasikan .

Definisikan graph tidak terhubung! Graph G disebut

terhubung jika untuk setiap dua simpul yang berbeda

terdapat lintasan yang menghubungkan simpul-simpul

101

tersebut. Sebuah lintasan geodesic (geodesic path)

antara titik dan dari graph G adalah lintasan

dengan panjang minimum. Panjang lintasan geodesic

antara simpul u dan v dinamakan jarak antara simpul u

dan v. Dinotasikan

Misalkan adalah sebuah graph.

adalah subgraph dari G jika dan .

Induced Subgraph. Spanning subgraph.

4. Keterkaitan Teori Graph dengan Dunia Nyata

Kontruksi model matematika dapat dibuat

dalam berbagai cara permasalahan matematika yang

berbeda-beda. Salah satu model matematika yang

sudah cukup dikenal dan bisa mencakup berbagai

permasalahan adalah teori graph. Pada bagian ini akan

disajikan contoh permasalahan yang dapat dibuat

model matematikanya dalam bentuk graph.

Contoh 5.5

Seorang guru bermaksud membuat suatu

diagram tentang hubungan antar siswa dari kelas yang

diajarnya. Diagram tersebut harus berisikan informasi

apakah antara satu siswa dengan siswa lainnya

berteman atau tidak berteman. Hal semacam itu dapat

102

dinyatakan dalam bentuk diagram yang disebut graph.

Dalam graph tersebut, seorang siswa dinyatakan

sebagai sebuah titik dan hubungan berteman antara

dua siswa, dinyatakan dengan sebuah sisi yang

menghubungkan titik-titik yang mewakili dua siswa

tersebut.

Contoh 5.6

Dalam suatu persiapan untuk menghadapi

perang, beberapa peleton tentara ditempatkan di

beberapa lokasi yang berbeda. Komunikasi antara

peleton dilakukan dengan menggunakan radio telepon

yang kemampuannya terbatas pada jarak tertentu.

Jika jarak antara dua peleton masih terjangkau,

maka komunikasi dapat dilakukan. Keadaan seperti ini

dapat dinyatakan dalam suatu model matematika

berbentuk graph. Dalam graph tersebut, titik

menyatakan peleton dansisi antara dua titik

menyatakan komunikasi antara dua peleton yang

diwakili oleh dua titik tersebut.

Contoh 5.7

Misalkan kita ingin menempuh perjalanan dari

Jakarta menuju Surabaya. Mungkin kita ingin

103

mengetahui rute terpendek yang dapat dipilih. Dalam

permasalahan ini kota direpresentasikan sebagai titik,

sedangkan rute atau jalan direpresentasikan sebagai

segmen garis atau kurva.

Contoh 5.8

Misalnya terdapat satuan tugas dalam

kepolisian yang bertugas mengungkap jaringan

pengedar obat terlarang. Hal tersebut dapat kita

gambarkan ke dalam sebuah graph. Dalam graph

tersebut, tiap-tiap anggota komisi dinyatakan dengan

sebuah titik, dan hubungan di antara anggota

dinyatakan dengan sisi atau kurva. Dalam

permasalahan ini kita mungkin ingin tahu seberapa

rapuhkah jaringan komunikasi ini, dan seberapa

mudahkah kita bisa menghancurkan jaringan tersebut.

Dengan menggunakan teori graph desain jaringan

komunikasi yang handal dapat diciptakan.

Contoh 5.9

Teori graph juga biasanya digunakan dalam

bidang elektronika, misalnya untuk mendesain sirkuit

cetakan. Biasanya sirkuit cetakan pada lembaran

silikon harus didesain secara khusus. Berbeda dengan

104

desain sirkuit yang menggunakan kabel-kabel, sirkuit

cetakan tidak boleh mengandung bagian-bagian

konduktor yang saling bersinggungan atau saling

memotong, karena hal tersebut bisa membuat

munculnya hubungan pendek. Teori graph memberi

penjelasan apakah suatu pola sirkuit cetakan yang kita

miliki mempunyai pola lain yang sejenis? Apakah

sebuah pola sirkuit yang memiliki hubungan

konduktor yang saling berpotongan dapat didesain

ulang demikian sehingga susunannya masih tetap tapi

tidak lagi mengandung bagian-bagian yang saling

bersinggungan atau berpotongan? Melalui konsep

graph isomorfik kita dapat mengetahui apakah

sebuah sirkuit cetakan memiliki desain lain yang lebih

baik tanpa mengubah susunannya.

5. Kesimpulan

Dalam membahas BAB V ini mahasiswa diharapkan

mampu menjelaskan dan mendeskripsikan ;

1) Pengertian dan konsep dasar teori graph

2) Jenis-jenis graph dan contohnya dalam

kehidupan nyata

3) Hubungan istilah-istilah dalam teori graph

dengan kehidupan nyata

105

6. Latihan Soal

1. Ada 7 kota (A, …, G) yang beberapa diantaranya

dapat dihubungkan secara langsung dengan jalan

darat. Hubungan-hubungan langsung yang dapat

dilakukan adalah sebagai berikut:

A dengan B dan D

B dengan D

C dengan B

E dengan F

Buatlah graf yang menunjukkan keadaan

transportasi di 7 kota tersebut.

2. Perhatikan graf berikut ini.

Tentukan:

a. Himpunan titik-titik, himpunan garis-garis, titik-

titik ujung masing-masing garis, dan garis

parallel.

b. Loop dan titik terasing.

3. Gambarlah graf G dengan titik V(G)={v1, v2, v3, v4}

dan garis E(G)={e1, e2, e3, e4, e5} dengan titik-titik

ujung sebagai berikut.

106

Garis Titik Ujung

e1 {v1,v3}

e2 {v2,v5}

e3 {v1}

e4 {v2,v5}

e5 {v3}

4. Gambarlah graf lengkap K2, K3, K4, K5, K6 !

5. Gambarlah komplemen graf G yang didefinisikan

dalam gambar dibawah ini!

A B C

6. Pada graf berikut, apakah graf H merupakan subgraf

G?

a.

107

b.

c.

d.

7. Gambarlah semua subgraf yang mungkin dibentuk

dari graf G berikut!

e2

V2

e1

V1 Graf G

108

8. Tentukan derajat tiap-tiap titik dalam graf pada

gambar berikut. Berapa derajat totalnya?

e1 e4 v5

v1 v3

e2 e3 v6

v4

v2 e5

9. Gambarlah graf dengan spesifikasi dibawah ini (jika

ada).

a. Graf dengan 4 titik yang masing-masing

berderajat 1, 1, 2 dan 3

b. Graf dengan 4 titik yang masing-masing

berderajat 1, 1, 3 dan 3

c. Graf dengan 10 titik yang masing-masing

berderajat 1, 1, 2, 2, 2, 3, 4, 4, 4 dan 6

d. Graf sederhana dengan 4 titik yang masing-

masing berderajat 1, 1, 3 dan 3

10. Tentukan mana diantara barisan titik dan garis

pada gambar berikut yang merupakan walk, path,

path sederhana, sirkuit dn sirkuit sederhana.

109

e4

V3 e5 v4

e2 e3

v1 v2 e7 e6 e10

e1 e8

v6 e9 v5

a. v1e1v2e3v3e4v3e5v4

b. v1e1v2e3v3e5v4e5v3e6v5

c. v2e3v3e5v4e10v5e6v3e7v6e8v2

d. v2e3v3e5v4e10v5e9v6e8v2

110

BAB VI KETERKAITAN MATEMATIKA DISKRIT

DENGAN MATA PELAJARAN MATMATIKA DI

SEKOLAH

1. Pendahuluan

Kualitas pembelajaran harus ditingkatkan untuk

meningkatkan hasil pendidikan. Dan secara mikro harus

ditemukan strategi atau pendekatan pembelajaran yang

efektif yang sangat beririsan dengan nilai-nilai softskill

sehingga wujud keberhasilan yang akan diperoleh

berimbang antara ranah kognitif, afektif dan

psikomotorik.

Dalam pembelajaran matematika di kelas

hendaknya penekanannya terletak pada keterlibatan

mahasiswa secara aktif dalam kegiatan pembelajaran

antara konsep-konsep matematika dengan pengalaman

mahasiswa sehari-hari sehingga mahasiswa dapat lebih

memahami konsep dan dapat menerapkan untuk

memecahkan permasalahan yang ada pada kehidupan

sehari-hari atau pada bidang lain.

Sesuai dengan tujuan diberikannya matematika di

sekolah, kita dapat melihat bahwa matematika sekolah

memegang peranan sangat penting. Anak didik

memerlukan matematika untuk memenuhi kebutuhan

111

praktis dan memecahkan masalah dalam kehidupan

sehari-hari. Misalnya, dapat berhitung, dapat menghitung

isi dan berat, dapat mengumpulkan, mengolah,

menyajikan dan menafsirkan data, dapat menggunakan

kalkulator dan komputer. Selain itu, agar mampu

mengikuti pelajaran matematika lebih lanjut, membantu

memahami bidang studi lain seperti fisika, kimia,

arsitektur, farmasi, geografi, ekonomi, dan sebagainya,

dan agar para siswa dapat berpikir logis, kritis, dan

praktis, beserta bersikap positif dan berjiwa kreatif.

2. Keterkaitan Materi Matematika Diskrit Dengan

Materi Di Sekolah

Matematika diskrit adalah bagian dari matematika

yang mempelajari objek-objek diskrit. Di sini objek-objek

diskrit diartikan sebagai objek-objek yang berbeda dan

saling lepas. Matematika diskrit memiliki aplikasi di

hampir semua bidang kehidupan, seperti ilmu komputer,

kimia, botani, zoologi, linguistik, geografi, dan bisnis.

Masalah-masalah seperti

(i) Ada berapa cara membuat password untuk sebuah

sistem komputer?

(ii) Bagaimana mengurutkan sebuah himpunan

bilangan bulat dari terkecil hingga terbesar?

112

(iii) Berapa besar peluang memenangkan sebuah

undian?

(iv) Berapa jarak terpendek antara 2 kota atau lebih?

(v) Bagaimana rute jaringan yang baik?

(vi) Seberapa efektif algoritma yang dibuat?

merupakan contoh kajian dalam matematika diskrit.

Secara lebih umum, matematika diskrit digunakan

untuk

a) Menghitung banyak objek

b) Mempelajari hubungan antara himpunan-

himpunan berhingga

c) Menganalisis proses yang melibatkan langkah-

langkah yang banyaknya berhingga

Lima tema dalam matematika diskrit berikut

tujuan masing-masing adalah

1. Penalaran matematika: memberikan pemahaman

tentang penalaran matematika dalam membaca,

memahami, dan membangun argumen

matematika.

2. Analisis kombinatorial: memberikan keterampilan

menghitung banyak objek sebagai salah satu

kemampuan dasar untuk memecahkan masalah.

3. Struktur diskrit: memberikan pemahaman tentang

struktur diskrit sebagai salah satu struktur

113

matematika abstrak yang digunakan untuk

menyajikan objek-objek diskrit dan hubungan di

antara objek-objek itu.

4. Aplikasi dan Pemodelan: memperkenalkan aplikasi

matematika diskri dan pemodelan matematika

sebagai salah satu kemampuan pemecahan

masalah yang sangat penting.

5. Berpikir algoritmik: memberikan kemampuan

membuat algoritma dan verikasinya serta

menganalisis memori komputer dan waktu yang

dibutuhkan untuk melakukan algoritma itu.

Beberapa alasan penting belajar matematika

diskrit adalah sebagai berikut:

a) Matematika diskrit memberikan kemampuan

membaca, memahami dan membangun argumen

matematika.

b) Matematika diskrit merupakan pintu gerbang untuk

mempelajari matakuliah lanjutan dalam logika, teori

himpunan, teori bilangan, aljabar linier, aljabar

abstrak, kombinatorika, teori graf,dan teori peluang.

c) Matematika diskrit memberikan landasan

matematika untuk mata kuliah ilmu komputer seperti

struktur data, algoritma, teori basis data, teori

114

automata, keamanan komputer (computer security),

dan sistem operasi.

d) Matematika diskrit memberikan latar belakang

matematika yang diperlukan dalam pemecahan

masalah riset operasi (operations research) seperti

teknik optimisasi diskrit.

Struktur diskrit mempelajari struktur matematika

yang memiliki objek atau elemen diskrit. Struktur atau

sistem matematika dide¯nisikan sebagai koleksi objek

dengan operasi yang terde¯nisi pada objek itu serta sifat-

sifatnya. Struktur diskrit berisi pokok bahasan:

Himpunan, Barisan, Fungsi, Logika, Teknik Membilang

(counting techniques), Relasi, Graf, dan Pohon.

Logika merupakan study penalaran (reasoning).

Pelajaran logika di fokuskan pada hubungan pernyataan –

penyataan (statements).

Contoh pernyataan :

Semua anak sekolah memakai rok

Setiap pemakai rok adalah anak perempuan

Jadi, semua anak sekolah adalah anak

perempuan

115

3. Perbedaan Dan Persamaan Materi Matematika

Diskrit Dengan Materi Di Sekolah

Dalam pembelajaran matematika perlu

disesuaikan dengan perkembangan kognitif siswa,

dimulai dari yang konkrit menuju abstrak. Namun

demikian meskipun obyek pembelajaran matematika

adalah abstark, tetapi mengingat kemampuan berpikir

siswa Sekolah Dasar yang masih dalam tahap operasional

konkrit, maka untuk memahami konsep dan prinsip

masih diperlukan pengalaman melalui obyek konkrit

Suatu konsep diangkat melalui manipulasi dan

observasi terhadap obyek konkrit, kemudian dilakukan

proses abstraksi dan idealisasi. Jadi dalam proses

pembelajaran matematika di SD peranan media/alat

peraga sangat penting untuk pemahaman suatu konsep

atau prinsip.

Di dalam GBPP mata pelajaran matematika SD

disebutkan bahwa tujuan yang akan dicapai dari

pembelajaran matematika sekolah adalah:

1. Menumbuhkan dan mengembangkan keterampilan

berhitung (menggunakan bilangan) sebagai alat

dalam kehidupan sehari-hari.

2. Menumbuhkan kemampuan siswa, yang dapat

dialihgunakan, melalui kegiatan matematika.

116

3. Mengembangkan pengetahuan dasar matematika

sebagai bekal lanjut di Sekolah Lanjutan Tingkat

Pertama (SLTP).

4. Membentuk sikap logis, kritis, cermat, kreatif dan

disiplin. (Depdikbud, 1993:40)

Sedangkan tujuan mata pelajaran matematika yang

tercantum dalam KTSP pada SD/MI adalah sebagai

berikut:

a) Memahami konsep matematika, menjelaskan

keterkaitan antar konsep dan mengaplikasikan

konsep atau algoritma, secara luwes, akurat,

efisien, dan tepat, dalam pemecahan masalah.

b) Menggunakan penalaran pada pola dan sifat,

melakukan manipulasi matematika dalam

membuat generalisasi, menyusun bukti, atau

menjelaskan gagasan dan pernyataan matematika.

c) Memecahkan masalah yang meliputi kemampuan

memahami masalah, merancang model

matematika, menyelesaikan model dan

menafsirkan solusi yang diperoleh

d) Mengkomunkasikan gagasan dengan simbol, table,

diagram, atau media lain untuk memperjelas

keadaan atau masalah

117

e) Memiliki sikap menghargai kegunaan matematika

dalam kehidupan, yaitu memiliki rasa ingin tahu,

perhatian, dan minat dalam mempelajari

matematika, serta sikap ulet dan percaya diri

dalam pemecahan masalah

(Depdiknas, 2006 : 417).

Ruang Lingkup Matematika Sekolah

Pembelajaran matematika di sekolah diarahkan

pada pencapaian standar kompetensi dasar oleh siswa.

Kegiatan pembelajaran matematika tidak berorientasi

pada penguasaan materi matematika semata, tetapi

materi matematika diposisikan sebagai alat dan sarana

siswa untuk mencapai kompetensi. Oleh karena itu, ruang

lingkup mata pelajaran matematika yang dipelajari di

sekolah disesuaikan dengan kompetensi yang harus

dicapai siswa. Standar kompetensi matematika

merupakan seperangkat kompetensi matematika yang

dibakukan dan harus ditunjukkan oleh siswa sebagai hasil

belajarnya dalam mata pelajaran matematika. Standar ini

dirinci dalam kompetensi dasar, indikator, dan materi

pokok, untuk setiap aspeknya. Pengorganisasian dan

pengelompokan materi pada aspek tersebut didasarkan

118

menurut kemahiran atau kecakapan yang hendak ingin di

capai.

Merujuk pada standar kompetensi dan kompetensi

dasar yang harus dicapai siswa maka ruang lingkup

materi matematika adalah aljabar, pengukuran dan

geomerti, peluang dan statistik, trigonometri, serta

kalkulus.

Kompetensi aljabar ditekankan pada kemampuan

melakukan dan menggunakan operasi hitung pada

persamaan, pertidaksamaan dan fungsi. Pengukuran dan

geometri ditekankan pada kemampuan menggunakan

sifat dan aturan dalam menentukan porsi, jarak, sudut,

volum, dan tranfrormasi. Peluang dan statistika

ditekankan pada menyajikan dan meringkas data dengan

berbagai cara. Trigonometri ditekankan pada

menggunakan perbandingan, fungsi, persamaan, dan

identitas trigonometri. Kalkulus ditekankan pada

mengunakam konsep limit laju perubahan fungsi.

Secara rinci, standar kompetensi mata pelajaran

matematika untuk sekolah menengah pertama adalah

sebagai berikut:

1. Bilangan

a) Melakukan dan mengunakan sifat-sifat operasi

hitung bilangan dalam pemecahan masalah

119

b) Menaksir hasil operasi hitung

2. Pengukuran dan Geometri

a) Mengidentifikasi bangun datar dan bangun ruang

menurut sifat, unsur, atau kesebangunannya

b) Melakukan operasi hitung yang melibatkan

keliling, luas, volume, dan satuan pengukuran

c) Menaksir ukuran (misal: panjang, luas, volume)

dari benda atau bangun geometri

d) Mengidentifikasi sifat garis dan sudut dalam

pemecahan masalah

3. Peluang dan statistika

a) Mengumpulkan, menyajikan, dan menafsirkan data

(ukuran pemusatan data)

b) Menentukan dan menafsirkan peluang suatu

kejadian

4. Aljabar

Melakukan operasi hitung pada persamaan,

pertidaksamaan, dan fungsi, meliputi: bentuk linear,

kuadrat, barisan dan deret, dalam pemecahan

masalah.

Sementara itu, standar kompetensi mata pelajaran

matematika untuk Sekolah Menengah Atas dan Madrasah

Aliyah adalah sebagai berikut:

1) Pengukuran dan geometri

120

Menggunakan sifat dan aturan dalam menentukan

posisi, jarak, sudut, volum, dan transformasi dalam

pemecahan masalah

2) Peluang dan Statistika

a) Menyusun dan menggunakan kaidah pencacahan

dalam menentukan banyak kemungkinan

b) Menentukan dan menafsirkan peluang kejadian

majemuk

c) Menyajikan dan meringkas data dengan berbagai

cara dan memberi tafsiran

3) Trigonometri

a) Menggunakan perbandingan, fungsi, persamaan,

dan identitas trigonometri dalam pemecahan

masalah

b) Menggunakan manipulasi aljabar untuk

merancang/menyusun bukti

4) Aljabar

a) Menggunakan operasi dan manipulasi aljabar

dalam pemecahanmasalah yang beraitan

dengan: bentuk pangkat, akar, logaritma,

persamaan dan fungsi komposisi dan fungsi

inver

b) Menyusun/menggunakan persamaan lingkaran

dan garis singgungnya

121

c) Menggunakan algoritma pembagian, teorema

sisa, dan teorema faktor dalam pemecahan

masalah

d) Merancang dan menggunakan model

matematika program linear

e) Menggunakan sifat dan aturan yang berkaitan

dengan barisan, deret, matriks, vektor,

transformasi, fungsi eksponen, dan logaritma

dalam pemecahan masalah

5) Kalkulus

Menggunakan konsep limit fungsi, turunan, dan

integral dalam pemecahan masalah

Contoh 6.1

Barisan Aritmetika

Matematika di sekolah Matematika Diskrit

Barisan aritmetika

merupakan salah satu dari

barisan bilangan yang

menjadi salah satu materi

pokok di dalam kurikulum

matematika sekolah

khsusnya di sekolah

menengah. Sebagai ciri

barisan dijumpai pada

pokok bahasan fungsi

pembangkit

122

utama dari barisan ini

adalah setiap suku yang

berurutan memiliki selisih

atau beda yang sama. Pokok

kajian substansi materi ini

adalah (1) menentukan

beda, (2) menentukan suku

ke-n dan (3) menghitung

jumlah n buah suku

berurutan.

4. Kesimpulan

1 Matematika sekolah mempunyai peranan yang

sangat penting baik bagi siswa supaya punya bekal

pengetahuan dan untuk pembentukan sikap serta

pola pikirnya, warga negara pada umumnya

supaya dapat hidup layak, untuk kemajuan

negaranya, dan untuk matematika itu sendiri

dalam rangka melestarikan dan

mengembangkannya.

2 Kajian materi matematika di sekolah masih dapat

dilanjutkan sampai dengan menemukan rumus

yang berbeda tetapi hasil penyelesaian sama.

123

3 Mahasiswa diharapkan mengembangkan

persamaan, perbedaan dan karakteristik

penyelesaian dari materi matematika sekolah

dengan matematika diskrit.

5. Latihan Soal

Buatlah laporan dari studi lapangan dengan aktivitas

sebagai berikut.

1. Menganalisis keterkaitan materi matematika

diskrit dengan materi matematika di SD, SMP dan

SMA

2. Menganalisis perbedaan dan persamaan materi

matematika diskrit dengan materi di

sekolahsecara luas

3. Menganalisis penyelesaian masalah yang ada di

sekolah

124

DAFTAR PUSTAKA

Depdiknas, (2006), Kurikulum Tingkat Satuan Pendidikan

Dediknas Jakarta.

Katz, B. P., & Starbird, M. (2013). Distylling Ideas: An

Introduction to Mathematical Thinking. America:

The Mathematical Association of America.

Muhsetyo, Gatot. 2007. Matematika Diskrit. Jakarta:

Universitas Terbuka.

Munir, R. 2005. Matematika Diskrit Edisi 3. Bandung:

Informatika Bandung.

Munir, Renaldi. 2009. Matematika Diskrit. Bandung:

Informatika Bandung

Munir, Rinaldi. 2012. Matematika Diskrit. Bandung :

Informatika.

Nurjanah, Priatna, Sutarno. 2003. Matematika Diskrit.

Malang: JICA

Purwanto. 1997. Bahan Ajar Matematika Diskrit. Malang:

Institut Keguruan dan Ilmu Pendidikan Malang

Siang, J.J. 2009. Matematika Diskrit dan Aplikasinya Pada

Ilmu Komputer. Yogyakarta: ANDI Press.

Townsend, Michael. 1987. Applied combinatorics and

Graph Theory. The Benjamin/cummings Publishing

Company, Inc.

Wibisono, Samuel. 2008. Matematika Diskrit. Yogyakarta:

Graha Ilmu.

125

SOAL DAN PENYELESAIAN 1

Induksi Matematika

1. Untuk semua bilangan bulat tidak-negatif n, buktikan

dengan induksi matematik bahwa 20 + 21 + 22 + … +

2n = 2n+1 – 1

2. Buktikan pernyataan “Untuk membayar biaya pos

sebesar n sen (n 8) selalu dapat digunakan hanya

perangko 3 sen dan perangko 5 sen” benar.

3. 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.

4. Tunjukkan apa yang salah dari pembuktian di bawah

ini yang menyimpulkan bahwa semua kuda berwarna

sama?

5. Temukan kesalahan dalam pembuktian berikut. Kita

ingin membuktikan bahwa an = 1 untuk semua

bilangan bulat tak-negatif n bilamana a adalah

bilangan riil tidak-nol. Kita akan membuktikan ini

dengan prinsip induksi kuat.

126

Penyelesaian 1

1. (i) Untuk n = 0 (bilangan bulat tidak negatif pertama),

kita peroleh:

20 = 20+1 - 1.

Ini jelas benar, sebab 20 = 1 = 20+1 - 1

= 21 - 1

= 2 - 1

= 1

(ii) Andaikan bahwa untuk semua bilangan bulat

tidak-negatif n,

20 + 21 + 22 + … + 2n = 2n+1 – 1 adalah benar (hipotesis

induksi). Kita harus menunjukkan bahwa

20 + 21 + 22 + … + 2n + 2n+1 = 2(n+1) + 1 – 1 juga benar. Ini

kita tunjukkan sebagai berikut:

20 + 21 + 22 + … + 2n + 2n+1 = (20 + 21 + 22 + … +

2n) + 2n+1

= (2n+1 - 1) + 2n+1 (dari

hipotesis induksi)

= (2n+1 + 2n+1) - 1

= (2 . 2n+1) – 1

= 2n+2 - 1

= 2(n+1) + 1 - 1

127

Karena langkah 1 dan 2 keduanya telah diperlihatkan

benar, maka untuk semua bilangan bulat tidak-negatif

n, terbukti bahwa 20 + 21 + 22 + … + 2n = 2n+1 - 1

2. (i) Untuk membayar biaya pos 8 sen dapat digunakan

1 buah perangko 3 sen dan 1 buah perangka 5 sen

saja. Ini jelas benar.

(ii) Andaikan bahwa untuk membayar biaya pos

sebesar n (n 8) sen dapat digunakan perangko 3 sen

dan 5 sen (hipotesis induksi). Kita harus

menunjukkan bahwa untuk membayar biaya pos

sebesar n + 1 sen juga dapat menggunakan perangko

3 sen dan perangko 5 sen. Ada dua kemungkinan

yang perlu diperiksa:

a. Kemungkinan pertama, misalkan kita membayar

biaya pos senilai n sen dengan sedikitnya satu

perangko 5 sen. Dengan mengganti satu buah

perangko 5 sen dengan dua buah perangko 3 sen,

akan diperoleh susunan perangko senilai n + 1 sen.

b. Kemungkinan kedua, jika tidak ada perangko 5 sen

yang digunakan, biaya pos senilai n sen

menggunakan perangko 3 sen semuanya. Karena n

8, setidaknya harus digunakan tiga buah

perangko 3 sen. Dengan mengganti tiga buah

128

perangko 3 sen dengan 2 buah perangko 5 sen,

akan dihasilkan nilai perangko n + 1 sen.

3. (i) Jika n = 2, maka 2 sendiri adalah bilangan prima

dan di sini 2 dapat dinyatakan sebagai perkalian dari

satu buah bilangan prima, yaitu dirinya sendiri.

(ii) Misalkan pernyataan bahwa bilangan 2, 3, …, n

dapat dinyatakan sebagai perkalian (satu atau lebih)

bilangan prima adalah benar (hipotesis induksi). Kita

perlu menunjukkan bahwa n + 1 juga dapat

dinyatakan sebagai perkalian bilangan prima. Ada

dua kemungkinan nilai n + 1:

a. Jika n + 1 sendiri bilangan prima, maka jelas ia

dapat dinyatakan sebagai perkalian satu atau

lebih bilangan prima.

b. 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 (i) dan (ii)

sudah ditunjukkan benar, maka terbukti bahwa

129

setiap bilangan bulat positif n (n 2) dapat

dinyatakan sebagai perkalian dari (satu atau

lebih) bilangan prima.

4. Misalkan P(n) adalah pernyataan bahwa semua kuda

di dalam sebuah himpunan berwarna sama

(i) Jika kuda di dalam himpunan hanya seekor,

jelaslah P(1) benar.

(ii) Andaikan bahwa semua kuda di dalam himpunan n

ekor kuda berwarna sama adalah benar. Tinjau

untuk himpunan dengan n + 1 kuda; nomori kuda-

kuda tersebut dengan 1, 2, 3, …, n, n+1. Tinjau dua

himpunan, yaitu n ekor kuda yang pertama (1, 2,

…n) harus berwarna sama, dan n ekor kuda yang

terakhir (2, 3, …, n, n+1) juga harus berwarna

sama. Karena himpunan n kuda pertama dan

himpunan n kuda terakhir beririsan, maka semua

n+1 kuda harus berwarna sama. Ini membuktikan

bahwa P(n+1) benar.

Penyelesaian: langkah induksi tidak benar jika n +

1 = 2, sebab dua himpunan (yang masing-masing

beranggotakan n = 1 elemen) tidak beririsan.

5. (i) Untuk n = 0, jelas a0 = 1 adalah benar sesuai

definisi a0.

130

(iii) Misalkan pernyataan tersebut benar untuk 0, 1, 2,

…, n, yaitu a0 = 1, a1 = 1, a2 = 1, …, an = 1. Kita

ingin memperlihatkan bahwa a(n+1) = 1. Untuk

menunjukkan hal ini, maka

an+1 =

=

(dari hipotesis induksi)

= 1

Penyelesaian: Kesalahan terjadi pada langkah

induksi, karena untuk n = 0 kita tidak dapat

menghitung

a0+1 =

sebab nilai a–1 tidak terdapat dalam hipotesis

induksi.

131


Kombinatorika

1. Berapa banyak “kata” yang terbentuk dari kata

“HAPUS”?

2. Lima putra dan tiga putri duduk berderet pada 8 kursi

kosong sesuai dengan 8 lembar karcis bioskop yang

mereka miliki. Berapa banyak cara untuk duduk yang

diperoleh dengan urutan berbeda jika :

a. Putra dan putri dapat duduk di sembarang kursi?

b. Putra dan putri masing-masing mengelompok

sehingga hanya sepasang putra dan putri yang dapat

duduk berdampingan?

3. 8 anak pada suatu acara saling berjabat tangan satu

sama lain. Tentukan banyaknya jabat tangan yang

terjadi!

4. Berapa koefisien x2y3dalam penjabaran (x + y)5 ?

5. Berapa koefisien dalam z2 y3 z dalam (x + 2y – z)6 ?

132

Penyelesaian 2

1. 5! = 5 x 4 x 3 x 2 x 1 = 120 buah kata

2. a. Terdapat 8 orang yang menempati 8 kursi dimana

perbedaan urutan duduk memberikan hasil yang

berbeda, P(8, 8) = 8! = 8 x 7 x 6 x 5 x 3 x 2 x 1 = 40.320

cara

b. 5 orang putra duduk pada 5 kursi tertentu dan

pertukaran duduk hanya boleh pada ke 5 kursi

tersebut, sehingga banyaknya cara duduk putra adalah

P(5, 5). Demikian juga 3 putri duduk pada tiga kursi

tertentu dan pertukaran duduk diatara mereka hanya

boleh pada ke 3 kursi ini, sehingga banyaknya cara

untuk duduk putri adalah P(3, 3). Dengan demikian,

banyak cara duduk 5 putra dan 3 putri yang masing-

masing mengelompok adalah P(5, 5) x P(3, 3) = 5! X 3!

= 720

3. Kombinasi dengan n = 8 dan r = 2

8C2 =

28 jabat tangan

4.

= 10

5. (2)3 (-1)

= (-8) (60) = -480

133


Fungsi Pembangkit Biasa

1. Tentukan fungsi pembangkit dari xxf

21

1)(

2. Tentukan turunan ke-n disekitar x = 0, dari x1

1)x(f

3. Tentukan fungsi pembangkit dari barisan 1,1,1,1, ......

4. Carilah barisan yang dibentuk oleh fungsi pembangkit

f (x) =

5. Berapa banyak solusi dari persamaan: ;

dengan a dan b bilangan

bulat.

134

Penyelesaian 3

1.

∑

∑

2.

3

4

3. Fungsi pembangkit dari barisan adalah

135

4.

Jadi

adalah fungsi pembangkit dari barisan

5. Dengan menggunakan fungsi pembangkit maka

masalah diatas analog dengan mencari koefisien

pangkat 13 dari:

( )

suku yang memuat pangkat 13 adalah: x4y9, x5y8, x6y7,

x7y6.

Jadi banyaknya penyelesaian ada 4.

136


Relasi Rekursif

1. Suatu virus berkembang biak dalam tubuh seorang

pasien, sebanyak 1 virus masuk ke dalam tubuh dan

di minggu pertama berkembang menjadi 5 virus, di

minggu ke-2 berkembang menjadi 12 virus, dan

untuk minggu seterusnya terus berkembang biak dan

semakin bertambah banyak hingga di minggu ke-3 si

pasien terjangkit 22 virus, di minggu ke-4 menjadi 35

virus, dan di minggu ke-5 menjadi 51 virus. Dari

kasus di atas buatlah relasi rekursifnya.

2. Carilah relasi berulang dengan syarat awal dari

barisan 1, 1, 2, 4, 16, 128, 4096, . . .

3. Buatlah rekursif dari:

a. Pola bilangan segitiga !

b. Kasus segitiga pascal!

4. Tentukan solusi homogen dari relasi rekurensi

dengan kondisi batas

5. Pada suatu kotak terdapat 110 permen karet yang

berbentuk bola. Untuk mengambil permen tersebut

harus menggunakan koin. Permen karet tersebut

akan keluar sesuai dengan berapa banyak koin yang

akan kita masukkan. Ada beberapa anak kecil yang

137

mengambil permen karet tersebut, sehingga permen

dalam kotak tersebut habis tidak tersisa. Carilah

relasi rekursifnya dan rumus !

138

Penyelesaian 4

1.

Maka didapat relasi rekursifnya

2. Bentuk rumusan setiap suku dengan menggunakan

suku sebelumnya

1 = 1

1 = 1 x 1

2 = 2 x 1 x 1

4 = 2 x 2 x 1

16 = 2 x 4 x 2

128 = 2 x 16 x 4

4096 = 2 x 128 x 16 x 4

Dengan demikian relasi yang berulang yang diperoleh

adalah an = 2 x an-1 x 2 x an-2 untuk n≥2

Dengan syarat awal a0 = 1 dan a1 = 1

3. a. Kasus pola bilangan segitiga

139

a0 = 1

a1= 3 a0+ 2 an-1 + (n +1)

a2= 6 a1+ 3 an-1 + (n +1)

a3= 10 a2+ 4 an-1 + (n +1) rekursifnya an-1 + (n +1)

a4= 15 a3+ 5 an-1 + (n +1)

a5= 21 a4+ 6 an-1 + (n +1)

b. Kasus segitiga Pascal

1 = 1

1 1 = 2

1 2 1 = 4

1 3 3 1 = 8

1 4 6 4 1 =16

1 5 10 10 5 1 = 32

1 3 6 1 15 2

140

a0 = 1

a1 = 2 2 x a0 2(an-1)

a2 = 4 2 x a12(an-1)

a3 = 8 2 x a22(an-1) rekursifnya 2(an-1)

a4 = 16 2 x a32(an-1)

a5 = 32 2 x a42(an-1)

4. Relasi rekurensi tersebut adalah relasi rekurensi

homogen, karena f(n) = 0.

Persamaan karakteristik dari relasi rekurensi :

adalah atau

Hingga diperoleh akar-akar karakteristik dan

Oleh karena akar-akar karakteristiknya berbeda,

maka solusi homogennya berbentuk

Dengan kondisi batas dan , maka :

Bila diselesaikan maka akan diperoleh harga

dan

, sehingga jawab homogen dari relasi

rekurensi adalah

141

Jika akar karakteristik dari persamaan

karakteristik merupakan akar ganda yang berulang

sebanyak m kali, maka bentuk solusi homogen yang

sesuai akar ganda tersebut adalah

Dimana adalah konstanta yang nantinya akan

ditentukan untuk memenuhi kondisi batas yang

ditentukan.

5. Anak pertama memasukkan 2 koin maka akan keluar

2 permen karet

Anak ke dua memasukkan 4 koin maka akan keluar 4

permen karet

Anak ke tiga memasukkan 6 koin maka akan keluar 6

permen karet

Anak ke empat memasukkan 8 koin maka akan keluar

8 permen karet

Anak ke lima memasukkan 10 koin maka akan keluar

10 permen karet

Anak ke enam memasukkan 12 koin maka akan

keluar 12 permen karet

𝐴 𝑛𝑚 𝐴 𝑛

𝑚 𝐴𝑚 𝑛 𝐴𝑚 𝑚 𝐴𝑚

𝑛

142

Anak ke tujuh memasukkan 14 koin maka akan


Anak ke delapan memasukkan 16 koin maka akan


Anak ke sembilan memasukkan 18 koin maka akan


Anak ke sepuluh memasukkan 20 koin maka akan


rekursifnya:

2, 4, 6, 8, 10, 12, 14, 16, 18, 20

Rumus

MATEMATIKA DISKRIT

DAN APLIKASINYA

DALAM MATEMATIKA KONTEKSTUAL

Buku Ajar ini mengulas tentang Induksi Matematika,

Prinsip Dasar Membilang, Kombinatorik, Fungsi

Pembangkit, Pengantar Dasar Teori Graph dan

Keterkaitan Matematika Diskrit dengan Matematika

Sekolah. Setiap pokok bahasan disertai dengan contoh

pemahaman konsep, penalaran komunikasi dan

kontekstual.

Buku Ajar ini sangat bermanfaat bagi mahasiswa dalam

memahami mata kuliah Matematika Diskrit secara

kontekstual. Soal latihan yang di sajikan dalam Buku Ajar

ini dikemas sedemikian hingga dapat meningkatkan

kemampuan menyelesaikan soal matematika kontekstual.

Variasi soal dalam Buku Ajar ini juga sangat bermanfaat

bagi dosen pengampu sebagai referensi soal yang

meliputi soal pemahaman konsep, penalaran komunikasi

dan soal matematika kontekstual.

matematika diskrit · iii prakata alhamdulillahirabbil'aalamin, penulis panjatkan sebagai rasa...

Documents