Makalah Induksi Matematika

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 v₀ anggota V sedemikian sehingga v₀ ≤ 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 ≥ n₀. Prinsip Induksi Matematika dapat dimodifikasi untuk mengatasi kasus seperti itu.

B.        Prinsip Induksi Matematika (versi kedua)
Misalkan n₀ anggota N dan misalkan P(n) merupakan pernyataan untuk setiap bilangan asli n ≥ n₀. Apabila:
(1) Pernyataan P(n₀) benar;
(2) Untuk setiap k ≥ n₀, jika P(k) benar mengakibatkan P(k + 1) benar.
Maka P(n) benar untuk semua n ≥ n₀.

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 2ⁿ × 2ⁿ (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 2¹ × 2¹ 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 2^{k + 1} × 2^{k + 1} yang salah satu persegi di bagian pojok dihilangkan. Bagilah papan catur tersebut menjadi 4 papan catur 2^k × 2^k 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 2^{k + 1} × 2^{k + 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 2^{k + 1} × 2^{k + 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/