Berapa cara yang mungkin dapat dibentuk jika dalam suatu pesta makan terdapat 7 orang yang duduk dalam meja makan bundar?

Misalkan di pasaran tersedia 4 merk TV. Masing-masing merk menyediakan 3 jenis ukuran layar. Masing-masing TV dikeluarkan dengan 2 macam kualitas suara, stereo dan mono. Jika seorang pembeli akan membeli TV baru, berapa macam pilihan yang dapat dilakukan olehnya?

Untuk menjawab pertanyaan di atas pembeli menggunakan alur pemikiran berikut ini.

Pertama, ketika memilih merk, terdapat 4 cara untuk memilih merk.

Kedua, ketika memillih ukuran layar, terdapat 3 cara untuk memilih ukuran layar.

Ketiga, ketika memilih kualitas suara, terdapat 2 cara untuk memilih kualitas suara.

A

B

C

D

B

C D A

C D A

B D A

B C

Jadi, seluruhnya terdapat 4 × 3 × 2 = 24 cara untuk memilih pasangan merk, ukuran layar, dan kualitas suara. Tanpa menyadari, pembeli itu sebenarnya telah menggunakan teknik mencacah dengan aturan perkalian.

Aturan Perkalian

Jika terdapat n buah tempat tersedia, dengan:

k1 adalah banyak cara mengisi tempat pertama,

k2 adalah banyak cara mengisi tempat kedua setelah tempat pertama terisi, ... dan seterusnya,

kn adalah banyak cara mengisi tempat ke-n setelah (n – 1) tempat-tempat sebelumnya terisi,

maka banyak cara mengisi n tempat yang tersedia itu secara keseluruhan adalah:

k1 × k2 × k3 × ... × kn

Jika kita perhatikan aturan perkalian di atas, dalam menentukan banyak cara untuk mengisi k tempat yang tersedia menggunakan operasi perkalian dalam aljabar biasa. Untuk lebih memahami aturan ini kita ikuti contoh aplikasi berikut ini.

Contoh 2.1.1

Ucok ingin bepergian dari kota P ke kota R. Dari kota P ke kota Q dapat ditempuh melalui 3 jalan, sedangkan dari kota Q ke kota R dapat ditempuh melalui 2 jalan.

Berapa banyak cara yang dapat ditempuh Ucok, jika ingin bepergian dari kota P ke kota R melalui kota Q?

Penyelesaian:

Dari kota P ke kota Q, terdapat 3 cara.

Dari kota Q ke kota R, terdapat 2 cara.

Dari kota P ke kota R melalui kota Q, terdapat 3 × 2 = 6 cara.

Jadi, banyak cara yang dapat dipilih Ucok untuk bepergian dari kota P ke kota R melalui kota Q adalah 6 cara.

W Contoh 2.1.2

Dari huruf S, O, P, A, dan N akan dibentuk susunan huruf sehingga dalam susunan tersebut tidak ada huruf yang sama. Berapa banyak cara untuk menyusun huruf-huruf itu, apabila:

a. huruf dimulai dengan huruf vokal?

b. huruf pertama dimulai dengan huruf konsonan?

Penyelesaian:

a. Huruf pertama dimulai dengan huruf vokal.

Huruf pertama dapat dipilih dengan 2 cara, yaitu huruf O dan A.

Huruf kedua dapat dipilih dengan 4 cara. Misalnya, jika huruf pertama kita pilih O, maka huruf kedua dapat kita pilih S, P, A, dan N.

Huruf ketiga dapat kita pilih dengan 3 cara.

Huruf keempat dapat kita pilih dengan 2 cara.

Huruf kelima dapat kita pilih dengan 1 cara.

Seluruhnya terdapat 2 4 3 2 1 48× × × × = cara.

Jadi, banyak cara untuk menyusun huruf S, O, P, A, dan N dengan huruf pertama dimulai huruf vokal seluruhnya ada 48 cara.

b. Huruf pertama dimulai dengan huruf konsonan.

Huruf pertama dapat dipilih dengan 3 cara, yaitu huruf S, P, dan N.

Huruf kedua dapat dipilih dengan 4 cara. Misalnya, jika huruf pertama kita pilih S, maka huruf kedua dapat kita pilih O, P, A, dan N.

Huruf ketiga dapat kita pilih dengan 3 cara.

Huruf keempat dapat kita pilih dengan 2 cara.

Huruf kelima dapat kita pilih dengan 1 cara.

Seluruhnya terdapat 2 4 3 2 1 48× × × × = cara.

Jadi, banyak cara untuk menyusun huruf-huruf S, O, P, A, dan N dengan huruf pertama dimulai huruf konsonan seluruhnya ada 72 cara.

W Contoh 2.1.3

Panitia penerimaan siswa baru suatu sekolah akan membuat nomor ujian peserta yang terdiri dari 4 angka, dari angka yang tersedia 1, 2, 3, 4, dan 5. Tetapi panitia menginginkan bahwa nomor ujian tidak diawali dengan angka 1. Berapa banyak cara untuk menyusun nomor ujian itu menjadi 4 angka, apabila:

a. nomor ujian itu boleh mempunyai angka yang sama?

b. nomor ujian itu tidak boleh mempunyai angka yang sama?

Penyelesaian:

a. Nomor ujian itu boleh mempunyai angka yang sama

Angka pertama (sebagai ribuan) dapat dipilih dengan 4 cara, yaitu angka 2, 3, 4, dan 5 karena disyaratkan angka pertama tidak boleh angka 1.

Karena nomor diperbolehkan mempunyai angka yang sama, maka:

angka kedua (sebagai ratusan) dapat dipilih dengan 5 cara, angka ketiga (sebagai puluhan) dapat dipilih dengan 5 cara, angka keempat (sebagai satuan) dapat dipilih dengan 5 cara.

Dengan aturan perkalian, seluruhnya terdapat 4 × 5 × 5 × 5 = 500 cara.

Jadi, banyak cara untuk menyusun angka 1, 2, 3, 4, dan 5 menjadi 4 angka dengan angka pertama bukan angka 1 adalah 500 cara.

b. Nomor ujian itu tidak boleh mempunyai angka yang sama

Angka pertama (sebagai ribuan) dapat dipilih dengan 4 cara, lihat jawaban sebelumnya.

Angka kedua (sebagai ratusan) hanya dapat dipilih dengan 4 cara karena nomor tidak diperbolehkan mempunyai angka yang sama. Misalnya setelah dipilih angka pertama 2, maka angka kedua yang dapat dipilih tinggal 4 angka, yaitu 1, 3, 4, dan 5.

Angka ketiga (sebagai puluhan) dapat dipilih dengan 3 cara.

Angka keempat (sebagai satuan) dapat dipilih dengan 2 cara.

Menurut aturan perkalian, seluruhnya terdapat 4 × 4 × 3 × 2 = 96 cara.

Jadi, banyak cara untuk menyusun angka 1, 2, 3, 4, dan 5 menjadi 4 angka dengan angka pertama bukan angka 1 dan tidak boleh ada angka yang sama adalah 96 cara.

W

Contoh 2.1.4

Diberikan lima buah angka: 0, 1, 2, 3, dan 4, akan disusun bilangan-bilangan genap yang terdiri dari tiga angka. Berapa banyak cara untuk menyusun bilangan-bilangan genap yang terdiri tiga angka, apabila:

a. bilangan-bilangan genap itu boleh mempunyai angka yang sama?

b. bilangan-bilangan genap tidak boleh mempunyai angka yang sama?

Penyelesaian:

Bilangan genap adalah bilangan yang pada posisi satuan adalah bilangan genap.

Dalam hal ini haruslah 0, 2, atau 4.

a. Bilangan-bilangan genap boleh mempunyai angka yang sama

Angka pertama (sebagai ratusan) dapat dipilih dengan 4 cara. Angka 0 tidak dapat dipilih sebagai angka pertama karena 012 sebagai contoh, bukan bilangan yang terdiri dari tiga angka.

Angka kedua (sebagai puluhan) dapat dipilih dengan 5 cara.

Angka ketiga (sebagai satuan) dapat dipilih dengan 3 cara. Angka ketiga yang dapat dipilih adalah 0, 2, dan 4.

Angka keempat (sebagai satuan) dapat dipilih dengan 5 cara.

Dengan aturan perkalian, seluruhnya terdapat 4 × 5 × 3 = 60 cara.

Jadi, banyak cara untuk menyusun angka 0, 1, 2, 3, dan 4 menjadi bilangan genap yang terdiri 3 angka dengan bilangan-bilangan itu boleh mempunyai angka yang sama adalah 60 cara.

b. Bilangan-bilangan genap tidak boleh mempunyai angka yang sama Angka pertama (sebagai ratusan) dapat dipilih dengan 4 cara.

Angka kedua (sebagai puluhan) hanya dapat dipilih dengan 4 cara karena bilangan tidak boleh mempunyai angka yang sama.

Angka ketiga (sebagai satuan) dapat dipilih dengan 3 cara.

Seluruhnya terdapat 4 × 4 × 3 = 48 cara.

Jadi, banyak cara untuk menyusun angka 0, 1, 2, 3, dan 4 menjadi bilangan genap yang terdiri 3 angka dengan bilangan-bilangan itu tidak boleh mempunyai angka yang sama adalah 48 cara.

W Misalkan, untuk bepergian dari kota P ke kota R kita dapat melewati kota Q atau melewati kota S dengan berbagai alternatif jalur. Misalkan kita pergi dari kota P ke kota Q mempunyai 3 jalur pilihan, kemudian dari kota Q ke kota R tersedia 2 jalur pilihan, maka menurut aturan perkalian untuk bepergian dari kota P ke kota R melewati kota Q kita mempunyai 3 × 2 jalur.

Selanjutnya, misalkan kita pergi dari kota P ke kota S tersedia 2 jalur pilihan, kemudian dari kota S kita hanya mempunyai 1 jalur untuk sampai di kota R, maka banyaknya jalur yang tersedia bagi kita untuk bepergian dari kota P ke kota R melewati kota S adalah 2 × 1 jalur.

Lihat Gambar 2.3.

Gambar 2.3 Diagram Pohon Jalur Perjalanan Dari Kota P ke Kota R

Dari uraian di atas dapat kita simpulkan bahwa untuk bepergian dari kota P ke kota R kita mempunyai (3×2) + (2×1) = 8 jalur pilihan. Dalam pencacahan ini kita menggunakan apa yang disebut aturan penjumlahan. Aturan penjumlahan kita gunakan untuk melengkapi aturan perkalian, apabila cara mengisi tempat kedua setelah tempat pertama terisi tidak dapat kita lakukan menggunakan sesuatu yang sudah digunakan sebagai pilihan untuk mengisi tempat pertama. Secara umum kita mempunyai aturan penjumlahan berikut ini.

Aturan Penjumlahan

Jika terdapat n peristiwa yang saling lepas, dengan:

c1 adalah banyak cara pada peristiwa pertama,

c2 adalah banyak cara pada peristiwa kedua, ... dan seterusnya, cn adalah banyak cara pada pada peristiwa ke-n,

maka banyak cara untuk n buah peristiwa secara keseluruhan:

c1 + c2 + c3 + ... + cn

2.1.2 Permutasi

Permutasi dibedakan menjadi 4 macam, yaitu permutasi dari unsur-unsur yang berbeda, permutasi yang memuat beberapa unsur sama, permutasi siklis, dan permutasi berulang.

1. Permutasi dari Unsur-Unsur yang Berbeda

Pada putaran akhir pemilihan pengurus OSIS seperti telah dibahas pada awal bab, ada 2 tempat yang tersedia untuk diisi oleh 2 anak dari 4 anak (A, B, C, dan D). Posisi ketua dapat diisi dengan 4 cara. Karena tidak mungkin ketua merangkap sekretaris, maka posisi sekretaris dapat diisi dengan (4 – 1) = 3 cara. Secara keseluruhan untuk memilih pasangan ketua-sekretaris ada 4 × 3 = 12 cara. Pada contoh itu, anak yang telah terpilih sebagai ketua tidak dapat dipilih kembali untuk menduduki posisi sekretaris. Pemilihan seperti itu kita sebut pemilihan tanpa pemulihan.

P

S

R Q

1 2

3

1 2

1 1 2

Secara umum, banyak cara menempatkan n buah unsur ke dalam k tempat yang tersedia itu disebut permutasi k unsur dari n unsur, yang dinotasikan dengan P , yang diberikan sebagai:kn

× − × − × × − +L

= ( 1) ( 2) ( 1)

kn

P n n n n k

dengan k n≤ . Beberapa buku menggunakan notasi nPk, nPk atau P(n,k) untuk

kn

P .

Dengan notasi ini, pada masalah penentuan ketua dan sekretaris dari 4 anak di atas, merupakan permutasi k = 2 unsur dari n = 4 unsur, sehingga banyak cara menentukan ketua dan sekretaris sama dengan

24

P = 4 × (4–2+1) = 4 × 3 = 12.

Jika pada putaran akhir pemilihan pengurus OSIS di atas dari keempat calon akan ditentukan ketua, sekretaris, bendahara, dan pembantu umum, ada berapa macam susunan pengurus yang mungkin timbul?

Masalah ini adalah pengisian tempat tanpa pemulihan dari 4 unsur ke dalam 4 tempat yang tersedia. Posisi ketua adalah salah satu dari empat anak itu. Yang menjadi sekretaris adalah salah satu dari 3 orang yang tersisa, yang menjadi bendahara adalah salah satu dari 2 orang yang tersisa. Akhirnya posisi pembantu umum hanya dapat ditempati satu anak. Dalam hal ini adalah kasus permutasi dari n = 4 anak ke dalam k = 4 tempat yang tersedia. Sehingga, banyaknya susunan pengurus adalah P = 4 × 3 × 2 × 1 = 24.44

Secara umum, jika k = n, maka permutasi n unsur dari n unsur yang tersedia disebut permutasi n, yang diberikan oleh:

= ( 1) ( 2) 3 2 1

nn

P n n× − × − × × × ×n L

Bagaimana hubungan P dan kn Pnn? Untuk menjawab pertanyaan ini, terlebih dahulu kita bahas pengertian faktorial dari bilangan asli.

Faktorial dari suatu bilangan asli didefinisikan berikut ini.

Untuk sembarang bilangan asli n, didefinisikan

! ( 1) ( 2) 3 2 1

n = × − × − × × × ×n n n L

Notasi n! dibaca “n faktorial”. Didefinisikan pula bahwa 0! = 1 dan 1! = 1.

Sebagai contoh,

4! = 4 × 3 × 2 × 1 = 24

6! = 6 × 5 × 4 × 3 × 2 × 1 = 720

9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362.880, ... , dan seterusnya.

Dengan pengertian faktorial, kita dapat menuliskan permutasi sebagai:

= ( 1) ( 2) 3 2 1 !

nn

P n n× − × − × × × × =n L n (2.1)

Lebih lanjut, karena P n nkn= (× − × − × × − +1) (n 2) L

(

)

= ( 1) ( 2) ( 1) ( ) ( 1) 3 2 1

nn

P n n× − × − × × − + × − × − − × × × ×n L n k n k n k L n P n k!= kn( − )!

Jadi, kita memperoleh hubungan:

! ( )!

n

k n

P = n k− , n k≥ (2.2)

Contoh 2.1.5

Tunjukkan bahwa n n n!= × −( 1)!. Penyelesaian:

Dari definisi n faktorial,

( )

! ( 1) ( 2) 3 2 1 ( 1)!

n = n× n− × − × × × × = × −n L n n

W Contoh 2.1.6

Hitunglah nilai dari setiap permutasi berikut.

a. P25 b. P46 c. P510 d. P88 Penyelesaian:

Dengan persamaan (2.1) dan (2.2), kita peroleh:

a. 25 5! 5! 5 4 3 2 1 5 4 20

(5 2)! 3! 3 2 1

P = = = × × × × = × =

− × ×

b. 46 6! 6! 6 5 4 3 2 1 6 5 4 3 360

(6 4)! 2! 2 1

P = = = × × × × × = × × × =

− ×

c. 410 10! 10!

(10 4)! 6!

10 9 8 7 6 5 4 3 2 1 6 5 4 3 2 1 10 9 8 7 5020

P = =

−

× × × × × × × × ×

= × × × × ×

= × × × =

d. P =88 8! 8 7 6 5 4 3 2 1 40.320= × × × × × × × =

W

Tugas Mandiri

Dengan hasil (2.1) dan (2.2), buktikan: (n k P− )! kn = k P! n kn− = Pnn.

Contoh 2.1.7

Berapakah banyak permutasi dari 2 huruf yang diambil dari 4 huruf: A, B, C, dan D.

Penyelesaian:

Hal ini merupakan permutasi dari 4 unsur ke dalam 2 unsur, sehingga menurut persamaan (2.2) banyak permutasi adalah:

24 4! 4 3 2 1

(4 2)! 2 1 12

P × × ×

= = =

− ×

Susunan huruf yang mungkin terlihat pada Gambar 2.4.

Gambar 2.4 Permutasi 2 Huruf dari 4 Huruf

W 2. Permutasi yang Memuat Beberapa Unsur Sama

Pada bagian sebelumnya telah kita bahas permutasi dari n unsur berbeda, bagaimana jika dari n unsur itu terdapat beberapa unsur yang sama.

Untuk menjawab pertanyaan ini coba kita ikuti ilustrasi pada contoh berikut ini.

AB AC AD BA BC BC CA CB CD DA DB DC

hurufhurufsusunan huruf

A

B

C

D

A B C A B C A B C A B C

Contoh 2.1.8

Berapa banyak permutasi 3 huruf yang diambil dari huruf P, Q, dan Q?

Penyelesaian:

Unsur yang tersedia ada 3, yaitu P, Q, dan Q. Dari ketiga unsur ini ada dua unsur yang sama, yaitu huruf Q. Akan kita gunakan pendekatan permutasi dengan 3 unsur yang berbeda untuk menentukan banyak permutasi dari 3 unsur yang memuat 2 unsur sama. Pertama, anggap 2 unsur yang sama yaitu Q sebagai dua unsur yang berbeda dengan memberinya indeks Q1 dan Q2.

Banyak permutasi 3 unsur yang berbeda P, Q1, dan Q2 adalah 3! = 6, yaitu permutasi-permutasi:

PQ1Q2, PQ2Q1, Q1PQ2, Q1Q2P, Q2PQ1, Q2Q1P

Dengan menghapus indeks-indeksnya, permutasi di atas dapat kita kelompokkan ke dalam permutasi yang sama. Misalnya,

- Kelompok PQ1Q2 dan PQ2Q1, jika indeksnya dihapuskan, maka diperoleh permutasi PQQ.

- Kelompok Q1PQ2 dan Q2PQ1, jika indeksnya dihapuskan, maka diperoleh permutasi QPQ.

- Kelompok Q1Q2P dan Q2Q1P, jika indeknya dihapuskan, maka diperoleh permutasi QQP.

Tampak bahwa jika indeksnya dihapuskan, maka setiap kelompok yang terdiri dari 2! = 2 permutasi, berubah menjadi 1 permutasi. Oleh karena itu, banyak permutasi 3 unsur yang memuat 2 unsur sama adalah 3, yang dapat kita nyatakan sebagai:

3! 3 2 1 3

2! 2 1

P= = × ×× = dengan permutasinya adalah PQQ, QPQ, dan QQP.

W Berdasarkan contoh di atas, secara umum kita mempunyai aturan berikut ini.

1. Jika dari n unsur yang tersedia terdapat k unsur yang sama dengan k ≤n, maka banyak permutasi dari n unsur adalah:

!

!

P=nk (2.3)

2. Jika dari n unsur yang tersedia terdapat k unsur yang sama, l unsur yang sama, dan m unsur yang sama dengan k+ + ≤l m n, maka banyak permutasi dari n unsur itu adalah:

!

! ! !n

P=k l m (2.4)

Contoh 2.1.9

Misalkan terdapat 7 buah foto, 4 buah foto dengan bingkai berbentuk persegi dan 3 buah foto dengan bingkai berbentuk oval. Berapa banyak cara untuk menyusun 7 buah foto itu secara berdampingan?

Penyelesaian:

Banyak unsur: n = 7, banyak unsur yang sama: k = 4 (untuk foto dengan bingkai persegi) dan l = 3 (untuk foto dengan bingkai oval). Jadi, banyak cara untuk menyusun 7 buah foto itu secara berdampingan adalah

7! 7 6 5 4 3 2 1 7 5 35

4!3! (4 3 2 1)(3 2 1)

P= = × × × × × ×× × × × × = × =

W 3. Permutasi Siklis

Misalkan Awan (A), Beti (B), dan Cinta (C) pergi ke restoran, mereka duduk mengelilingi meja berbentuk lingkaran. Posisi duduk mereka hanya dua kemungkinan seperti diperlihatkan oleh gambar berikut ini.

Gambar 2.5 Posisi Duduk 3 Orang Melingkar

Dalam bentuk bagan, Gambar 2.5 dapat kita sederhanakan menjadi Gambar 2.6.

(a) (b)

Gambar 2.6 Bagan Posisi Duduk 3 Orang Melingkar

Dari Gambar 2.6 (a) jika dibaca searah dengan arah putaran jarum jam, kita peroleh 3 susunan yang mungkin, yaitu:

ABC, BCA, dan CAB

⊗

⊗ ⊗

B

A C

⊗

⊗ ⊗

B

C A

Tetapi ketiga susunan ini sebenarnya memberikan sebuah susunan yang sama, yaitu susunan yang diperlihatkan oleh Gambar 2.6 (a).

Seperti susunan Gambar 2.6 (a), susunan Gambar 2.6 (b) jika dibaca searah dengan arah putaran jarum jam, kita peroleh 3 susunan yang mungkin, yaitu:

ACB, CBA, dan BAC

Ketiga susunan ini memberikan sebuah susunan yang sama, yaitu susunan yang diperlihatkan oleh Gambar 2.6 (b).

Dari kedua ilustrasi ini, dapat kita simpulkan bahwa banyak susunan dari huruf A, B, dan C yang ditempatkan pada kurva tertutup berbentuk lingkaran adalah 2! = 2 macam, yaitu susunan yang diberikan oleh Gambar 2.6.

Penempatan unsur-unsur dengan cara inilah yang disebut permutasi siklis atau permutasi sirkuler (circular permutation). Secara umum kita mempunyai aturan berikut ini.

Jika tersedia n unsur yang berbeda, maka banyak permutasi siklisnya adalah

siklis ( 1)!

P = −n (2.5)

Untuk memahami tentang permutasi siklis ini, kita ikuti contoh berikut.

Contoh 2.1.10

Berapa cara yang mungkin dapat dibuat, jika dalam suatu pesta makan terdapat 7 orang yang duduk dalam:

a. berjajar dalam satu baris, b. meja makan bundar.

Penyelesaian:

a. Posisi duduk berjajar dalam satu baris merupakan permutasi 7 unsur dari 7 unsur, sehingga menurut persamaan (2.1),

7= =

7 7! 5.040

P cara

Jadi, jika 7 orang tersebut duduk berjajar dalam satu baris, maka banyak cara mereka duduk ada 5.040 cara.

b. Posisi duduk mengelilingi meja makan bundar merupakan permutasi siklis dari 7 unsur, sehingga menurut persamaan (2.5),

siklis (7 1) 6! 720

P = − = = cara

Jadi, jika 7 orang tersebut duduk mengelilingi meja bundar, maka banyak cara mereka duduk ada 720 cara.

W 4. Permutasi Berulang

Kita ingat kembali bahwa permutasi dari 3 huruf, P, Q dan R, adalah susunan-susunan yang berbentuk:

PQR, PRQ, QPR, QRP, RPQ, RQP

Dalam susunan ini, unsur-unsur yang tersedia tidak boleh berulang. Jika unsur-unsur yang tersedia boleh berulang, misalkan

PPP, PPQ, PPR, ..., QQP, QQR...., dan seterusnya

maka permutasi semacam ini disebut permutasi berulang (repeated permutation).

Dengan memperhatikan permutasi di atas, maka banyaknya permutasi berulang dari huruf P, Q, dan R ditentukan sebagai berikut.

- Huruf pertama dapat dipilih dengan 3 cara, yaitu huruf P, Q, dan R.

- Huruf kedua dan huruf ketiga dapat dipilih masing-masing dengan 3 cara karena huruf-hurufnya boleh berulang

Dengan menggunakan aturan perkalian, maka banyak permutasi seluruhnya adalah:

3 3 3 3× × = 3 =27

Jika dari 3 huruf, P, Q, dan R, akan disusun 2 huruf dengan huruf-huruf boleh berulang, maka banyak permutasi berulang dua huruf yang diambil dari 3 huruf yang tersedia ditentukan sebagai berikut.

- Huruf pertama dapat dipilih dengan 3 cara, yaitu huruf P, Q, dan R.

- Huruf kedua dapat dipilih dengan 3 cara karena huruf-hurufnya boleh berulang.

Dengan menggunakan aturan perkalian, maka banyak permutasi seluruhnya adalah:

3 3 3× = 2 =9

Dari dua ilustrasi di atas, maka secara umum kita mempunyai aturan berikut ini.

Jika tersedia n unsur yang berbeda, maka banyak permutasi berulang k unsur yang diambil dari n unsur (k n≤ ) adalah:

Pberulang=nk (2.6)

Contoh 2.1.11

Diberikan angka 1, 2, 3, 4, 5, dan 6, akan dibentuk bilangan-bilangan yang terdiri dari 4 angka dengan angka-angka boleh berulang. Berapa banyak bilangan yang dapat dibentuk?

Penyelesaian:

Banyak unsur yang tersedia adalah n = 6, yaitu angka 1, 2, 3, 4, 5, dan 6. Dibentuk bilangan yang terdiri dari 4 angka, kita ambil k = 4. Karena angka-angka boleh berulang, maka bilangan yang tersusun merupakan permutasi berulang, dengan k = 4, sehingga dengan persamaan (2.6) kita peroleh

= 4 =

berulang 6 1.296 P

Jadi, banyak bilangan yang dapat dibentuk seluruhnya ada 1.296 macam.

W

2.1.3 Kombinasi

Sekolah akan mengikuti perlombaan paduan suara yang tiap regunya terdiri dari 2 anak. Dari hasil seleksi diperoleh 4 anak, A, B, C dan D, yang memenuhi kriteria yang telah ditentukan. Pertanyaannya adalah berapa regu yang dapat dipilih dari empat anak tersebut?

Untuk menjawab pertanyaan ini, perhatikan kembali banyaknya cara keempat anak, A, B, C, dan D, dapat menempati tempat pertama dan kedua. Kemungkinan-kemungkinannya adalah:

{AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC}

Kita tahu bahwa susunan AB dan susunan BA menentukan satu regu yang sama karena tidak memperhatikan urutan. Demikian pula halnya susunan AC = CA, AD = DA, BC = CB, BD = DB, dan CD = DC. Jadi, ada 12 2 6= cara untuk menyusun regu paduan suara yang terdiri atas 2 anak dari 4 anak yang tersedia,

{AB, AC, AD, BC, BD, CD}

Banyak cara memilih 2 unsur dari 4 unsur yang tersedia disebut kombinasi 2 unsur dari 4 unsur. Secara umum kita mempunyai definisi berikut ini.

Definisi:

Kombinasi k unsur yang diambil dari n unsur yang berbeda adalah suatu pilihan dari k unsur tanpa memperhatikan urutannya (k n≤ ), dinotasikan dengan Ckn.

Dengan kata lain, banyak kombinasi k unsur yang diambil dari n unsur yang tersedia adalah banyak cara memilih k unsur yang diambil dari n unsur yang tersedia tanpa memperhatikan urutannya.

Kita masih ingat bahwa banyaknya cara memilih 2 anak dari 4 anak untuk ditempatkan dalam dua kedudukan yang berbeda adalah permutasi 2 unsur dari 4 unsur yang tersedia, yaitu 24 4! 12

(4 2)!

P = =

− . Untuk kombinasi AB yang tata letak unsur-unsur A dan B-nya tidak diperhatikan, dapat diturunkan 2! = 2 permutasi karena setiap kombinasi memberikan 2 permutasi. Jadi, kita peroleh hubungan:

4 4

2 2

2C =P atau

4 24

2 2

C =P

Secara umum, untuk setiap kombinasi k unsur dari n unsur yang tersedia, kita dapat membentuk Pkk=k! permutasi. Oleh karena itu, terdapat hubungan antara kombinasi k unsur dari n unsur yang tersedia, yaitu Cnk, dengan permutasi k unsur dari n unsur yang tersedia, yaitu Pkn adalah:

!

!( )!

n kn

k k

k

P n

C =P =k n k− (2.7)

Contoh 2.1.12

Hitunglah nilai dari setiap kombinasi berikut.

a. C25 b. C46 c. C105 d. C37 Penyelesaian:

Langsung kita gunakan rumus pada persamaan (2.7), diperoleh:

a. 25 5! 5! 5 4 3 2 1 5 2 10

2!(5 2)! 2!3! (2 1)(3 2 1)

C = = = × × × × = × =

− × × ×

b. 64 6! 6! 6 5 4 3 2 1 5 4!(6 4)! 4!2! (4 3 2 1)(3 2 1)

C = = = × × × × × =

− × × × × ×

c. 510 10! 10!

5!(10 5)! 5!5!

10 9 8 7 6 5 4 3 2 1 2 9 2 7 252 (5 4 3 2 1)(5 4 3 2 1)

C = =

−

× × × × × × × × ×

= = × × × =

× × × × × × × ×

d. 37 7! 7! 7 6 5 4 3 2 1 7 5 35

3!(7 3)! 3!4! (3 2 1)(4 3 2 1)

C = = = × × × × × × = × =

− × × × × ×

W Contoh 2.1.13

Berapakah kemungkinan jumlah kombinasi yang dapat dibuat dari 4 orang, A, B, C, dan D, yang ingin membuat suatu panitia yang terdiri 3 orang?

Penyelesaian:

Masalah ini adalah kombinasi 3 unsur dari 4 unsur yang tersedia, sehingga dari persamaan (2.7) diperoleh:

4

3 4! 4! 4 3 2 1 4

3!(4 3)! 3!1! 3 2 1 1

C = = = × × × =

− × × ×

Jadi, terdapat 4 kemungkinan panitia yang terdiri dari 3 orang yang dapat dibentuk dari 4 orang, yaitu ABC, ABD, ACD, dan BCD.

W Contoh 2.1.14

Hitunglah nilai n , apabila C2n=4n+5. Penyelesaian:

Dari rumus pada persamaan (2.7) kita peroleh:

2 ! ( 1) ( 2) ( 3) 3 2 1 ( 1)

2!( 2)! (2 1)(( 2) ( 3) 3 2 1) 2

n n n n n n n n

C = n− = × − × − × − × × × ×× n− × − × × × ×n L = × − L

Di pihak lain, diketahui bahwa C2n=4n+5, sehingga diperoleh hubungan:

( 1) 4 5 2

n n× − = n+

⇔

⇔

⇔ (n−10)(n+ =1) 0

⇔

Karena n harus bilangan asli, maka n yang memenuhi adalah n = 10.

W Pada bagian akhir ini, kita akan menyelesaikan masalah pembentukan tim lomba renang yang diungkapkan pada awal bab.

Contoh 2.1.15

Tersedia 10 siswa yang memenuhi syarat menjadi tim lomba renang dari suatu SMA. Dari sejumlah siswa itu, 6 siswa pandai gaya bebas dan 4 siswa pandai gaya kupu-kupu. Tim yang dibentuk beranggotakan 3 siswa, yang terdiri dari 2 siswa pandai gaya bebas dan 1 siswa pandai gaya kupu-kupu. Berapa banyak susunan yang mungkin dapat dibentuk?

Penyelesaian:

Dua siswa dipilih dari 6 siswa yang pandai gaya bebas, sehingga kombinasinya adalah 26 6! 15

2!(6 2)!

C = =

− cara. Seorang anggota dipilih dari 4 siswa yang pandai gaya kupu-kupu, sehingga kombinasinya 14 4! 4

1!(4 1)!

C = =

− cara. Dengan menggunakan aturan perkalian, banyak susunan tim lomba renang yang terdiri dari 2 siswa pandai gaya bebas dan 1 siswa pandai gaya kupu-kupu adalah:

6 4

2 1 15 4 60

C C× = × =

Jadi, banyak susunan tim lomba renang yang terdiri dari 2 siswa pandai gaya bebas dan 1 siswa pandai gaya kupu-kupu yang dipilih dari 6 siswa pandai gaya bebas dan 4 siswa pandai gaya kupu-kupu adalah 60 susunan.

W

Aturan Pengisian Tempat yang Tersedia 1. Suatu kelompok penari latar mempunyai:

baju berwarna: merah, pink, biru, kuning, dan hijau, rok pendek berwarna: putih, ungu, dan cokelat, sepatu berwarna: merah dan hitam.

Latihan 2.1

a. Gambarkan diagram pohon yang menghubungkan warna baju, warana rok pendek, dan warna sepatu.

b. Berapa banyak pasangan warna seragam yang dapat disusun ?

2. Suatu apartemen terdiri dari empat lantai, masing-masing lantai berturut-turut dihuni 12 orang, 8 orang, 6 orang, dan 5 orang. Dari setiap lantai akan dipilih seorang wakil untuk dibentuk sebagai pengurus apartemen. Berapa cara susunan pengurus dapat dibentuk?

3. Perjalanan dari Jakarta ke Bandung dapat melalui 4 jalur, dari Bandung ke Yogyakarta dapat melalui 2 jalur, dan dari Yogyakarta ke Surabaya melalui 3 jalur. Berapa banyak jalur perjalanan yang dapat dipilih dari perjalanan-perjalanan berikut ini.

a. Dari Jakarta ke Yogyakarta melalui Bandung.

b. Dari Surabaya ke Jakarta melalui Yogyakarta.

c. Dari Jakarta ke Surabaya melalui Bandung dan Yogyakarta.

4. Bahasa

Diberikan 11 huruf masing-masing H, I, D, U, P, C, E, R, D, A, dan S. Berapa banyak cara

Diberikan 11 huruf masing-masing H, I, D, U, P, C, E, R, D, A, dan S. Berapa banyak cara