O KOMBINATORIK. By : ILHAM SAIFUDIN

L/O/G/O

KOMBINATORIK

By :

ILHAM SAIFUDIN

Senin, 09 Mei 2016

1.2 Kaidah Dasar menghitung BAB 4. KOMBINATORIK 1.1 Pendahuluan 1.2 Kaidah Dasar Menghitung 1.3 Permutasi

1.4 Kombinasi 1.5 Permutasi dan Kombinasi bentuk Umum 1.6 Kombinasi dengan pengulangan

1.7 Koefisien Binomial

www.themegallery.com

1.1 Pendahuluan Kombinatorik merupakan studi tentang pengaturan objek-objek, yaitu pemasangan, pengelompokan, pengurutan, pemilihan, atau penempatan objek-objek dengan karakteristik tertentu. Contoh: 1. Berapa banyak cara menyusun nomor kendaraan bermotor yang terdiri atas dua huruf dan diikuti 4 angka ? 2. Berapa angka yang muncul pada pelemparan dadu ? 3. Berapa banyak kemungkinan 5 susunan huruf jika didalam susunan tersebut tidak boleh ada huruf yang berulang ?


1.2 Kaidah Dasar menghitung 1

Kaidah Perkalian (rule of product)

Percobaan 1 : a Percobaan 2 : b Hasil percobaan 1 dan percobaan 2 : a x b Untuk 𝑛 percobaan dengan 𝑎𝑖 , maka berlaku : 𝑎1 × 𝑎2 × ⋯ × 𝑎𝑛 2

Kaidah Penjumlahan (rule of sum) Percobaan 1 : a Percobaan 2 : b Hasil percobaan 1 atau percobaan 2 : a + b Untuk 𝑛 percobaan dengan 𝑎𝑖 , maka berlaku : 𝑎1 + 𝑎2 + ⋯ + 𝑎𝑛


1.2 Kaidah Dasar menghitung Contoh: 1

Diketahui bit biner hanya 0 dan 1. Tentukan banyak string biner jika: a. Panjang string 4 bit b. Panjang string 7 bit Jawab: a. 2 × 2 × 2 × 2 = 24 = 16 buah b. 27 = 128 buah

2

Diketahui mahasiswa TI yang menempuh matdis yaitu mahasiswa laki-laki sebanyak 30 dan perempuan sebanyak 10. Dua orang mahasiswa akan diikutkan lomba KTI. Berapa banyak cara memilih 2 perwakilan tersebut ? Jawab: 30 × 10 = 300


1.3 Permutasi Permutasi adalah jumlah urutan berbeda dari pengaturan objekobjek. Permutasi merupakan bentuk khusus aplikasi kaidah perkalian. Misalkan jumlah objek adalah 𝑛, maka  Urutan pertama dipilih 𝑛 objek  Urutan kedua dipilih 𝑛 − 1 objek  Urutan ketiga dipilih 𝑛 − 2 objek  Urutan terakhir dipilih dari 1 objek tersisa Sehingga permutasi dari 𝑛 objek adalah 𝑛 𝑛 − 1 𝑛 − 2 … 1 = 𝑛!


1.3 Permutasi Contoh: 1

Berapa banyak kata yang terbentuk dari kata “KOMPUTER” ? Jawab : 𝑃 8,8 = 8! = 40.320 kata

2

Berapa cara mengurutkan nama 45 orang mahasiswa? Jawab : 𝑃 45,45 = 45! kata


BAB I. PENDAHULUAN

1.3.1 Permutasi 𝒓 dari 𝒏 elemen Definisi Permutasi r dari n elemen adalah jumlah kemungkinan urutan r buah elemen yang dipilih dari n buah elemen, dengan 𝑟 ≤ 𝑛, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada elemen yang sama, 𝑛! 𝑃 𝑛, 𝑟 = 𝑛 𝑛 − 1 𝑛 − 2 … 𝑛 − 𝑟 − 1 = 𝑛−𝑟 !


BAB I. PENDAHULUAN

1.3.1 Permutasi 𝒓 dari 𝒏 elemen Contoh: Berapakah jumlah kemungkinan dapat membentuk 4 angka dari 5 angka yaitu 1,2,3,4,5, jika: -Boleh ada pengulangan angka -Tidak boleh ada pengulangan angka Jawab : -Menggunakan kaidah perkalian: 5 5 5 5 = 54 = 625 -Dengan kaidah perkalian: (5)(4)(3)(2)=120 buah -Dengan rumus permutasi: 5! 𝑃 5,4 = = 120 5−4 !


BAB I. PENDAHULUAN

1.3.1 Permutasi 𝒓 dari 𝒏 elemen Bola Wadah

Ada enam buah bola yang berbeda warna dan 3 buah wadah. Masing-masing kotak hanya boleh diisi 1 buah bola. Berapa jumlah urutan berbeda yang mungkin dibuat dari penempatan bola ke dalam wadah terdebut? Jawab: Jumlah urutan berbeda dari penempatan bola =(6)(5)(4)=120 Maka jumlah urutan berbeda dari penempatan bola dengan 𝑛 buah bola dan 𝑟 buah kotak (𝑟 ≤ 𝑛) : 𝑛 𝑛 − 1 𝑛 − 2 … (𝑛 − (𝑟 − 1)) www.themegallery.com

1.4 Kombinasi Definisi. Kombinasi 𝑟 elemen dari 𝑛 elemen, atau 𝐶(𝑛, 𝑟) adalah jumlah pemilihan yang tidak terurut 𝑟 elemet yang diambil dari 𝑛 buah elemen.

Bentuk khusus dari permutasi adalah kombinasi. Jika permutasi, urutan kemunculan diperhitungkan. Sedangkan kombinasi, urutan kemunculan diabaikan. Secara umum dapat dirumuskan : 𝐶 𝑛, 𝑟 =

𝑛 𝑛 − 1 𝑛 − 2 … (𝑛 − (𝑟 − 1)) 𝑛! = 𝑟! 𝑟! 𝑛 − 𝑟 !

𝐶(𝑛, 𝑟) sering dibaca “𝑛 diambil 𝑟” artinya 𝑟 objek diambil dari 𝑛 buah objek.


1.5 Permuatasi dan Kombinasi Bentuk umum Contoh:

Misalkan ada 𝑛 buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang berwarna sama). 𝑛1 bola diantaranya berwarna 1, 𝑛2 bola diantaranya berwarna 2, 𝑛𝑘 bola diantaranya berwarna k dan 𝑛1 + 𝑛2 … + 𝑛𝑘 = 𝑛 Berapa jumlah cara pengaturan 𝑛 buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimal 1 buah bola)? Jika 𝑛 buah bola itu dianggap berbeda semua, maka jumlah cara pengaturan 𝑛 buah bola ke dalam 𝑛 buah kotak adalah 𝑃 𝑛, 𝑛 = 𝑛!


1.5 Permuatasi dan Kombinasi Bentuk umum Rumus:

Permutasi n buah bola yang mana 𝑛1 diantaranya berwarna 1, 𝑛2 bola berwarna 2,..., 𝑛𝑘 bola berwarna 𝑘 adalah 𝑃(𝑛, 𝑛) 𝑛! 𝑃 𝑛; 𝑛1 , 𝑛2 , … , 𝑛𝑘 = = 𝑛1 ! 𝑛2 ! … 𝑛𝑘 ! 𝑛1 ! 𝑛2 ! … 𝑛𝑘 ! Jumlah cara pengaturan seluruh bola ke dalam kotak : 𝐶 𝑛; 𝑛1 , 𝑛2 , … , 𝑛𝑘 = 𝐶 𝑛, 𝑛1 𝐶 𝑛 − 𝑛1 , 𝑛2 𝐶 𝑛 − 𝑛1 −𝑛2 , 𝑛3 … 𝐶(𝑛 − 𝑛1 −𝑛2 − ⋯ − 𝑛𝑘−1 , 𝑛𝑘 ) 𝑛! (𝑛−𝑛 )! (𝑛−𝑛 −𝑛 −⋯−𝑛 )! = 𝑛 !(𝑛−𝑛 )! 𝑛 !(𝑛−𝑛 1−𝑛 )! … 𝑛 !(𝑛−𝑛 1−𝑛 2−⋯−𝑛 𝑘−1−𝑛 1

1

𝑛! 1 !𝑛2 !…𝑛𝑘 !

2

1

2

𝑘

1

2

𝑘−1

𝑘 )!

=𝑛 Sehingga

𝑃 𝑛; 𝑛1 , 𝑛2 , … , 𝑛𝑘 = 𝐶 𝑛; 𝑛1 , 𝑛2 , … , 𝑛𝑘 =


𝑛! 𝑛1 ! 𝑛2 ! … 𝑛𝑘 !

1.5 Permuatasi dan Kombinasi Bentuk umum Contoh:

Berapa banyak kata yang dapat dibentuk dengan menggunakan huruf-huruf dari kata “MISSISSIPPI” ? Jawab : 𝑆 = *𝑀, 𝐼, 𝑆, 𝑆, 𝐼, 𝑆, 𝑆, 𝐼, 𝑃, 𝑃, 𝐼+ Huruf 𝑀 = 1 buah Huruf 𝐼 = 4 buah Huruf 𝑆 = 4 buah Huruf 𝑃 = 2 buah 𝑛 = 1 + 4 + 4 + 2 = 11 = |𝑆|, maka 11! Jumlah string= 𝑃(11; 1,4,4,2) = 1!4!4!2! = 34650


1.6 Kombinasi dengan pengulangan

Misalnya terdapat 𝑟 buah bola yang semua warnanya sama dengan 𝑛 buah kotak. I. Masing-masing kotak hanya boleh diisi paling banyak satu buah bola. Jumlah memasukkan bola : 𝐶(𝑛, 𝑟). II. Masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatan jumlah bola ). Jumlah cara memasukkan bola: 𝐶 𝑛 + 𝑟 − 1, 𝑟 = 𝐶(𝑛 + 𝑟 − 1, 𝑛 − 1)


1.6 Kombinasi dengan pengulangan Contoh:

1. Pada persamaan 𝑥1 + 𝑥2 + 𝑥3 = 10, 𝑥𝑖 adalah bilangan bulat > 0. berapakah jumlah kemungkinan solusinya? Jawab :  Analogi 𝑟 = 10 diibaratkan bola dan dimasukkan ke dalam 𝑥1 , 𝑥2 , 𝑥3 atau 3 buah kotak berarti 𝑛 = 3.  Misalkan : 𝑥1 = 3 𝑥2 = 3 𝑥3 = 4 Maka 𝑥1 +𝑥2 + 𝑥3 = 3 + 3 + 4 = 10 Sehingga ada 𝐶(𝑛 + 𝑟 − 1, 𝑟) = 𝐶(3 + 10 − 1,10) = 𝐶(12,10) =66



Bentuk umum:

(𝑥 + 𝑦)𝑛 = 𝐶 𝑛, 0 𝑥 𝑛 + 𝐶 𝑛, 1 𝑥 𝑛−1 𝑦 1 + ⋯ + 𝐶 𝑛, 𝑘 𝑥 𝑛−𝑘 𝑦 𝑘 + ⋯ + 𝐶 𝑛, 𝑛 𝑦 𝑛 = 𝑛𝑘=0 𝐶(𝑛, 𝑘)𝑥 𝑛−𝑘 𝑦 𝑘 Koefisien untuk 𝑥 𝑛−𝑘 𝑥 𝑘 adalah c(n,k). Bilangan C(n,k) disebut koefisien binomial.



Contoh:

Tentukan penjabaran dari (2x−1) 4 dan tentukan suku ketiganya! Jawab: Misalkan 𝑎 = 2𝑥 dan 𝑏 = (−1) Maka: (𝑎 + 𝑏)4 = 𝐶 4,0 𝑎4 + 𝐶 4,1 𝑎3 𝑏1 + 𝐶 4,2 𝑎2 𝑏2 + 𝐶 4,3 𝑎1 𝑏3 + 𝐶 4,4 𝑏4 (𝑎 + 𝑏)4 = 1𝑎4 + 4𝑎 3 𝑏1 + 6𝑎2 𝑏2 + 4𝑎1 𝑏3 + 1𝑏4 (𝑎 + 𝑏)4 = 16𝑥 4 − 32𝑥 3 + 24𝑥 2 − 8𝑥 + 1 Suku ketiga dari (2x−1) 4 adalah 𝐶 4,2 𝑎2 𝑏2 = 6𝑎2 𝑏2 = 24𝑥 2



O KOMBINATORIK. By : ILHAM SAIFUDIN

Recommend Documents