PERMUTASI, KOMBINASI DAN PIGEONHOLE

PERMUTASI, KOMBINASI

1.  Banyaknya bilangan yang terdiri atas 2 angka yang berbeda yang dapat disusun dari angka-angka 3, 5, dan 7?

a.      2

b.      3

c.       4

d.      5

e.      6

Jawab: e

Banyaknya bilangan yang terdiri atas 2 angka berbeda dan disusun dari angka-angka 3, 5, dan 7 adalah
sama dengan permutasi yang terdiri atas dua unsur yang dipilih dari 3 unsur, P (3, 2)

P (3, 2) = 3!/(3-2)!

             = 3!/1!

             = 3 x 2 x 1!/1!

             = 2 x 3

             = 6

2.      Dari 3 siswa, yaitu Budi, Rendi, dan Rema akan dibentuk pasangan ganda bulu tangkis. Berapa pasangan ganda yang dapat dibentuk dari ketiga siswa tersebut?

a.       1

b.      2

c.       7

d.      3

e.      10

Jawab: d

Banyaknya pasangan ganda bulu tangkis yang dapat dibentuk adalah C(3, 2)

C (3, 2) = 3!/(3-2)! 2!

                        = 3!/1! 2!

                         = 3 x 2!/1! 2!

                         = 3/1

                         = 3

3.        Menjelang Pergantian kepengurusan BEM STMIK Tasikmalaya akan dibentuk panitia inti sebanyak 2 orang (terdiri dari ketua dan wakil ketua), calon panitia tersebut ada 6 orang yaitu: a, b, c, d, e, dan f. Ada berapa pasang calon yang dapat duduk sebagai panitia inti tersebut?

a.      30

b.      34

c.       23

d.      12

e.      65

Jawab: a

6P2 = 6!/(6-2)!

= (6.5.4.3.2.1)/(4.3.2.1)

= 720/24  = 30 cara

4.      Ada berapa cara 5 gelas warna yang mengitari meja kecil, dapat menempati kelima tempat dengan urutan yang berlainan?

a.       10

b.      15

c.       24

d.      26

e.      43

Jawab: c

Banyaknya cara duduk ada (5 – 1) ! = 4 ! ® 4. 3 . 2 . 1 = 24 cara.

5.      Misal sebuah kelompok memiliki 20 orang anggota, kemudian dipilih 5 orang sebagai panitia, dimana panitia merupakan kelompok yang tidak terurut (artinya setiap anggota di dalam panitia kedudukannya sama). Sehingga banyaknya cara memilih anggota panitia yang terdiri dari 5 anggota panitia yang terdiri dari 5 orang anggota adalah ...

a.      15504 cara

b.      12000 cara

c.       14325 cara

d.      20901 cara

e.      23220 cara

Jawab : a

6.      Dalam suatu pertemuan terdapat 10 orang yang belum saling kenal. Agar mereka saling kenal maka mereka saling berjabat tangan. Berapa banyaknya jabat tangan yang terjadi ?

a.       43 jabat tangan

b.      45 jabat tangan

c.       47 jabat tangan

d.      87 jabat tangan

e.      54 jabat tangan

Jawab : b

10C2 = (10!)/(2!(10-2)!) = 45 jabat tangan

PIGEONHOLE

1.      Sebut dan jelaskan aplikasi dan pigeon hole ?

Jawab :

Prinsip pigeonhole merupakan salah satu teknik pembuktian yang sederhana dan efektif. Prinsip ini merupakan salah satu alat kombinatorial yang berguna dalam menghitung objek dengan properti tertentu.

Prinsip pigeonhole mempunyai banyak aplikasi, diantaranya dalam sains komputer,permasalahan relasi,permasalahannumerikal, permasalahan geometri,trik kartu kombinatorik, dan teori Ramsey

-          sains komputer : Salah satu aplikasi prinsip pigeonhole pada sains komputer adalah pada hash collision. Sebagai informasi,algoritma hash mengubah suatu data apapun ke dalam bentuk data lain

-          permasalahan relasi : Aplikasi prinsip pigeonhole dalam relasi cukup berguna dalam mengaproksimasi kebutuhan minimal yang harus disiapkan dalam hal tertentu.

-          Permasalahan numerical : Prinsip pigeonhole mampu menyelesaikan beberapa permasalahan numerikal. Contoh pertama adalah permasalahan divisibilitas. Dengan prinsip pigeonhole, kita mampu membuktikan bahwa pasti ada dua angka dalam n angka yang selisihnya habis dibagi angka n-1 dengan n bilangan bulat positif ≥ 2.

-          Permasalahan geometri : Prinsip pigeonhole dapat digunakan dalam pembuktian masalah masalah geometri.

-          Teori ramsey : Secara umum, teori Ramsey membahas distribusi subset elemen dalam suatu set elemen. Teori Ramsey merupakan extremal combinatorics yang memberikan jumlah objek jika kumpulan objek tersebut harus memenuhi kondisi tertentu.

2.      Adakah keterkaitan antara permutasi ,kombinasi dan pigeon hole ? jelaskan ?

Jawab :

hubungannya dengan pigeon hole adalah sebagai suatu alat kombinatorial ,permutasi digunakan sebagai jumlah pengaturan objek dengan memperhatikan urutan dan memiliki bentuk khusus yang di kenal dengan kombinasi fungsinya ,berbeda dengan permutasi,jika pada permutasi memperhatikan urutan namun pada kombinasi kita dapat memilih secara acak tanpa memperhatikan urutan.