Matematika Diskrit

PERMUTASI DAN KOMBINASI

If you can DREAM it, you CAN DO IT...!!!

- Walt Disney

Matematika Diskrit merupakan mata kuliah dasar yang berisi dasar-dasar logika matematika yang diperlukan untuk pembelajaran lebih lanjut di bidang Ilmu Komputer. Mata kuliah ini diajarkan pada semester awal dengan beban 2 sks. Dan salah satu tuntutan materi yang harus dikuasai mahasiswanya adalah materi Permutasi dan Kombinasi yang akan di bahas lebih lanjut saat ini.

I. Permutasi

Di dalam ilmu matematika permutasi diartikan sebagai sebuah konsep penyusunan sekumpulan objek/angka menjadi beberapa urutan berbeda tanpa mengalami pengulangan.

Di dalam permutasi, urutan sangat diperhatikan. setiap objek yang dihasilkan harus berbeda antara satu dengan yang lain. kita ambil contoh, urutan huruf ({ABC} berbeda dengan {CAB} begitu juga dengan {BAC) dan {ACB}). Berikut di bawah akan dijelaskan pula jenis-jenis permutas.

1.1 Jenis-jenis Permutasi

a.     Permutasi dari n elemen, setiap permutasi terdiri dari n elemen

Jika ada unsur yang berbeda diambil n unsur, maka banyaknya susunan (permutasi) yang berbeda dari n unsur tersebut adalah P_(n,n) = n! atau _nP_n = n!

Contoh:

Untuk menyambut sebuah pertemuan delegasi negara yang dihadiri oleh lima negara, panitia akan memasang kelima bendera dari lima negara yang hadir. Banyak cara panitia menyusun kelima bendera tersebut adalah...

Jawab :

Dari lima bendera yang ada, berarti n = 5, maka banyak susunan bendera yang mungkin yaitu:

5! = 5.4.3.2.1 = 120 cara.

b.   Permutasi n elemen, tiap permutasi tersendiri dari r unsur dari n elemen dengan r<=n 

Syarat : Urutan di perhatikan

Contoh:

Banyak cara untuk memilih seorang ketua, sekertaris dan bendahara dari 8 siswa yang tersedia adalah…

Jawab:

Banyak siswa, n = 8

Ketua, sekretaris dan bendahara (banyak pilihan objek), r = 3

Maka:

c.      Permutasi dari n unsur yang mengandung p, q, dan r unsur yang sama

Keterangan:

n    = banyaknya elemen seluruhnya

k₁  = banyaknya elemen kelompok 1 yang sama

k₂  = banyaknya elemen kelompok 2 yang sama

…

k_t   = banyaknya elemen kelompok kt yang sama

t = 1,2,3,…

Contoh:

Banyak cara untuk menyusun dari kata ”BASSABASSI” adalah…

Jawab:

Dari kata ”BASSABASSI”, banyak huruf (n) = 10

k₁ = huruf B = 2

k₂ = huruf A = 3

k₃ = huruf S = 4

k₄ = huruf I = 1

d.      Permutasi Siklis

Permutasi siklis adalah permutasi melingkar (urutan melingkar).

Contoh:

Dari 5 orang anggota keluarga akan duduk mengelilingi sebuah meja bundar, banyak cara susunan yang dapat dibuat dari 5 orang tersebut adalah...

Jawab:

Banyak orang (n) = 5, maka :

₅P_siklis = (5 – 1)! = 4! = 4.3.2.1 = 24 cara.

e.      Permutasi berulang dari n unsur, tipe permutasi terdiri dari k unsur

Contoh:

Banyak susunan 3 bilangan dari angka-angka 1, 2, 3, 4, 5 dan 6 adalah…

Jawab:

Banyak susunan 3 bilangan, berarti bilangan ratusan, k = 3
Banyak angka yang akan disusun, n = 6
Banyak susunan 3 bilangan dari angka 1, 2, 3, 4, 5, dan 6:

P₆ = 6³ = 216 susunan.

II. Kombinasi

Kombinasi merupakan sebuah kumpulan dari sebagian atau seluruh objek dengan tidak memperhatikan urutannya. di dalam kombinasi, {AB} dianggap sama dengan {BA} sehingga sebuah kombinasi dari dua objek yang sama tidak dapat terulang.

Rumus Kombinasi :

Contoh

Manuel Pelegrini membawa 16 pemain saat Manchester City melawan Liverpool di Etihad Stadium. 11 orang diantaranya akan dipilih untuk bermain pada babak pertama. jika kita tidak memperhatikan posisi pemain, berapakah banyaknya cara yang dapat diambil oleh pelatih untuk memilih pemain?

Jawab :

Karena tidak mementingkan posisi pemain, maka kita gunakan rumus kombinasi:

¹⁶C₁₁ =       16!        =  16 x 15 x 14 x 13 x 12 x 11!  

              11!(16-11)!                      11!5!                          

      =          524160         =  524160  = 4368

     5 x 4 x 3 x 2 x 1          120

III. Perbedaan Permutasi dan Kombinasi

Perbedaan antara permutasi dan kombinasi adalah permutasi memperhatikan urutan susunan anggota sedangkan kombinasi tidak memperhatikan urutan susunan anggota. Hal ini dapat dilihat dari kedua contoh diatas, yaitu permutasi dan kombinasi dari 2 anggota dari himpunan yang terdiri dari huruf a, b, dan c.

P(3,2) = 6 Keenam cara tersebuat adalah: ab, ac, ba, bc, ca, cb.

C(3,2) = 3 Ketiga cara tersebuat adalah: ab, ac, bc.

Matematika Diskrit

INDUKSI MATEMATIKA

Success is no accident.

Its hars work, preseverance, learning, studying, sacrifice and most of all,

Love of you are doing or learning to do.

-          PELE

Dalam matematika diskrit, induksi matematika digunaan sebagai pembukti yang baku dari suatu pernyataan. Metode pembuktian ini digunakan untuk membuktikan pernyataan yang bergantung pada bilangan bulat positif.

3.1 Definisi

Induksi matematika (Mathematical induction) merupakan metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang di berikan dalam bentuk bilangan asli. Induksi matematika dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk kedalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.

Contoh :

1.     Jumlah bilangan bulat positif dari 1 sampai n adalah  

Bukti :

Misalkan n = 6 --> p(6) adalah “Jumlah bilangan bulat positif dari 1 sampai 6 adalah "(6+1)/2 ” terlihat bahwa :

           1 + 2 + 3 + 4 + 5 + 6 = 21 --> 6(7)/2 = 21

Sehingga proposisi (pernyataan) tersebut benar.

2.   Jumlah n buah bilangan ganjil positif pertama adalah n²

Bukti :

Misalkan n = 6buah (n = 1,2,3,4,5,6) maka :

¤  n = 1 à 1 = 1                                       à (1)² = 1

¤  n = 2 à 1 + 3 = 3                                 à (2)² = 4

¤  n = 3 à 1 + 3 + 5 = 9                           à (3)² = 9

¤  n = 4 à 1 + 3 + 5 + 7 = 16                   à (4)² = 16

¤  n = 5 à 1 + 3 + 5 + 7 + 9 = 25             à (5)² = 25

¤  n = 6 à 1 + 3 + 5 + 7 + 9 + 11 = 36     à (6)² = 36

Sehingga proposisi (pernyataan) tersebut benar.

3.2 Prinsip Induksi Matematika

Induksi matematika (Mathematical induction) merupakan metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan asli.

1.   Prinsip Induksi Sederhana

      Basis Induksi

Ø  Digunakan untuk memperlihatkan bahwa pernyataan benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil.

Ø  Buat implikasi untuk fungsi berikutnya benar untuk setiap bilangan bulat positif.

      Langkah Induksi

Ø  Berisi asumsi (andaian) yang menyatakan bahwa p(n) benar.

Ø  Asumsi tersebut dinamakan hipotesis  induksi.

      Bila kedua langkah tersebut benar maka pembuktian bahwa p(n) benar untuk semua bilangan positif n.

Contoh :

a.     Tunjukkan bahwa untuk n ≥ 1, 1 + 2 + 3 + ... + 4 = n(n+1)/2 melalui induksi matematika.

ü  Basis Induksi

P(1) benar --> n = 1 diperoleh dari :

          1 = 1(1+1)/2

             = 1(2)/2

             = 2/2

             = 1

ü  Langkah Induksi

Misalkan p(n) benar à asumsi bahwa :

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

Adalah benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar yaitu :

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

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

                                       = [n(n+1)/2] + (n+1)

                                       = [(n²+n)/2] + (n+1)

                                       = [(n²+n)/2]+[(2n+2)/2]

                                       = (n²+3n+2)/2

                                       = (n+1) (n+2)/2

                                       = (n+1) [(n+1)+1]/2

Langkah (i) dan (ii) dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ≥ 1, 1+2+3+...+n = = n(n+1)/2

b.   Gunakan induksi matematika untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n².

ü  Basis Induksi

P(1) benar --> jumlah 1 buah bilangan ganjil positif pertama adalah 1² = 1

ü  Langkah Indusi

Misalkan p(n) benar à asumsi bahwa :

          1+3+5+...+(2n-1) = n²

Adalah benar (hipotesis induksi)

Perlihatkan bahwa p(n+1) juga benar, yaitu :

          1+3+5+...+(2n-1)+(2n+1) = (n+1)²

Hal ini dapat ditunjukkan sebagai berikut :

          1+3+5+...+(2n-1)+(2n+1) = [1+3+5+...+(2n-1)]+(2n+1)

                                                 = n² + (2n+1)

                                                 = n² + 2n+1

                                                 = (n+1)²

Langkah (i) dan (ii) dibuktikan benar, maka  untuk jumlah n buah bilangan ganjil positif pertama adalah n².

2.   Prinsip Induksi yang Dirampatkan (Generalized)

Misalkan p(n) adalah pernyataan perihal bilangan bulat n ≥ n₀. Untuk membuktikannya perlu menunjukkan bahwa :

1)   p(n₀) benar

2)   Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ≥ n₀

Sehingga p(n) benar untuk semua bilangan n ≥ n_0.

Contoh :

a.    Untuk semua bilangan bulat tidak negatif n, buktikan dengan induksi matematika bahwa 2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1.

Misalkan p(n) adalah proposisi bahwa untuk semua bilangan bulat tidak negatig n, 2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1.

ü  Basis Induksi

p(0) benar à untuk n = 0 (bilangan bulat tidak negatif pertama) diperoleh dari :

                           2⁰ = 1 = 2⁰⁺¹ -1

                               = 2¹ -1

                               = 2 – 1

                               = 1

ü  Langkah Induksi

Misalkan p(n) benar, yaitu proposisi :

          2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1

Diasumsikan benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar, yaitu :

           2⁰+ 2¹+ 2²+…+ 2ⁿ+ 2ⁿ⁺¹ = 2^(n+1)+1 -1

Hal ini dapat ditunjukkan sebagai berikut :

           2⁰+ 2¹+ 2²+…+ 2ⁿ+ 2ⁿ⁺¹ = (2⁰+ 2¹+ 2²+…+ 2ⁿ) + 2⁽ⁿ⁺¹⁾

                        = 2^(n+1)+1 -1 + 2ⁿ⁺¹  (dari hipotesis induksi)

                   = (2ⁿ⁺¹ + 2ⁿ⁺¹) – 1

                   = (2 . 2ⁿ⁺¹) – 1

                   = 2ⁿ⁺² – 1

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

Langkah (i) dan (ii) dibuktikan benar, maka untuk semua bilangan bulat tidak negatif n, terbukti bahwa 2⁰+ 2¹+ 2²+…+ 2ⁿ= 2ⁿ⁺¹ -1.

b.   Buktikan dengan induksi matematika bahwa 3ⁿ < n! untuk n bilangan bulat positif yang lebih besar dari 6

Misalkan p(n) adalah proposisi bahwa 3ⁿ < n! untuk n bilangan bulat positif yang lebih besar dari 6

ü  Basis Induksi

   p(7) benar --> 3⁷ < 7! « 2187 < 5040

ü  Langkah Induksi

Misalkan bahwa p(n) benar, yaitu asumsikan bahwa 3ⁿ < n! adalah benar. Perlihatkan juga bahwa p(n+1) juga benar, yaitu 3ⁿ⁺¹ < (n+1)!

Hal ini dapat ditunjukkan sbb :

           3ⁿ⁺¹ < (n+1)!

           3 . 3ⁿ < (n+1) . n!

 3ⁿ . 3 / (n+1) < n!

Menurut hipotesis induksi, 3ⁿ < n!, sedangkan untuk n > 6, nilai 3/(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan. Efek nettonya, 3ⁿ . 3/(n+1) < n! jelas benar

Langkah (i) dan (ii) dibuktikan benar, maka terbukti bahwa 3ⁿ < n! untuk n bilangan bulat positif lebih besar dari 6