the sphere packing bound · 1.7 koefisien binomial . kombinatorik merupakan studi tentang...

L/O/G/O

KOMBINATORIK

Selasa, 22 Nopember 2016

By :

ILHAM SAIFUDIN

www.themegallery.com

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


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.1 Pendahuluan


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 objek-

objek.

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

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,4 =5!

5 − 4 != 120

Contoh:


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))


1.4 Kombinasi

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.

Definisi. Kombinasi 𝑟 elemen dari 𝑛 elemen, atau 𝐶(𝑛, 𝑟) adalah

jumlah pemilihan yang tidak terurut 𝑟 elemet yang diambil dari

𝑛 buah elemen.


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 𝑃 𝑛, 𝑛 = 𝑛!



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)!

(𝑛−𝑛1)!

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

(𝑛−𝑛1−𝑛2−⋯−𝑛𝑘−1)!

𝑛𝑘!(𝑛−𝑛1−𝑛2−⋯−𝑛𝑘−1−𝑛𝑘)!

=𝑛!

𝑛1!𝑛2!…𝑛𝑘!

Sehingga

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

𝑛1! 𝑛2! … 𝑛𝑘!



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

Jumlah string= 𝑃(11; 1,4,4,2) =11!

1!4!4!2!= 34650



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. 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

Contoh:



(𝑥 + 𝑦)𝑛= 𝐶 𝑛, 0 𝑥𝑛 + 𝐶 𝑛, 1 𝑥𝑛−1𝑦1 +⋯+ 𝐶 𝑛, 𝑘 𝑥𝑛−𝑘𝑦𝑘 +⋯+ 𝐶 𝑛, 𝑛 𝑦𝑛

= 𝐶(𝑛, 𝑘)𝑥𝑛−𝑘𝑦𝑘𝑛𝑘=0

Koefisien untuk 𝑥𝑛−𝑘𝑥𝑘 adalah c(n,k). Bilangan C(n,k) disebut koefisien

binomial.

Bentuk umum:



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

Contoh:

the sphere packing bound · 1.7 koefisien binomial . kombinatorik merupakan studi tentang...

Documents