Seorang siswa harus menjawab 8 soal dari 10 soal yang tersedia jika 3 soal pertama harus dijawab

KOMBINATORIK

2.1. PERMUTASI DAN KOMBINASI Sebuah permutasi dari sebuah himpunan obyek-obyek berbeda adalah

penyusunan berurutan dari obyek-obyek tersebut.

Contoh 2.1.

Misalkan S = {1, 2, 3}. Susunan 3 1 2 adalah sebuah permutasi dari S. Susunan

3 2 adalah sebuah permutasi-2 (2-permutation) dari S

Banyak permutasi-r dari himpunan dengan n obyek berbeda dinyatakan

sebagai P(n,r) dimana

P(n,r) = n . (n - 1) . (n - 2) . (n - 3) . ... . (n r + 1).

Jika r = n , maka

P(n,n) = n . (n - 1) . (n - 2) . (n - 3) . ... . (n n + 1).

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

= n !

atau ditulis Pn = n !

Contoh 2.2.

P(8,3) = 8. 7. 6 = 336

= 1.2.3.4.5

1.2.3.4.5.6.7.8 =

! )38(! 8

Rumus umum : n . (n-1) . (n-2) = 1 2. . ... 4)-3).(n-(n

1 2. . ... 4)-3).(n-(n 2).-1).(n-.(n n

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

! n

Sebuah kombinasi-r elemen-elemen dari sebuah himpunan adalah pemilihan tak

berurutan (tanpa memperhatikan urutan) r elemen dari himpunan tersebut.

Contoh 2.3.

Jika S = {1, 2, 3, 4}, susunan { 1, 3, 4 } adalah sebuah kombinasi-3 dari S.

Banyaknya kombinasi-r (r-combinations) dari sebuah himpunan dengan n obyek

berbeda dinyatakan sebagai C(n,r) atau rnC atau .

rn

Rumus umum : !)(!

! rn r

nrnC =

Jika r = n, maka 1 nn n

nnnC ==

!)(!!

Contoh 2.4.

Misalkan S = {1, 2, 3, 4}.

Kombinasi-4 dari S adalah { 1, 2, 3, 4 } ; . 1C =44

Kombinasi-3 dari S adalah { 1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4} ; . 4C =34

Tentukan ....24

.=C ....14

.=C

Soal Latihan 2.1.

1. Tunjukkan bahwa P(n,n-1) = P(n,n).

2. Nomor telephon internal dalam sebuah kampus terdiri dari lima angka dimana

angka pertama tidak sama dengan nol. Banyaknya nomor telephon berbeda yang

dapat disusun di kampus tersebut adalah ......... .

3. Pada sebuah lingkungan RT, penduduknya berencana menyelenggarakan acara

peringatan kemerdekaan Indonesia. Demi lancarnya kelangsungan acara tersebut,

mereka bersepakat untuk menyusun sebuah kepanitiaan yang beranggotakan 12

orang. Jika dalam lingkungan tersebut terdapat 16 pasangan suami istri, berapa

pilihan yang mereka miliki untuk membentuk kepanitiaan yang beranggotakan 4

wanita dan 8 pria ?

Soal Latihan 2.2.

1. Sebuah himpunan yang tidak kosong dan mengandung 26 anggota memiliki

himpunan bagian yang mengandung 6 anggota sebanyak ............ .

2. Tunjukkan bahwa C(n,n-r) = C(n,r) .

Soal Latihan 2.3.

1. Seorang mahasiswa harus menjawab 8 dari 10 soal ujian Matematika Diskrit.

a. Berapa banyak pilihan yang ia miliki ?

b. Berapa banyak pilihan yang ia miliki jika ia harus menjawab 3 soal pertama.

2. Jika P (n,k) menyatakan permutasi k dari n obyek dan C (n,k) menyatakan

kombinasi k dari n obyek , maka pernyataan yang benar adalah :

a. C (n ,k ) P (n ,k ) = C (n ,k ).

b. C (n ,k ) = P (n ,k ) . P (k ,k ).

c. P (n ,k ) = C (n ,k ) . P (k ,k ).

d. P (n , n k ) = C (n ,n k ) P (k ,k ).

2.2. KOMBINASI PADA HIMPUNAN DENGAN PENGULANGAN Sebuah himpunan disebut himpunan ganda (himpunan dengan pengulangan)

jika setiap anggotanya berulang.

Contoh 2.5.

1). A = { 3.a, 2.b, 5.c } adalah sebuah himpunan dari 3 elemen berbeda dengan

pengulangan hingga.

2). B = { ~.3, ~.5, ~.7, ~.9 } adalah sebuah himpunan dari empat elemen

berbeda dengan pengulangan tak hingga.

3). C = { ~.p, 10.q, 3.r, ~.s } adalah sebuah himpunan dari empat elemen

berbeda dengan pengulangan.

Misalkan A sebuah himpunan ganda berpengulang tak hingga dengan k

anggota berbeda. Banyaknya kombinasi-r pada A dinyatakan sebagai :

1) !r ! (k1) !r(k

rrk

+

=

+ 1

Contoh 2.6.

Diketahui S = { ~.a } . Banyaknya kombinasi-5 pada S adalah :

1 5 ! (0) !

5 ! 1) !5 ! (11) !5(1

5151

==+

=

+

Soal Latihan 2.4.

1. Tentukan kombinasi-5 dari B = { ~.a, ~.b} .

2. Banyaknya kombinasi-8 dari C = { ~.a, ~.b, ~.c } .

3. Banyaknya kombinasi-8 dari himpunan { ~.p, ~.q, ~.r } yang mengandung

paling sedikit 4 buah q adalah ........... .

4. Hitung banyaknya kombinasi 10 dari himpunan { ~.1, ~.2, ~.3, ~.4 } yang

a. mengandung paling sedikit 4 buah 3.

b. mengandung paling sedikit 5 buah 2.

c. mengandung paling sedikit 4 buah 3 dan 5 buah 2.

d. tidak mengandung 2 dan 3.

Taken From : library.gunadarma.ac.id/files/disk1/9/jbptgunadarma-gdl-course-2005-dradlcrisp-414-lecture-1.doc -

2.1. PERMUTASI DAN KOMBINASI 2.2. KOMBINASI PADA HIMPUNAN DENGAN PENGULANGAN