Tugas Matdis Teorema Permutasi Dan Kombinasi Beserta Pembuktian.docx

NAMA

: AISYA FADHILLA

NIM

: 17030062

PRODI

: MATEMATIKA (NK)

TEOREMA PERMUTASI DAN KOMBINASI BESERTA PEMBUKTIANNYA Permutasi Permutasi adalah penyusunan kembali suatu kumpulan objek dalam urutan yang berbeda dari urutan yang semula. 

Urutan diperhatikan



Perulangan tidak diperbolehkan

Teorema permutasi P(n,r) = Banyaknya permutasi -r dari suatu himpunan dengan n elemen.

Teorema 1.

Jika n  Z+ dan r  Z untuk 1≤ r ≤ n, maka P(n,r) = n×(n-1)×(n-2)×…× ( n-r+1)

Bukti: Asumsikan bahwa permutasi -r dari unsur n yang berbeda merupakn aktifitas yang terdiridari -r langkah yang berurutan. Langkah pertama adalah memilih unsur pertama yang bisa dilakukan dengan n cara. Langkah kedua adalah memilih unsur kedua yang bisa dilakukan dengan (n-1) cara karena karena unsur pertama sudah terpilih. Lanjutkan langkah tersebut sampai pada langkah ke -r yang bisa dilakukan dengan ( n-r+1) cara.

Kotak ke-

1

2

3

4

5

Tahap pertama adalah mengisi kotak ke-1,tahap kedua adalah mengisi kotak ke-2, dan seterusnya sampai tahap ke-r Tahap

Pengisian kotak ke-

Banyak cara

1

1

n

2

2

n-1

…

…

...

r-1

r-1

n(r-2)= n-r+2

r

r

n-(r-1)=n-r+1

Berdasarkan Prinsip Perkalian,diperoleh P(n,r) = n×(n-1)×(n-2)×…× ( n-r+1)

Akibat 1

Jika n, r  Z untuk 0 ≤ r ≤ n maka P(n,r) =

n! (n  r )!

Bukti: Jika n, r  Z untuk 1 ≤ r ≤ n, berdasarkan teorema 1 diperoleh: P(n,r)

= n×(n-1)×(n-2)×…× ( n-(r-1))

=

n! (n  r )!

untuk r=n, maka persamaan menjadi karena

P(n,r) =

n! n!   1 , untuk n  Z+ semua bisa memperoleh rumus bahwa (n  0)! n! n! juga terpenuhi untuk r=0 (n  r )!

Kombinasi

 Kombinasi r elemen dari n elemen adalah:  Jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen  Kombinasi merupakan bentuk khusus dari permutasi  Perbedaan permutasi dengan kombinasi:  Permutasi

: urutan kemunculan diperhitungkan

 Kombinasi : urutankemunculan diabaikan  Jumlah pemilihan yang tidak terurut dari r elemen yang diambil dari n elemen disebut dengan kombinasi -r: n! n C (n, r )  C    Crn  (n  r )! r

 C(n,r) dibaca “n diambil r” atau r objek diambil dari n buah objek

Teorema 2.

Jika n  Z+ dan r  Z untuk 0≤ r ≤ n, maka C (n, r ) 

n! (n  r )! r!

Bukti: 

Permutasi -r dari suatu himpunan dengan n elemen dapat diperoleh dengan cara membentuk kombinasi -r dan kemdian mengurutkan elemen pada setiap kombinasi -r tersebut (dapat dilakukan dalam P(r,r) cara).



Jadi, P(n,r)= C(n,r). P(r,r)



Ini berarti bahwa n! P(n, r ) (n  r )! n! C (n, r )    P(r , r r! (n  r )! r!

Akibat 2: Jika n,r  Z+ untuk r ≤ n, maka C (n, r )  C (n, n  r ) Bukti: Berdasarkan teorema 2: C (n, r ) 

n! (n  r )! r!

Dan

C (n, n  r ) 

n! (n  (n  r )!(n  r )!

Jadi, C (n, r )  C (n, n  r )

Hubungan Permutasi dan Kombinasi

Pemisalan: Pada waktu kenaikan kelas dari kelas X ke kelas XI, siswa yang naik akan memasuki jurusan masing-masing. Ada yang IPA, IPS, maupun Bahasa. Oleh karena itu, diadakan perpisahan kelas dengan jalan berjabat tangan. Kita contohkan ada 3 siswa saling berjabat tangan misalkan Adi, Budi, dan Cory. Ini dapat ditulis Adi-Budi,

Adi-Cory, Budi-Adi, Budi-Cory, Cory-Adi, Cory-Budi. Dalam himpunan Adi berjabat tangan dengan Budi ditulis {Adi, Budi}. Budi berjabat tangan dengan Adi ditulis {Budi, Adi}. Antara {Adi, Budi} dan {Budi, Adi} menyatakan himpunan yang sama, berarti keduanya merupakan kombinasi yang sama. Di lain pihak Adi – Budi, Budi – Adi menunjukkan urutan yang berbeda yang berarti merupakan permutasi yang berbeda. Dari contoh dapat diambil kesimpulan: Permutasi

= Adi – Budi, Adi – Cory, Budi – Adi, Budi – Cory, Cory – Adi, Cory – Budi = 6 karena urutan diperhatikan

Kombinasi

= Adi – Budi, Adi – Cory, Budi – Cory = 3 karena urutan tidak diperhatikan

Sehingga, secara umum dapat disimpulkan bahwa : Banyaknya kombinasi dari n unsur yang berbeda dengan setiap pengambilan dengan r unsur ditulis dinotasikan dengan nCr atau C ( n , r ) atau C n,r adalah :

nCr 

n Pr n!  r! r!(n  r )!

Sehingga dapat disimpulkan juga bahwa kombinasi merupakan subset dari permutasi.