PERMUTASI DAN KOMBINASI

PERMUTASI DAN KOMBINASI

1.1 PermutasiPermutasi adalah suatu susunan yang berbeda atau urutan yang berbeda yang dibentuk oleh sebagian atau keseluruhan objek atau unsur yang diambil dari sekelompok objek atau unsur yang tersedia.

• Misalkan H adalah himpunan dengan n objek

• Misalkan k ≤ n, permutasi k objek dari himpunan H adalah susunan objek-objek berbeda dalam urutan tertentu yang terdiri dari k objek anggota himpunan H
• Lambang permutasi adalah huruf P (_nP_k)
• Faktorial n! = n(n-1)(n-2)…3.2.1

Banyak permutasi dari k unsur yang diambil dari n unsur yang tersedia sama dengan
Susunan pada permutasi memperhatikan urutan artinya AB dengan BA dihitung berbeda.
Contoh :
1. Tentukan nilai ₈P₄ 
Jawaban :           

2. Tentukan banyaknya susunan atau permutasi 3 huruf yang diambil dari 5 huruf A , B , C , D, E.  
 Jawaban : 

 
3. Dalam suatu perlombaan balap sepeda yang terdiri dari 7 orang akan diambil 3 orang sebagai juara yaitu : juara I, juara II dan juara III. Tentukan kemungkinan susunan juara yang terjadi !
Jawaban :

1.2 Permutasi Siklis atau Permutasi MelingkarDefinisinya : Permutasi siklis dari n objek adalah penyusunan objek objek yang mengelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!Contoh :1. Misalkan ada 10 orang yang duduk pada satu barisan kursi yang terdiri dari 10 kursi.

• Menurut rumus permutasi, ada sebanyak P(10,10) = 10! Cara pengaturan tempat duduk bagi 10 orang tersebut.

Sekarang, misalkan mereka disuruh duduk mengelilingi meja melingkar. Berapa banyak cara pengaturan tempat duduk bagi mereka tersebut? Satu orang dapat duduk pada tempat duduk mana saja. Sembilan orang lainnya dapat duduk dalam 9.8.7.6.5.4.3.2.1 = 9! Cara. Meskipun orang pertama dapat memilih tempat duduk mana saja, namun susunan tempat duduk yang dihasilkan oleh 9 orang lainnya tetap sama. Inilah yang dinamakan Permutasi Siklis atau Melingkar.

Pembuktian permutasi melingkar cukup sederhana : Objek pertama dapat ditempatkan dimana saja pada lingkaran dengan 1 cara. Sisa n-1 objek lainnya dapat diatur serah jarum jam (misalnya) dengan P(n-1,n-1) = (n-1)! Cara.

2.1 KombinasiKombinasi adalah susunan dari sekelompok objek tanpa memperhatikan susunannya atau urutannya. Kombinasi dapat disebut pengelompokan sejumlah unsur. Di dalam kombinasi AB = BA , ABC = ACB = CBABanyaknya kombinasi dari r objek yang diambil dari n objek yang tersedia dinotasikan dengan _nC_r atau C ( n , r ) atau C n,r atau

Contoh :
1. Berapakah Kombinasi 3 huruf dari A , B , C dan D
Jawaban :

2. Timnas karate kelas 60 kg akan memilih 3 orang dari 10 orang yang memenuhi syarat. Banyak cara memilih ketiga pemain tersebut ialah
Jawaban :

3. Berapa kemungkinan yang terjadi apabila dari 10 orang anak akan diambil sebagai pemain futsal ?
Jawaban :
Diketahui, pemain futsal = 5, jadi r =5 dan n=10

PERBEDAAN KOMBINASI DAN PERMUTASI
Salah satu perbedaan antara Permutasi dan Kombinasi adalah jika Permutasi maka perbedaan urutan menjadikan perbedaan makna, sementara di Kombinasi perbedaan urutan tidak akan menjadikan perbedaan makna. Contoh: {a,b,c} pengambilan 2 unsur dari 3 unsur jika menggunakan permutasi maka akan diperoleh hasil ab, ba, ac, ca, bc, cb. Tetapi jika menggunakan kombinasi hasil yang diperoleh adalah ab, ca, bc. 

INDUKSI MATEMATIKA

Assalamualaikum Warahmatullahi Wabarakatuh

INDUKSI MATEMATIKA

1.1 Pengertian Induksi Matematika

Induksi matematik adalah merupakan teknik pembuktian yang baku di dalam Matematika. Induksi matematik digunakan untuk membuktikan pernyataan yang khusus menyangkut bilangan bulat positif. Pembuktian dengan Induksi matematik dapat diilustrasikan dengan fenomena yang terkenal dengan Efek Domino. Sejumlah batu domino diletakan berdiri dengan jarak ruang yang sama satu dengan yang lain. Untuk merebahkan domino kita hanya cukup mendorong domino 1 ke kanan. Jika Domino 1 didorong kekanan, ia akan memdorong domino ke 2, domino 2 mendorong domino 3, dst sampai semua domino rebah ke kanan. A. 

1.2 Prinsip Induksi Sederhana 

Misal p(n) adalah pernyataan yang bergantung pada n bilangan bulat positif. Kita ingin membuktikan bahwa p(n) benar utnuk semua bilangan bulat positif. Langkah induksi: 

1.     Basis Induksi: tunjukan p(1) benar 

2.     Hipotesa induksi: Misal p(n) benar untuk semua bilangan positif n ≥ 1. 

3.     Buktikan bahwa p(n+1) benar. 

Contoh: 

1. Tunjukan bahwa 1 + 2 + 3 + . . . + n = 2 n(n + )1 untuk n≥1. 

Jawab: 

• Basis induksi 

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

 = 2/2 

 = 1 (benar) 

• Hipotesa induksi 

Andaikan untuk n≥1 1 + 2 + 3 + . . . + n =  n(n + 1) /2 benar 

• Akan dibuktikan untuk (n+1), 

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

bukti: 

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

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

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

Terbukti. 

∴1 + 2 + 3 + . . . + n = n(n +1)/2 untuk n≥1.

1.3 Prinsip Induksi Yang Dirapatkan (Generalized) 

Prinsip Induksi sederhana digunakan untuk membuktikan pernyataan p(n) dimana n dimulai dari 1. Prinsip Induksi yang dirapatkan digunakan untuk membuktikan pernyataan p(n) dimana n tidak harus dimulai dari 1, tetapi berlaku untuk semua bilangan bulat positif (nonnegative). 

Misal p(n) adalah pernyataan. Kita akan buktikan p(n) benar untuk semua bilangan bulat n ≥ n0. Langkah Induksi: 

1. Basis Induksi: p(n0) benar 
2. Hipotesa Induksi : Andaikan p(n) benar untuk n ≥ n0. 
3. Akan dibuktikan bahwa p(n+1) benar. 

Contoh: 

1. Tunjukan bahwa utnuk semua bilangan bulat non negative 2^0 + 2^1 + 2^2 + . . . + 2^n = 2^n+1 – 1 

Jawab: 

• Basis Induksi 

Untuk n = 0 ⇒ 2^0 = 2^0+1 – 1

1 = 2 – 1 

 1 = 1 (benar) 

• Hipotesa Induksi 

Andaikan untuk n≥0, 2^0 + 2^1 + 2^2 + . . . + 2^n = 2^n+1 – 1 adalah benar. 

• Akan dibuktikan untuk p(n+1) : 2^0 + 2^1 + 2^2 + . . . + 2^n + 2^n+1 = 2^n+2 – 1 

Bukti: 

2^0 + 2^1 + 2^2 + . . . + 2^n + 2^n+1 = (2^n+1 – 1) + 2^n+1 

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

 = 2. 2^n+1 – 1 

 = 2^n+2 – 1 

Terbukti

∴2 0 + 21 + 22 + . . . + 2n = 2n+1 – 1, untuk semua bilangan bulat nonnegatif. 

1.4 Prinsip Induksi Kuat 

Misal p(n) adalah suatu pernyataan yang menyangkut bilangan bulat. Kita akan buktikan bahwa p(n) adalah benar utnuk semua bilangan bulat n≥n0. Langkah induksi: 

1.     Basis Induksi: p(n0) benar. 

2.     Hipotesa Induksi : Andaikan utnuk semua bilangn bulat n≥n0, p(n0), p(n0 + 1), . . . , p(n) benar. 

3.     Akan dibuktikan p(n+1) benar. 

Contoh: 

Tunjukan bahwa bilangan bulat positif adalah bilangan prima jika hanya jika hanya habis dibagi 1 dan dirinya sendiri. 

Jawab: 

Kita akan buktikan bahwa utnuk setiap bilangan bulat n≥2, dapat dinyatakan sebagai hasil kali satu atau lebih bilangan prima. 

• Basis Induksi Untuk n = 2 ⇒ 2 = 1.2 ( 2 dapat dinyatakan sebagai perkalian satu bilangan prima) benar. 

• Hipotesa induksi Misalkan 2,3,4, . . ., n dapat dinyatakan sebagai hasil kali satu atau lebih bilangan prima. 

• Akan dibuktikan bahwa (n+1) dapat dinyatakan sebagai hasil kali satu atau lebih bilangan prima. 

Bukti: 

Jika (n+1) adalah bilangan prima , maka (n+1) dapat dinyatakan sebagai hasil kali satu bilangan prima yaitu (n+1) = 1.(n+1) 

Jika (n+1) bukan bilangan prima, maka terdapat bilangan positif a sedemikian sehingga 2< a < (n+1) yang membagi habis (n+1). Dengan kata lain: 

(n +1)/a = b atau (n+1) = ab

Dari hipotesa, karena 2< a,b<n maka a dan b dapat dinyatakan sebagai hasil kali

satu atau lebih bilangan prima. Jadi, ab juga dapat dinyatakan sebagai hasil kali satu

atau lebih bilangan prima, sehingga (n+1) dapat dinyatakan sebagai hasil kali satu

atau lebih bilangan prima. (terbukti). 

Waalaikumsalam Warahmatullahi Wabarakatuh

Semoga bermanfaat guys:)