6.3 PERMUTASI DAN KOMBINASI6.4 KOEFISIEN BINOMIAL

ERINA WIDIANI(90116007)PMA 2016

6.3 PERMUTASI DAN KOMBINASI6.4 KOEFISIEN BINOMIAL

PERMUTASI

1

Definisi 1 [Definisi Permutasi]Permutasi dari sebuah himpunan dengan objek yang berbeda adalah sebuah susunan terurut dari objek-objek tersebut.

Permutasi-r adalah susunan terurut r objek dari sebuah himpunan yang terdiri atas n objek yang berbeda.

2

Misalkan S = {1, 2, 3}, susunan terurut 3, 2, 1 adalah sebuah permutasi dari S.sedangkan susunan urutan 3, 2 merupakan permutasi-2 dari S. Banyak permutasi-r dari n objek yang berbeda dinotasikan dengan P(n,r) atau nPr atau Pn,r. Untuk menemukan P(n,r) dapat menggunakan aturan perkalian.

3

Contoh 1Misalkan S = {a, b, c}, permutasi-2 dari S adalah susunan huruf a,b; a,c; b,a; b,c; c,a; dan c,b. Akibatnya ada enam permutasi-2 dari himpunan dengan tiga elemen. Dengan menggunakan aturan perkalian, ada 3 cara untuk memilih elemen pertama dan ada 2 cara untuk memilih elemen kedua pada susunan huruf tersebut. Oleh karena itu, banyak susunan huruf adalah P(3,2) = 3.2 = 6.

4

Teorema 1

Jika n adalah bilangan bulat positif dan r adalah bilangan bulat dengan 1 ≤ r ≤ n, maka permutasi-r dari himpunan dengan n elemen berbeda adalah

P(n,r) = n(n−1)(n−2) ... (n−r+1)

5

Bukti Teorema 1Asumsikan permutasi-r sebagai aktifitas dengan dengan panjang r langkah. Elemen pertama pada permutasi-r dapat dipilih dalam n cara (karena ada n elemen berbeda dalam himpunan). Selanjutnya ada n−1 cara untuk memilih elemen kedua pada permutasi-r (karena ada n−1 elemen yang tersisa setelah memilih posisi pada elemen pertama). Dengan cara yang sama, ada n−2 cara untuk memilih elemen ketiga, dan seterusnya hingga n−(r−1)=n−r+1 cara untuk memilih elemen ke-r. Akibatnya, berdasarkan aturan perkalian:

P(n,r) = n(n−1)(n−2) ... (n−r+1)

adalah permutasi-r pada himpunan dengan n elemen berbeda.

6

P(n,0) = 1 untuk n elemen bilangan bulat nonnegatif karena pada permutasi tersebut tepat ada satu cara untuk mengurutkan elemen nol yaitu satu daftar tanpa elemen didalamnya yang disebut daftar kosong.

7

Akibat 1Jika n dan r adalah bilangan bulat dengan 0 ≤ r ≤ n, maka P(n,r) = .

Bukti:Diasumsikan n dan r adalah bilangan bulat dengan 1 ≤ r ≤ n,dengan teorema 1 diperolehP(n,r) = n(n−1)(n−2) ... (n−r+1) = Karena  dengan n bilangan bulat nonnegatif, disimpulkan bahwa P(n,r) =  juga berlaku untuk r = 0.

8

Berdasarkan Teorema 1, jika  maka P(n,n) = n!

9

Contoh 2

Berapa banyak susunan untuk memilih pemenang pertama, pemenang kedua, dan pemenang ketiga dari 100 orang yang berbeda yang mengikuti sebuah kontes?Jawab:Banyak susunan untuk memilih tiga pemenang adalah banyak susunan terurut tiga elemen dari 100 elemen, yaitu banyak permutasi-3 dari himpunan dengan 100 elemen. Akibatnya, jawabannya adalah P(100,3) = 100.99.98 = 970.200. 10

KOMBINASI

11

Definisi 2 [Definisi Kombinasi]

Kombinasi dari sebuah himpunan dengan objek yang berbeda adalah sebuah susunan tidak terurut dari objek-objek tersebut.

Kombinasi-r adalah susunan tak terurut r objek dari sebuah himpunan yang terdiri atas n objek yang berbeda.

12

Misalkan S = {1,2,3}, susunan tak terurut 3,2,1 adalah sebuah kombinasi dari S sedangkan susunan  3,2 merupakan kombinasi-2 dari S (catatan: 3,2 memiliki kombinasi-2 yang sama dengan 2,3 karena urutan elemen dalam susunan tidak diperhatikan). Banyaknya kombinasi-r dari n objek yang berbeda dinotasikan dengan C(n,r)  atau nCr atau  atau .

13

Teorema 2

Banyaknya kombinasi-r dari himpunan dengan n elemen, dimana n adalah bilangan bulat nonnegatif dan r adalah bilangan bulat dengan 0 ≤ r ≤ n, adalah

C(n,r) =

14

Bukti Teorema 2

Banyak permutasi-r dari himpunan dengan n elemen (P(n,r)) dapat diperoleh dengan membentuk kombinasi-r himpunan tersebut (C(n,r)) dan selanjutnya mengurutkan elemen-elemen pada masing-masing kombinasi-r yang dalam hal ini dapat dilakukan dalam P(r,r)  cara. Akibatnya, berdasarkan aturan perkalian diperoleh:

P(n,r)=C(n,r).P(r,r)ini mengimplikasikan .

15

Contoh 3Berapa banyak susunan untuk memilih 5 kartu dari 52 kartu dan berapa banyak susunan untuk memilih 47 kartu dari 52 kartu?

Jawab: Karena dalam memilih kartu tidak memperhatikan urutan, maka banyak susunan untuk memilih 5 kartu dari 52 kartu adalah C(52,5)=sedangkan banyak susunan untuk memilih 47 kartu dari 52 kartu adalahC(52,47)=  16

Dari contoh 3, dapat dilihat bahwa C(52,5) = C(52,47).Ini adalah kasus khusus untuk kombinasi-r pada himpunan dengan n elemen yang selanjutnya akan dijabarkan pada Akibat 2.

17

Akibat 2Misalkan n dan r adalah bilangan bulat nonnegatif dengan r ≤ n, maka C(n,r) = C(n,n−r). Bukti: Dari Teorema 2,C(n,r) = danC(n,n−r) =

Oleh karena itu, dapat disimpulkan C(n,r) = C(n,n−r).

18

Contoh 4

Misalkan sebuah departemen terdiri dari 10 pria dan 15 wanita. Berapa banyak susunan berbeda dari sebuah komite yang terdiri atas enam anggota jika dalam komite tersebut harus 3 orang laki-laki dan 3 orang wanita?

Cek Jawaban  C(10,3).C(15,3)=54.600

19

KOEFISIEN BINOMIAL

20

Teorema 1 [Teorema Koefisien Binomial]Misalkan x dan y adalah variabel, dan n adalah bilangan bulat nonnegatif, maka

21

Bukti Teorema 1

Suku - suku pada hasil penjabaran  berbentuk  untuk  Untuk menghitung banyak susunansuku yang berbentuk , pertama dipilih dari   faktor. Oleh karenanya koefisien dari  adalah  yang ekuivalen dengan .

22

Contoh 1

Berapakah nilai koefisien dari  pada ekspansi ?

Jawab: Dari teorema binomial, nilai koefisien  dapat dihitung sebagai berikut.

23

Contoh 2

Berapakah nilai koefisien dari  pada ekspansi ?

Jawab: pertama perlu diingat bahwa ekspresi sama dengan . Berdasarkan teorema binomial kita dapatkan:

Akibatnya, koefisien  pada ekspansi diperoleh saat j=13 yaitu

24

Akibat 1Misalkan n adalah bilangan bulat nonnegatif, maka

Bukti: Berdasarkan teorema binomial, jika diambil x = 1 dan y = 1, maka akan kita peroleh

Persamaan di atas mengakhiri pembuktian. 25

Akibat 2

Misalkan n adalah bilangan bulat nonnegatif, maka

Bukti: Berdasarkan teorema binomial, jika diambil x = 1 dan y = -1, maka akan diperoleh

Ini mengakhiri pembuktian.

26

Akibat 3Misalkan n adalah bilangan bulat nonnegatif, maka

Bukti: Pada sisi kiri persamaan merupakan hasil dari ekspansi berdasarkan teorema binomial.Oleh karenanya, diperoleh

Ini mengakhiri pembuktian. 27

Teorema 2 [Identitas Paskal]

Misalkan n dan k adalah bilangan bulat positif dengan n ≥ k, maka

28

Bukti Teorema 2

Misalkan T adalah himpunan yang memuat n+1 elemen. Misalkan pula bahwa a adalah sebuah elemen pada himpunan T dan S = T−{a}. Karena |T| = n+1 berarti ada  subset dari himpunan T dengan k elemen. Akan tetapi, subset dari himpunan T dengan k elemen salah satunya memuat a bersama dengan k−1 elemen dari S atau kalau tidak memuat k elemen dari S dan tidak memuat a. Jika subset dari himpunan T dengan k elemen memuat a bersama dengan k−1 elemen dari S maka banyak subset yang berbentuk seperti ini ada . Jika subset dari himpunan T dengan k elemen memuat k elemen dari S dan tidak memuat a maka banyak subset yang berbentuk seperti ini ada  Akibatnya, .

29

Segitiga Paskal

Baris ke-n pada segitiga terdiri atas koefisien binomial , =0,1, 2, …, n. Segitiga tersebut dikenal dengan nama Segitiga Paskal. Identitas paskal menunjukkan bahwa saat koefisien binomial yang bertetangga pada segitiga ini dijumlahkan, koefisien pada baris selanjutnya yang berada diantara dua koefisien ini dihasilkan dari penjumlahan tersebut.

30

Teorema 3 [Identitas Vandermonde]

Misalkan m, n, dan r adalah bilangan bulat nonnegatif dengan r tidak melebihi salah satu dari m atau n, maka

31

Bukti Teorema 3

Misalkan ada m item himpunan pertama dan n item pada himpunan kedua, maka banyaknya cara memilih r elemen dari gabungan dua himpunan ini adalah . Cara lainnya untuk memilih r elemen dari gabungan himpunan adalah mengambil k elemen dari himpunan kedua kemudian r−k elemen dari himpunan kedua, dimana k adalah bilangan bulat dengan 0≤k≤r. Karena ada cara untuk memilih k elemen dari himpunan kedua dan ada cara untuk memilih r−k elemen dari himpunan pertama, maka berdasarkan aturan perkalian, banyak cara memilih r elemen dengan prosedur ini dapat dilakukan dengan cara. Oleh karenanya, jumlah total banyak cara memilih r elemen dari gabungan dua himpunan tersebut adalah .   

32

Akibat 4Jika n adalah bilangan bulat nonnegatif, maka

Bukti: Dengan menggunakan identitas Vandermonde dengan n = m = r akan didapat

Persamaan terakhir didapat dengan menggunakan identitas binomial .

33

Kuis

1. Berapa banyak susunan berbeda untuk memilih 1 orang pemenang pertama, 3 orang pemenang kedua, dan 3 orang pemenang ketiga dari 10 orang yang berbeda yang mengikuti sebuah kontes?

2. Berapa banyak susunan berbeda untuk membuat satu kelompok yang beranggotakan 5 orang dari 8 orang siswa?

3. Berapakah koefisien dari dalam ekspansi ?

34

Jawaban Kuis1. Banyak susunan berbeda untuk memilih pemenang

tersebut adalah .2. Banyak susunan berbeda untuk membuat kelompok

tersebut adalah C(8,5)=3. koefisien dari dalam ekspansi adalah

35

Terima kasih