INDUKSI
MATEMATIKA
Paper
ini disusun untuk memenuhi syarat tugas perkuliahan
Struktur
Diskrit
Di
Susun Oleh :
Andy
Haryadi (13.11.0219)
JURUSAN
TEKNIK INFORMATIKA
SEKOLAH
TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER AMIKOM
PURWOKERTO
2015
KATA PENGANTAR
Kebenaran
pernyataan matematika yang berkaitan dengan bilangan bulat perlu pembuktian
salah satu metode pembuktian dapat menggunakan Induksi matematik. Sedangkan
untuk mengetahui banyak cara pengurutan bilangan disebut teori kombinatorik. Dalam
menentukan banyak cara pengurutan bilangan ini
dapat digunakan metode permutasi dan kombinasi permutasi.
Purwokerto,
09 Maret 2015
Penyusun
Kelompok
Induksi matematika (mathematical induction)
adalah metode pembuktian yang sering digunakan untuk
menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan
asli. Akan tetapi sebelum membahas mengenai induksi matematika, kita akan
membahas suatu prinsip yang digunakan untuk membuktikan induksi matematika,
yaitu prinsip terurut rapi (well-ordering principle) dari bilangan asli.
Seperti kita ketahui, himpunan bilangan asli adalah himpunan yang memiliki
anggota 1, 2, 3, … yang dapat dituliskan sebagai berikut.
Setelah
mengingat mengenai himpunan bilangan asli, sekarang perhatikan prinsip terurut
rapi dari bilangan asli berikut.
Prinsip
Terurut Rapi Bilangan Asli
Setiap himpunan bagian yang tidak
kosong dari N memiliki anggota terkecil.
Secara
lebih formal, prinsip tersebut menyatakan bahwa untuk setiap himpunan tidak
kosong V yang merupakan himpunan bagian dari N, maka ada v0
anggota V sedemikian sehingga v0 ≤ v untuk setiap v
anggota V.
Berdasarkan
prinsip terurut rapi di atas, kita akan menurunkan prinsip induksi matematika
yang dinyatakan dalam bentuk himpunan bagian N.
A. Prinsip Induksi Matematika
Misalkan S adalah himpunan bagian N
yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.
Sebelum
membuktikan prinsip induksi matematika di atas secara formal, kita akan mencoba
memahaminya dengan menggunakan efek domino seperti berikut.
Pada gambar (a) di atas kita melihat sebaris 4 domino
pertama yang ditata rapi dengan jarak antara masing-masing domino yang
berdekatan kurang dari tinggi domino. Sehingga, jika kita mendorong domino
nomor k ke kanan, maka domino tersebut akan merebahkan domino nomor (k
+ 1).
Proses ini ditunjukkan oleh gambar (b). Kita tentu akan
berpikir bahwa apabila proses ini berlanjut, maka domino nomor (k + 1)
tersebut juga akan merebahkan domino di sebelah kanannya, yaitu domino nomor (k
+ 2), dan seterusnya.
Bagian (c)
menggambarkan bahwa dorongan terhadap domino pertama merupakan analogi dari
bilangan 1 menjadi anggota himpunan S. Hal ini merupakan langkah dasar
dari proses efek domino. Selanjutnya, jika k anggota S akan
menyebabkan (k + 1) anggota S, akan memberikan langkah induktif
dan melanjutkan proses perebahan domino. Sehingga, pada akhirnya kita akan
melihat bahwa semua domino akan rebah. Atau dengan kata lain, domino yang
memiliki nomor urut semua bilangan asli akan rebah. Hal ini merupakan analogi
dari S = N. Bagaimana dengan bukti formal dari prinsip induksi
matematika?
Bukti Andaikan S ≠ N. Maka
himpunan N – S bukan merupakan himpunan kosong, sehingga
berdasarkan prinsip terurut rapi, himpunan tersebut memiliki anggota terkecil m.
Karena 1 anggota S (berdasarkan hipotesis 1), maka m > 1. Tetapi hal
ini akan mengakibatkan bahwa m – 1 juga merupakan bilangan asli. Karena m
– 1 < m dan m adalah anggota terkecil dari N – S, maka m
– 1 anggota S.
Sekarang
kita akan menggunakan hipotesis 2 bahwa k = m – 1 merupakan
anggota S, maka k + 1 = (m – 1) + 1 = m juga anggota S.
Akan tetapi pernyataan ini akan kontradiksi bahwa m bukan anggota S.
Sehingga N – S adalah himpunan kosong atau dengan kata lain N = S.
Selain
diformulasikan seperti di atas, Prinsip Induksi Matematika juga dapat
dinyatakan sebagai berikut.
Untuk
setiap n anggota N, misalkan P(n) merupakan suatu
pernyataan tentang n. Apabila:
1.
P(1) benar.
2.
Untuk
setiap k anggota N, jika P(k) benar, maka P(k
+ 1) benar.
Maka
P(n) benar untuk setiap n anggota N.
Hubungan Prinsip Induksi Matematika tersebut dengan
sebelumnya adalah dengan memisalkan S = {n anggota N | P(n)
adalah benar}. Sehingga kondisi 1 dan 2 pada Prinsip Induksi Matematika di awal
secara berturut-turut berkorespondensi dengan kondisi 1 dan 2 pada Prinsip
Induksi Matematika terakhir. Selain itu, kesimpulan S = N juga
berkorespondensi dengan kesimpulan P(n) benar untuk setiap n
anggota N.
Asumsi
bahwa “jika P(k) benar” dinamakan hipotesis induksi. Untuk
membangun hipostesis 2, kita tidak perlu menghiraukan kebenaran dari P(k),
tetapi yang perlu kita hiraukan adalah validitas dari “jika P(k),
maka P(k + 1)”. Misalkan, jika kita akan menguji pernyataan P(n):
“n = n + 5”, maka secara logis kondisi (2) adalah benar, dengan
menambahkan 1 pada kedua sisi P(k) untuk mendapatkan P(k
+ 1). Akan tetapi, karena pernyataan P(1): “1 = 6” adalah salah, kita
tidak dapat menggunakan Induksi Matematika untuk menyimpulkan bahwa n = n
+ 5 untuk setiap n anggota N.
Pada
beberapa kasus, kadang P(n) bernilai salah untuk beberapa
bilangan asli tertentu tetapi bernilai benar untuk n ≥ n0.
Prinsip Induksi Matematika dapat dimodifikasi untuk mengatasi kasus seperti
itu.
B.
Prinsip
Induksi Matematika (versi kedua)
Misalkan n0 anggota N dan
misalkan P(n) merupakan pernyataan untuk setiap bilangan asli n ≥ n0.
Apabila:
(1) Pernyataan P(n0) benar;
(2) Untuk setiap k ≥ n0, jika P(k) benar mengakibatkan P(k + 1)
benar.
Maka P(n) benar untuk semua n ≥ n0.
Berikut
ini adalah beberapa contoh yang menunjukkan bagaimana Induksi Matematika dapat
digunakan untuk membuktikan pernyataan tentang bilangan asli.
Contoh 1: Pengubinan dengan Tromino
Diberikan
suatu papan catur 2n × 2n (n >
0), dengan salah satu persegi di bagian pojok dihilangkan, buktikan bahwa papan
catur tersebut dapat ditutup sempurna dengan tromino. (Tromino adalah gambar
yang terdiri dari 3 persegi yang sisinya saling bersinggungan, tetapi 3 persegi
tersebut tidak dalam satu barisan yang berjajar)
Bukti Pernyataan tersebut benar untuk n = 1
karena secara jelas papan catur 21 × 21 yang salah satu
persegi bagian pojok dihilangkan memiliki bentuk yang sama dengan tromino.
Andaikan pernyataan tersebut benar untuk k anggota N. Diberikan
papan catur dengan ukuran 2k + 1 × 2k
+ 1 yang salah satu persegi di bagian pojok dihilangkan. Bagilah papan
catur tersebut menjadi 4 papan catur 2k × 2k
A, B, C, dan D, dengan satu di antaranya, yaitu A, memiliki bagian yang salah
satu persegi di pojok hilang. Tempatkan 1 tromino, T, di tengah-tengah papan
catur 2k + 1 × 2k + 1
sedemikian sehingga persegi-persegi tromino tersebut berada di bagian B, C, dan
D. Kemudian gunakan kasus n = k untuk menutup bagian A, B – T, C
– T, dan D – T dengan tromino. Proses tersebut akan menutup papan catur 2k
+ 1 × 2k + 1 tepat sempurna dengan
tromino-tromino. (Gambar di bawah ini mengilustrasikan untuk kasus n =
3)
Contoh
2: Jumlah n Bilangan Asli Pertama
Buktikan
untuk setiap n anggota N, jumlah dari n bilangan asli
pertama diberikan oleh rumus,
Bukti Kita akan mencoba membuktikan
pernyataan di atas dengan Prinsip Induksi Matematika yang dibahas di awal.
Misalkan S adalah himpunan yang memuat n anggota N
sedemikian sehingga rumus di atas bernilai benar. Kita harus menguji apakah
kondisi (1) dan (2) pada Prinsip Induksi Matematika terpenuhi. Jika n =
1, maka 1 = 1/2 ∙ 1 ∙ (1 + 1) sehingga 1 anggota S, dan (1) terpenuhi.
Selanjutnya, andaikan k anggota S maka kita akan menunjukkan k
+ 1 juga akan menjadi anggota S. Jika k angota S, maka
Jika
kita menambahkan k + 1 pada persamaan di atas, maka akan diperoleh
Karena
persamaan di atas merupakan pernyataan untuk n = k + 1, maka kita
menyimpulkan bahwa k + 1 anggota S. Sehingga, kondisi (2)
terpenuhi. Sebagai hasilnya, menurut Prinsi Induksi Matematika kita memperoleh
bahwa S = N, atau dengan kata lain persamaan tersebut berlaku
untuk semua bilangan asli.
Prinsip Induksi Sederhana
Misal p(n) menyatakan suatu pernyataan bilangan
bulat positip dan akan
dibuktikan bahwa pernyataan p(n)
tersebut benar untuk semua bilangan positip n
maka untuk membuktikan pernyataan
ini digunakan aturan
sbb:
Langkah 1 :
p(1) benar dan Langkah 2 : Untuk semua
bilangan bulat positi f n ≥ 1, jika p(n) benar
maka p(n +
1) juga benar.
Dimana langkah 1. disebut dengan
basis induksi dan langkah 2
disebut langkah induksi dengan
p(n) disebut hipotesis
induksi.
Contoh 3.1.
Buktikan bahwa 1+ 2 + 3 + … + n = n(n+1)/2 untuk setiap n bilangan bulat positip
Bukti : Langkah
1, Akan diperlihatkan pernyataan
benar untuk n = 1, untuk n = 1 maka 1 = 1(1+1)/2.
Langkah Induksi
Akan ditunjukkan pernyataan benar untuk setiap bilangan bulat n, n ≥ 1, apabila pernyataan benar untuk n =
k maka pernyataan benar untuk n = k + 1.
1.
Matematika
diskrit III-2
Bab III Induksi Matematik & kombinatorik
Jika diasumsikan
pernyataan 1 + 2 + 3+ … + n =
n(n+1) /2 benar maka
1 + 2 + 3 + … + n + (n+1)= (1 + 2 + 3 + … + n)
+(n+1) = n(n+1) /2 +
(n+1) = n(n+1)+ 2(n+1)
= 2 (
1) 2( 1) +++ n n n =
(n+1)(n+2)/2 =
(n+1)((n+1)+1)/2
Karena kedua langkah induksi telah terpenuhi
maka untuk setiap bilangan positip n
berlaku bahwa : 1 + 2 + 3 + … + n = n(n+1)/2
.
Contoh 3.2.
Buktikan
bahwa banyak n buah bilangan bulat
positif ganjil pertama
adalah n2
Bukti : Misalkan p(n)
merupakan pernyataan yang menyatakan
bahwa jumlah n
buah bilangan bulat positif
ganjil pertama adalah
n2, maka :
Langkah 1,
Untuk n = 1
maka 12 = 1 maka p(1)
benar , karena banyak buah bilangan ganjil positif pertama adalah
n2
Langkah
Induksi
Untuk n = n Andaikan
untuk n ≥ 1 pernyataan 1 + 3 + 5… + (2n-1) = n2 benar
maka akan ditunjukkan bahwa
1+ 3 + … + (2n-1) + (2n+1) = (n+1)2
yaitu 1 + 3 + … + (2n-1)+ (2n+1) =
{(1+2+3+ … +n)}+(2n+1)
2.
Matematika
diskrit III-3
Bab III Induksi Matematik & kombinatorik
=
n2 + (2n+1) =
n2 + 2n + 1 = (n+1)2
4.1.2.
Aplikasi Induksi Matematik
dalam program
Salah satu aplikasi induksi matematik dalam
pemrograman yaitu bentuk kalang (loop), dengan struktur sbb :
Keadaan sebelum menjumpai kalang( loop) While
s Perintah-perintah dalam tubuh kalang semua perintah tidak boleh melompat keluar kalang
End While Keadaan setelah kalang(loop)
Perintah While akan dieksekusi terus
menerus selama syarat kondisi S bernilai benar. Apabila
dalam proses kalang dijumpai kondisi bernilai salah (tidak memenuhi syarat yang
didefinisikan) eksekusi akan berhenti.
Teorema 3.1
: Kalang (loop) Diberikan Kalang While
dengan syarat kondisi
S, kondisi sebelum dan sesudah kalang. Jika diberikan predikat
I(n) yang disebut kalang invarian. Apabila keempat
syarat ini benar maka kalang
benar terhadap kondisi sebelum dan sesudahnya.
1. Langkah basis : Kondisi sebelum kalang berarti
bahwa I (0) benar sebelum
iterasi pertama dalam kalang.
2. Langkah induksi : Jika syarat kondisi S
dan kalang invariant I(k)
benar untuk suatu
bilangan bulat k ≥ 0 sebelum iterasi kalang, maka I(k+1) juga benar setelah iterasi kalang.
3.
Matematika
diskrit III-4
Bab III Induksi Matematik & kombinatorik
3. Kondisi penghentian Setelah sejumlah
iterasi kalang yang berhingga,
maka syarat kondisi S menjadi
salah. 4. Kebenaran kondisi setelah kalang
Jika untuk
suatu bilangan bulat tak negatif N,
syarat kondisi S salah dan
I(N) benar maka harga
variable akan sama dengan yang ditentukan dalam kondisi
kalang.( tanpa menggunakan operasi perkalian langsung)
Contoh 3.3.
Akan
dihitung hasil kali dua buah bilangan bulat positip, atau nilai nol c dan d, dengan
tanpa melalui operasi
perkalian langsung. Berikut ini
potongan algoritma pemrograman untuk menghitung hasil kali dua bilangan
bulat tersebut, dengan cara menjumlahkan
d sebanyak c kali yang hasilnya
c.d sbb :
i ← 0 J ← 0
while i ≠ c do
(1) J ← J + d i ← i+ 1 endwhile
(
i = c, J = c.d )
Buktikan
bahwa setiap kali
eksekusi mencapai awal kalang while-do 1), ditemukan J = i.d.
Bukti :
Algoritma
untuk enumerasi nilai i dan j
untuk setiap kali eksekusi
mencapai awal kalang while -
do tersebut dapat
diilustrasikan sbb:
Tabel eksekusi
while - do
4.
Matematika
diskrit III-5
Bab III Induksi Matematik & kombinatorik
Setiap kali (n) eksekusi Nilai mencapai awal loop i
Nilai j loop
ke 1 0 0 2 1 1. d 3 2 2. d 4 3 3. d c+1 c c.d
dari
tabel tersebut tampak
bahwa setiap kali eksekusi
algoritma mencapai awal kalang
while-do, nilai j = 1.d. Untuk
mengetahui kebenaranya dapat
digunakan induksi matematik.
Misal p(n) merupakan pernyataan
bahwa setiap kali yaitu n eksekusi algoritma
mencapai awal kalang
while – do, nilai i dan
j pada eksekusi ke n
dinyatakan in dan jn.
a) Langkah 1
.
untuk n = 1, pernyataan p(1) benar
karena pada saat n
= 1 eksekusi mencapai awal
kalang while – do i = 0
dan j = 0, serta nilai
jn= in .d = 0 adalah benar.
b) Langkah
induksi :
misal
pernyataan p(n) benar, dengan
asumsi bahwa jn = in .d saat eksekusi
mencapai awal kalang while – do. Akan ditunjukkan bahwa
p(n+1) benar yaitu saat
eksekusi mencapai awal
kalang while – do yang
ke (n+1) yang berarti jn+1 =
in+1 .d juga benar. Dari
tabel dapat dilihat
bahwa nilai i
yang baru bertambah
sebesar 1 dari nilai i yang
lama dan j yang baru bertambah
sebesar d dari nilai
j yang lama sehingga
in+1 = in + 1
dan
jn+1 = jn + d, dari
hipotesa induksi jn= in .d
maka jn+1 = (in.d) + d = (in + 1 ).d =
in+1 .d .
5.
Matematika
diskrit III-6
Bab III Induksi Matematik & kombinatorik
maka terbukti bahwa
setiap kali eksekusi algoritma mencapai
awal kalang while – do
nilai j= i.d.
Prinsip Umum Induksi
Prinsip
induksi sederhana dapat
digeneralisir sebagai berikut :
Misal p(n) adalah
pernyataan tentang bilangan
bulat dan akan membuktikan bahwa
pernyataan p(n) benar untuk semua
bilangan bulat n ≥ n0 . Untuk membuktikan pernyataan
tersebut kita hanya
perlu menunjukkan bahwa
:
i) p(n0) benar
dan ii) jika p(n) benar maka p(n+1)
benar untuk setiap n
≥ n0 , akibatnya pernyataan p(n)
benar untuk setiap bilangan bulat n
≥ n0
Kombinatorik
Kombinatorik (combinatorik) adalah cabang
matematika yang mempelajari
pengaturan objek-objek. Penyelesaian yang diperoleh adalah jumlah cara pengaturan obyek-obyek
tertentu dalam kelompoknya.
Contoh 3.4
:
1. Dari 30 anggota Fraksi
X di DPR, akan dibentuk sebuah
komisi yang beranggotakan 6
orang. Berapa banyak cara
memilih anggota komisi. 2. Password system
komputer panjangnya enam
sampai delapan karakter. Tiap
karakter boleh berupa huruf huruf atau
angka, huruf besar dan kecil tidak dibedakan. Berapa banyak password
dapat dibuat.
Aturan dasar
menghitung pada
Kombinatorik.
Didalam
kombinatorik semua kemungkinan
objek harus dihitung. Disini terdapat
dua aturan penghitungan yaitu
rule of product dan rule of sum
6.
Matematika
diskrit III-7
Bab III Induksi Matematik & kombinatorik
a.
Aturan
perkalian(rule of product):
Adalah aturan
untuk menghitung banyak
cara yang dapat dilakukan . - Missal suatu pekerjaan
melibatkan p buah langkah .
Langkah ke- 1
dapat dilakukan dalam
n1 cara. Langkah ke- 2 dapat dilakukan
dalam n2 cara. …….. Langkah ke- p dapat
dilakukan dalam np cara.
Maka
keseluruhan pekerjaan dapat
dilakukan dalam n1 . n2… np cara.
b. Aturan
penjumlahan (rule of sum ):
Missal suatu pekerjaan melibatkan p buah
langkah yang mungkin terjadi
Langkah ke- 1 dapat dilakukan
dalam n1 cara. Langkah ke- 2 dapat
dilakukan dalam n2 cara. …….. Langkah ke- p dapat
dilakukan dalam np cara.
maka
keseluruhan pekerjaan dapat
dilakukan dalam n1 + n2 +
…+ np
cara.
Contoh 3.5:
Jika
himpunan A adalah gabungan
dari himpunan-himpunan bagian tidak kosong yang saling asing H1, H2, …
Hn maka jumlah
anggota himpunan sama dengan jumlah
anggota semua himpunan bagiannya
atau |A| = |H1| +
| H2| + …+ |Hn|
Contoh 3.6 :
Dalam kotak
berisi kartu bridge lengkap, berapa
macam cara untuk
mengambil :
7.
Matematika
diskrit III-8
Bab III Induksi Matematik & kombinatorik
a. Sebuah
diamon atau sebuah
heart? b. Sebuah diamon atau kartu AS? c. Sebuah kartu bernomor 2 hingga 8 berwarna
merah.
4.3. Permutasi
dan Kombinasi
4.3.1. Permutasi
Pada subbab ini dibahas tentang
pengurutan dan pemilihan yang tidak boleh diulang .
Definisi 3.1. : Setiap pengelompokan berbeda atau
himpunan objek berurutan dinamakan
permutasi objek-objek tersebut.
Sebagai contoh bilangan 213
dan 312 terdiri atas tiga
angka yang sama tetapi kedua bilangan itu berbeda karena urutan angka 1, 2 dan 3 berbeda.
Umumnya urutan r objek dan diambil
r objek dengan r ≤ n dalam suatu urutan berhingga, maka pengelompokan
seperti itu disebut permutasi n
objek yang diambil r objek
pada suatu waktu. Banyak cara
yang berbeda dalam
penyusunan r objek
yang dipilih dari
n objek dilambangkan
P(n,r) atau nPr .
Untuk ilustrasi pada permutasi dari
angka 1, 2 dan 3. Langkah 1
: Pilih
sembarang elemen untuk
ditempatkan pada urutan pertama Langkah
2 : Pilih elemen untuk ditempatkan pada urutan kedua Langkah
3 : Pilih elemen untuk
ditempatkan pada urutan ketiga
Karena telah dipilih satu elemen (dari
tiga elemen ) untuk menduduki urutan pertama maka pada urutan kedua masih terdapat dua pilihan setelah terpilih urutan ke tiga
tinggal satu kemungkinan.
Dan karena pada ilustrasi ini n = 3 ( terdiri dari unsur 1, 2, 3 ) maka banyak kemungkinan urutan bilangan yang
terjadi
8.
Matematika
diskrit III-9
Bab III Induksi Matematik & kombinatorik
n(n-1)(n-2).....1 = 3 (3-1)(2-1) = 3.2.1 = 6
urutan yang berbeda atau
123 , 213, 321, 231, 312, 321 Teorema 3.1. :
Banyak
permutasi n objek yang
diambil r objek
pada suatu waktu
P( n ,r )
= n (n-1) (n-1) (n-1)…….. (n - r
+ 1)
(3.1)
Contoh 3.7 : Tentukan banyak permutasi yang terjadi dari empat
buah bilangan bulat 1, 2, 3 dan 4 yang
diambil dua bilangan suatu
waktu .
Jawab :
Banyak permutasi yang mungkin
terjadi dari empat bilangan yang diambil
dua bilangan
P(4, 2) = 4(4
- 1) = 12
Contoh 3.8 : Dengan
berapa cara empat buah buku dapat disusun dalam suatu rak.
Jawab : Pernyataan ini menyatakan permutasi dari
empat obyek yang diambil empat suatu waktu, yaitu
P(4,4) = 4(4-1)(4-2)(4-3) = 24
Jadi terdapat
dua puluh empat cara dalam menyusun buku dalam suatu
kotak.
Selanjutnya permutasi dari n buah objek yang diambil n objek pada suatu waktu
P(n,n) = n(n-1)(n-2)......3.2.1 = n!
(3.2)
Persamaan (3.1) dapat ditulis
9.
Matematika
diskrit III-10
Bab III Induksi Matematik & kombinatorik
P( n ,r ) = n
(n-1) (n-1) (n-1)…….. (n - r + 1).
(n r)(n r 1)...2.1 (n r)(n r 1)...2.1 − − − −−−
atau ( )! ! (
, ) n r n P n r − = (3.3)
Contoh 3.9:
a. 120 6 720 (6 3)! 6! P(6,3) =
b. P( 4 , 4 ) = 4 ! = 24
Contoh 3.10 : Tentukan jumlah
cara memasukkan 6 buah bola
yang berbeda warnanya
ke dalam tiga
buah kotak
Jawab:
Dari data tersebut
n = 6 (enam buah bola
yang berbeda warnanya) dan
r = 3 (tiga
buah kotak yang tersedia), maka jumlah
cara yang mungkin adalah
P(6,3) = (6 3)! 6! −
= 120
cara
Jadi banyak
cara untuk memasukkan enam bola kedalam suatu kotak adalah
enam. Contoh 3.11. Berapa
banyak permutasi dari huruf ABCDEF yang mengandung unsur ABC bersama sama
dalam urutan sembarang.
Jawab : Untuk menyelesaikannya dapat dipilih
pengurutan ABC. Jadi bentuk permutasi dari ABCDEF memuat pengurutan
dari huruf ABC, sehinnga pengurut huruf ABC dapat dilakukan dalam 3! atau 6 cara sedangkan
untuk huruf ABCDEF dapat dilakukan dalam
4! Atau 24 cara. Maka permutasi huruf
ABCDEF yang memuat huruf ABC
dapat dilakukan dalam 6 x 24 = 144.
10.
Matematika diskrit
III-11
Bab III Induksi Matematik & kombinatorik
Permutasi yang berkaitan
dengan pengambilan objek yang terdiri
atas bermacam-macam objek
dari suatu himpunan objek tercantum dalam teorema berikut.
Teorema 3.2.
Jika P
menyatakan banyak permutasi berbeda
dari n objek yang diambil p objek macam pertama , q objek macam
kedua , r objek macam ke
tiga dan seterusnya pada
suatu waktu
P =
p!q!r!... n!
Contoh 3.12:
Tentukan banyak permutasi yang terdapat
pada
a. Sepuluh huruf
dalam kata ‘Yogyakarta’
b. Delapan huruf
dalam kata ‘password’ yang
diambil bersama-sama.
Jawab:
a. Karena pada kata yogyakarta terdapat
tiga huruf a, dua huruf
y masing-masing satu huruf
g, k, o, r dan t maka banyak permutasi
P = 3!.2!.1!.1!.1!.1!.1! 10! = 302.400
b. Karena kata pasword terdiri atas dua kata s, satu kata
masing-masing a, p, w, o, r dan d, maka banyak permutasi
P = 2!.1!.1!.1!.1!.1!.1! 7! = 2520
11.
Matematika diskrit
III-12
Bab III Induksi Matematik & kombinatorik
4.3.2. Kombinasi
Himpunan atau
koleksi objek dengan
urutan yang tak tertentu
disebut kombinasi kombinasi.
Jadi kombinasi n objek
berbeda yang diambil r objek (r ≤
n) pada suatu waktu merupakan
susunan r objek berbeda dari n objek tanpa memperhatikan urutan.
Banyak kombinasi
n objek yang diambil r objek dinyatakan
C(n,r) atau nCr
atau ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛n r
Definisi 3.2:
Diberikan sebuah himpunan
X = { x1 , x2 , x3 …. xn }, yang memuat n
objek berbeda
a. Sebuah
r kombinasi dari
X adalah seleksi tak
terurut dari r- objek dari X yaitu
himpunan bagian yang terdiri atas
r objek dari n objek b. Banyak r kombinasi
dari sebuah himpunan
dengan n objek
yang berbeda dinotasikan
C(n,r)
atau = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛n r !( )! ! r n r n −
,
pernyataan
C(n,r) dibaca kombinasi banyak cara pengambilan dari n
buah data diambil sebanyak r untuk r ≤
n.
Contoh 3.13
:
Untuk
menghitung jumlah cara
memasukkan r buah
bola yang berwarna
ke dalam n
buah kotak adalah
C(n,r) =
!( )! ! r n r n −
Contoh 3.14:
Hitunglah : a. C( 5 , 3 )
dan C( 8 , 5 )
12.
Matematika diskrit
III-13
Bab III Induksi Matematik & kombinatorik
Jawab :
a. C(5 , 3) =
3!(5 3)! 5! − = 3.2.1.2.1 5.4.3.2.1= 3.2.1 5.4.3 = 10
Cara lain C(5
, 3) = 3! P(5,3) 3.2.1 5.4.3 = 10
Contoh 3.15
:
Sebuah
karakter ASCII berukuran
1 byte atau
8 bit (1 atau 0) Pertanyaan :
a. Berapa
banyak pola bit
yang terbentuk atau
berapa banyak karakter
dapat direpresentasikan.
b. Berapa
banyak pola bit
yang mempunyai 3 bit
1 ? c. Berapa banyak pola
bit yang mempunyai bil 1
sejumlah ganjil.
Jawab :
a Kemungkinan
bilangan bit muncul ada dua
yaitu 0 atau 1 dalam membentuk
pola bit karakter ASCII dalam
urutan : 0 1
2 3 4
5 6 7 ,
semua posisi urutan tersebut harus
diisi bilangan 0 atau 1 jadi
jumlah pola bit
yang terbentuk = 28 .
b. Banyaknya
pola bit yang mempunyai
3 bit 1 adalah
kombinasi dari delapan
dengan tiga atau
C(n,r) =
!( )! ! r n r n −
dengan n = 8 dan r
= 3
13.
Matematika diskrit
III-14
Bab III Induksi Matematik & kombinatorik
maka diperoleh
C(8,3) = 3!(8 3)! 8! −= 56
c.
Banyaknya pola bit yang
mempunyai 0 buah bit
1 = C(8,0) Banyaknya
pola bit yang mempunyai
1 buah bit 1 =
C(8,1) Banyaknya pola bit yang
mempunyai 3 buah bit
1 = C(8,3) Banyaknya pola bit
yang mempunyai 5 buah
bit 1 = C(8,5) Banyaknya pola bit
yang mempunyai 7 buah
bit 1 = C(8,7)
Maka banyak pola bit
yang mempunyai bil 1 sejumlah
ganjil = C(8,0) + C(8,1) + C(8,3) + C(8,5) +
C(8,7)
Resume :
1. Induksi
matematik
Induksi
matematik adalah suatu metode pembuktian kebenaran pernyataan matematik yang menyangkut bilangan bulat positip. Misal p(n) menyatakan suatu pernyataan
bilangan bulat positip dan akan
dibuktikan bahwa pernyataan
tersebut benar untuk semua bilangan positip n
maka untuk membuktikan pernyataan
ini digunakan aturan
sbb:
Langkah 1 :
p(1) benar dan Langkah 2 : Untuk semua
bilangan bulat positi f
n ≥ 1, jika p(n) benar maka p(n
+ 1) juga benar.
dimana langkah 1. disebut dengan
basis induksi dan langkah 2
disebut langkah induksi dengan
p(n) disebut hipotesis
induksi.
2. Permutasi
Permutasi dari
x1 , x2 x3 .... xn adalah
banyaknya pengurutan dari x1 , x2 x3 .... xn.
Banyak permutasi
dari n unsur dinyatakan dengan
n!.
14.
Matematika diskrit
III-15
Bab III Induksi Matematik & kombinatorik
P(n,r)
menyatakan permutasi r unsur dari
sebuah himpunan n unsur dinyatakan
( )! !
( , )
n r n
P n r −
= Banyak permutasi
n objek yang diambil
r objek pada suatu
waktu dinyatakan
P( n ,r ) = n (n-1) (n-1)
(n-1)…….. (n - r + 1)
3.
Kombinasi
Kombinasi r dari { x1 , x2 x3 .... xn } adalah sub himpunan yang tidak memperhatikan
urutan dari { x1 , x2 x3 .... xn } yang
mengandung r unsur yang dirumuskan sebagai
berikut C(n , r) = C(n,r) =
!( )! ! r n r n −
Referensi
1. Johnsonbaugh,
2005, Discrete Mathematics , Prentice Hall.
2. Munir R, 2005,
Matematika Diskrit', Informatika
Bandung.
3. Susana, 2004, “ Discrete Mathematics with Aplications “, Thomson Learning Inc Singapore
4. http://apaadanya-as.blogspot.com/2014/01/induksi-matematik-dalam-matematika.html
5. https://yos3prens.wordpress.com/2013/10/06/induksi-matematika/
