permutasi dan kombinasi

PERMUTASI DAN KOMBINASI

1)      Permutasi

Permutasi merupakan penyusunan kembali suatu kumpulan objek dalam urutan yang berbeda dari urutan yang semula. Atau dalam kata lain, perutasi merupakan jumlah urutan berbeda dari objek objek.

Permutasi merupakan bentuk khusus aplikasi aturan perkalian. Misalkan jumlah objek adalah n , maka urutan pertama dipilih dari n objek, urutan ke dua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterus nya dan urutan terakhir dipilih dari 1 objek yang tersisa.

n(n-1)(n-2)...(2)(1)=n!

·         Rumus dari Permutasi k unsur dari n unsur:

                                 P(n,k)=

Contoh:

1.       Terdapat 4 orang mahasiswa yang di calonkan sebagai ketua dan wakil ketua. Tentukan berapa banyak cara yang dapat digunakan untuk mengisi posisi tersebut?

Penyelesaian:

n=4

k=2

maka, P(4,2)=

maka ada 12 cara yang dapat dilakukan untuk mengisi posisi tersebut.

·         Permutasi r dari n objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤ n, yang dalam hal ini pada setiap kemunkinan urutan tidak ada yang  sama.

             P(n,n)== ==n!

·         Permutasi beberapa unsur yang sama.

Setiap unsur pada permutasi tidak boleh digunakan lebih dari satu kali, kecuali jika dinyatakan secara khusus. Banyaknya permutasi dari unsur n yang memuat k unsur yang sama(k+l+...+m<=n) dapat di tentukan dengan rumus:

       P=

Contoh:

Terdapat dua boneka beruang,1 boneka panda, dan 3 boneka kucing yang sama jenis dan ukurannya. Ada berapa carakah boneka-boneka itu dapat disusun berdampingan?

Pembahasan:

                     

                        Jadi banyaknya susunan boneka-boneka tesebut adalah 60 cara.

2)      KOMBINASI

Kombinasi merupakan bentuk khusus dari permutasi. Jika pada permutasi urutan kemunculan di perhitungkan, maka pada kombinasi urutan kemunculan diabaikan. Dimana urutan acb,bca, dan acb dianggap sama dan dihitung sekali.

Kombinasi r elemen dari n elemen adalah:

Ø  Jumlah pemilihan yang tidak terurut r elemen yang daiambil dari n buah elemen disebut  dengan kombinasi-r.

          C(n,r)=C=

Ø  C(n,r ) dibaca “n diambil r”→r objek diambil dari n buah objek.

Interpretasi kombinasi

1.      Persoalan kombinasi, C(n,r), sama dengan menghitung banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen. Dua atau lebih himpunan bagian dengan elemen-elemen yang sama dianggap sebagai himpunan yang sama, meskipun urutan elemen-elemennya berbeda.

Musalkan A={1,2,3}

Jumlah himpunan bagian dengan 2 elemen yang dapat dibentuk dari himpunan a ada 3 buah, yaitu:

{1,2}={2,1}

{1,3}={3,1}                    3 buah

{3,2}={2,3}

Atau  ==

2.      Persoalan kombinasi , C(n,r), dapat di pandang sebagai cara memilih r buah elemen dari n buah elemen yang ada, tetapi urutan elemen di dalam susunan hasil pemilihan tidak penting.

Contoh:

Ada berapa cara dapat memilih 3 dari 4 elemen  himpunan A = {a, b, c, d} ?

Penyelesaian:

 Ini adalah persoalan kombinasi karena urutan kemunculan  ketiga elemen tersebut tidak  

 penting

Himpunan bagian A dengan 3 elemen	Permutasi setiap himpunan bagian
{a, b, c}	abc,acb,bca,bac,cab,cba
{a, b, d}	abd,adb,bda,bad,dab,dba
{a, c, d}	acd,adc,cda,cad,dac,dca
{b, c, d}	bcd,bdc,cdb,cbd,dbc,dcb

 
Untuk setiap 3 elemen ada 3! = 6 urutan yang berbeda  (permutasi  P = n ! ). 

Jadi jumlah cara memilih 3 dari 4 elemen himpunan adalah C(4,3)=

yaitu himpunan {a, b, c}, {a, b, d}, {a, c, d}, dan {b, c, d}.

Soal:

1.    Berapa banyak string yang dapat dibentuk dari huruf WEAKNESS jika urutan diperhatikan?

Penyelesaian:

WEAKNESS

W=1

E=2

A=1

K=1

N=1

S=2

n=8 buah

Jumlah string= P(8;1,1,2,1,1,2)=8!/1!1!2!1!2!

                                                  = 8!/2!2!

                                                  = 8!/4!

                                                  =8*7*6*5*4!/4!

                                                  = 10.080 cara

2.      Ada 5 orang mahasiswa jurusan Teknik Informatika dan 7 orang mahasiswa jurusan Teknik Elektro. Berapa banyak cara membentuk panitia yang terrdiri dari 4 orang jika:

a.       Tidak ada batasan jurusan

b.      Semua anggota panitia harus dari jurusan Teknik Informatika

c.       Semua anggota panitia harus dari jurusan Teknik Elektro

d.      Semua anggota panitia harus dari jurusan yang sama

e.       2 orang mahawiswa per jurusan harus mewakili

Penyelesaian:

a.       C(12,4) = (12!/4!*8!)

     = 495 cara

b.      C(5,4)*C(7,0)  = (5!/4!*1!) * (7!/0!*7!)

                         = 5 cara

c.       C(7,4)*C(5,0) = (7!/4!*3!) * C(5!/0!*5!)

                         = 35 cara

d.      C(5,4)*C(7,0) + C(7,4)*C(5,0)   = 5 + 35

                                                    = 40 cara

e.       C(5,2)*C(7,2)  = (5!/2!*3!) * (7!/2!*5!)

                          = 10 * 21

                          = 210 cara

Induksi Matematika

INDUKSI MATEMATIKA

1.    PENGERTIAN INDUKSI MATEMATIKA

Induksi matematika atau disebut juga induksi lengkap sering dipergunakan untuk pernyataan-pernyataan yang menyangkut bilangan-bilangan asli. Atau dalam kata lain induksi matematika merupakan metode pembuktian untuk proposisi perihal bilangan bulat dan merupakan teknik pembuktian yang baku dalam matematika.
Pembuktian cara induksi matematika ingin membuktikan bahwa teori atau sifat itu benar untuk semua bilangan asli atau semua bilangan dalam himpunan bagiannya. Caranya ialah dengan menunjukkan bahwa sifat itu benar untuk n = 1 (atau S(1) adalah benar), kemudian ditunjukkan bahwa bila sifat itu benar untuk n = k (bila S(k) benar) menyebabkan sifat itu benar untuk n = k + 1 (atau S(k + 1) benar).

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

Contohnya:

1)      Apakah pernyataan tersebut benar ?
kita coba memasukkan n = 2 apakah hasilnya adalah 2 ?

2(2+1) / 3 = 2 ternyata benar

2)      Kita coba masukkan  n = 5

5(5+1) / 2 = 15 ternyata benar, 1+2+3+4+5 = 15

Dari contoh soal diatas terbukti bahwa kita tidak harus menggunakan cara yang terkesan panjang untuk membuktikan nilai dari suatu soal yang ingin ketahui.

2.     PROPOSISI PERIHAL BILANGAN BULAT

Proposisi merupakan istilah yang digunakan untuk kalimat pernyataan yang memiliki arti penuh dan utuh, atau dalam kata lain proposisi merupakan pernyataan mengenai hal-hal yang bernilai benar atau salah.

Proposisi yang menyangkut perihal bilangan bulat cukup banyak ditemui dalam matematiks diskret. Proposisi tersebut mengaitkan suatu masalah yang dihubungkan dengan bilangan bulat.

Dalam matematika banyak fenomena yang manyatakan bahawa p(n) benanr untuk semua bilangan bulat positif n. Dimana dalam hal ini p(n) disebut juga fungsi proposisi.

Contoh:

Misalkan p(n) adalah proposisi yang menyatakan : “jumlah bilangan bulat positif dari 1 sampai nadalah n(n+1)/2”. Buktikan bahwa p(n) benar!

Jawab:

Misalnya untuk n=5, p(5) adalah: : jumlah bilangan bulat positif dari 1 sampai 5 adalah 5(5+1)/2, terlihat bahwa:

1+2+3+4+5=15=5(6)/2.

Contoh 2 : Jika ingin menemukan rumus jumlah dari n buah bilangan ganjil positif yang pertama. Misalnya untuk n = 1, 2, 3, 4, 5, perhatikan jumlah n bilangan ganjil positif pertama

 n = 1 ® 1 = 1

 n = 2 ® 1 + 3 = 4

 n = 3 ® 1 + 3 + 5 = 9

 n = 4 ® 1 + 3 + 5 + 7 = 16

 n = 5 ® 1 + 3 + 5 + 7 + 9 = 25

Dari nilai-nilai penjumlahan, bahwa jumlah n buah bilangan ganjil yang pertama adalah n2

3.   Prinsip Induksi Sederhana

Misalkan p(n) adalah proposisi bilangan bulat positif dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat positif n. Maka langkah-langkahnya adalah sebagai berikut :

a.       p(n) benar

b.       Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ³ 1

Sehingga p(n) benar untuk semua bilangan bulat positif n.

  Basis Induksi dan Langkah Induksi

 Langkah 1 dinamakan Basis Induksi, sedangkan langkah 2 dinamakan Langkah Induksi. • Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar. Asumsi tersebut dinamakan hipotesis induksi.

Bila kedua langkah tsb benar, maka sudah dibuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.

• Basis induksi digunakan untuk memperlihatkan bahwa pernyataan tersebut benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil. Langkah induksi harus memperlihatkan bahwa p(n) ® p(n+1) benar untuk semua bilangan bulat positif.

·  Contoh  : Tunjukkan bahwa untuk n ³ 1, 1+2+3+…+n = n(n+1)/2 melalui induksi matematika

Penyelesaian:

 (i) Basis induksi : p(1) benar, karena untuk n = 1 kita peroleh

 1 = 1(1+1)/2

    = 1(2)/2

    =2/2

    = 1

(ii) Langkah induksi : misal p(n) benar, yaitu mengasumsikan bahwa:

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

     Adalah benar, kita juga harus memperlihatkan bahwa

      p(n+1) juga benar, 1+2+3+…+n+(n+1) = (n+1) [(n+1) +1] /2.

Untuk membuktikan ini, tunjukkan bahwa:

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

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

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

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

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

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

Karena langkah (i) dan (ii) telah dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ³ 1, 1+2+3+…+n = n(n+1)/2:  sama.

4.   Prinsip Induksi yang Dirampatkan

è Prinsip induksi sederhana dapat dirampatkan (generalized).

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

a.       p(n₀) benar

b.       Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ³ n₀

          sehingga p(n) benar untuk semua bilangan bulat n ³ n₀

·  Contoh  :

a)       Untuk semua bilangan bulat tidak negatif n, buktikan dengan induksi matematika bahwa 20+21+22+…+2n = 2n+1-1

           Penyelesaian:

            Misalkan p(n) adalah proposisi bahwa untuk semua bilangan bulat tidak negatif n,      

            20+21+22+…+2n = 2n+1-1.

(i)                  Basis induksi : p(0) benar, karena untuk n = 0 (bilangan bulat tidak negatif pertama), kita peroleh : 2⁰ = 1 = 2⁰⁺¹ – 1

                            = 2¹ – 1

                            =2 – 1

                            = 1

(ii)                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

Penyelesain:

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

(i)                  Basis induksi

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

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