Toko roti Enak menjual 8 jenis roti berapa jumlah cara mengambil 1 lusin roti 1 lusin = 12 buah

M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 1
KOMBINATORIAL
Kombinatorial merupakan cabang matematika yang mempelajari pengaturan objek-
objek. Dengan analisis kombinatorial, memungkinkan kita dapat menentukan
pengaturan objek-objek tanpa dihitung satu per satu (enumerasi).
A. TEKNIK PERHITUNGAN
Dalam kombinatorial dikembangkan teknik-teknik menghitung jumlah kemungkinan
munculnya suatu kejadian tertentu atau jumlah elemen dalam suatu himpunan.
Contoh 1.
Pada semester ini, mahasiswa semester IV jurusan PMT, memperoleh tawaran 4 mata
kuliah bidang ilmu matematika yang berbeda, 3 mata kuliah bidang ilmu kependidikan
yang berbeda, dan 2 mata kuliah bidang ilmu agama yang berbeda. Berapa banyak cara
seorang mahasiswa semester IV tersebut jika:
a) harus memilih satu mata kuliah dari setiap bidang ilmu yang ditawarkan ?
b) hanya perlu memilih satu mata kuliah dari seluruh mata kuliah yang ditawarkan ?
Jawab:
a) Jumlah cara mahasiswa harus memilih satu mata kuliah dari setiap bidang ilmu
yang ditawarkan adalah:
b) Jumlah cara mahasiswa hanya memilih satu mata kuliah dari seluruh mata kuliah
yang ditawarkan adalah:
Seperti pada ilustrasi Contoh 1, pada permasalahan perhitungan sesungguhnya
terdapat dua prinsip dasar perhitungan, yaitu:
1. Prinsip Perkalian.
2. Prinsip Penjumlahan.
Dua prinsip ini akan menjadi pondasi dari hampir seluruh teknik perhitungan dalam
penyelesaian masalah perhitungan.
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 2
1. PRINSIP PERKALIAN
Pada langkah pertama terdapat cara dan pada langkah kedua terdapat cara, maka
jika harus memilih satu pilihan dari langkah pertama dan langkah kedua, maka jumlah
seluruh kemungkin akan terdapat cara.
Jika prinsip perkalian ini diperluas dengan sejumlah langkah, yaitu
langkah 1, terdapat cara,
langkah 2, terdapat cara,
langkah 3, terdapat cara,
:
langkah , terdapat cara,
Maka banyaknya aktivitas berbeda yang dilakukan secara bersamaan yang mungkin
adalah cara.
Dalam masalah pada Contoh 1, perhitungan banyaknya cara mahasiswa memilih satu
mata kuliah dari setiap bidang ilmu yang ditawarkan, dilakukan sebagai berikut:
langkah pertama adalah memilih satu mata kuliah dari bidang ilmu matematika
yang terdapat pilihan, kemudian
langkah kedua adalah memilih satu mata kuliah dari bidang ilmu kependidikan yang
terdapat pilihan, dan
langkah ketiga adalah memilih satu mata kuliah dari bidang ilmu agama yang
terdapat pilihan,
Jadi dengan prinsip perkalian diperoleh cara.
Interpretasi teori himpunan dalam prinsip perkalian ini, misalkan sebagai
produk Kartesian dari himpunan-himpunan dan , serta notasi jumlah elemen
pada himpunan , maka
Contoh 2.
Suatu sistem komputer menetapkan password bagi pengguna terdiri dari 4 digit
bilangan. Ada berapa banyak password yang mungkin ?
Jawab:
Untuk menempatkan 4 digit sebagai password maka dapat dilakukan:
langkah 1, mempunyai 10 cara (memilih satu bilangan dari 0, 1, 2, , 9),
langkah 2, mempunyai 10 cara,
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 3
langkah 3, mempunyai 10 cara,
langkah 4, mempunyai 10 cara,
Jadi akan diperoleh password.
2. PRINSIP PENJUMLAHAN
Pada langkah pertama terdapat cara dan pada langkah kedua terdapat cara, maka
jika harus memilih satu pilihan dari langkah pertama atau langkah kedua, maka jumlah
seluruh kemungkin akan terdapat cara.
Jika prinsip penjumlahan ini diperluas dengan sejumlah langkah, yaitu
langkah 1, terdapat cara,
langkah 2, terdapat cara,
langkah 3, terdapat cara,
:
langkah , terdapat cara,
Maka banyaknya aktivitas berbeda namun tidak dapat dilakukan secara bersamaan
adalah cara.
Dalam masalah pada Contoh 1, perhitungan banyaknya cara mahasiswa memilih satu
mata kuliah dari seluruh mata kuliah yang ditawarkan, dilakukan sebagai berikut:
langkah pertama adalah memilih satu mata kuliah dari bidang ilmu matematika
yang terdapat pilihan, atau
langkah kedua adalah memilih satu mata kuliah dari bidang ilmu kependidikan yang
terdapat pilihan, atau
langkah ketiga adalah memilih satu mata kuliah dari bidang ilmu agama yang
terdapat pilihan,
Jadi dengan prinsip penjumlahan diperoleh cara.
Interpretasi teori himpunan dalam prinsip penjumlahan ini, misalkan adalah
himpunan-himpunan saling lepas, maka
Contoh 3.
Di jurusan PMT pada suatu perguruan tinggi akan dilakukan pemilihan ketua himpunan
mahasiswa. Data seluruh mahasiswanya diperoleh sebagai berikut. Pada semester 2
terdapat 99 mahasiswa, semester 4 terdapat 103 mahasiswa, semester 6 terdapat 112
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 4
mahasiswa, dan pada semester 8 terdapat 120 mahasiswa, Berapa banyak pilihan yang
mungkin untuk pemilihan ketua himpunan mahasiswa tersebut, jika peraturan
menetapkan bahwa hanya mahasiswa semester 4 dan 6 yang boleh dipilih ?
Jawab:
Untuk memilih satu ketua himpunan mahasiswa maka dapat dilakukan:
langkah 1, jika memilih mahasiswa dari semester 4, dimiliki 103 cara, atau
langkah 2, jika memilih mahasiswa dari semester 6, dimiliki 112 cara,
Jadi akan diperoleh mahasiswa yang dapat dipilih.
B. DIAGRAM POHON
Diagram pohon adalah alat bantu untuk menghitung semua kemungkinan yang
dihasilkan oleh suatu barisan kejadian dalam sejumlah terhingga cara.
Contoh 4.
A B C dimana A = {1,2}, B = {a,b}, dan C = {x,y}.
Maka diagram pohonnya diilustrasikan sebagai berikut.
C. PRINSIP SARANG MERPATI

Prinsip Sarang Merpati (Pigeon hole): Jika sarang merpati terisi oleh atau
lebih merpati, maka paling tidak satu sarang terisi oleh lebih dari satu ekor merpati.
Contoh 5.
Dari 13 orang mahasiswa, maka akan ada minimal dua dari mahasiswa tersebut lahir
pada bulan yang sama.
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 5
Prinsip Sarang Merpati secara Umum: Jika sarang merpati terisi oleh
merpati, dimana bilangan bulat positif, maka paling tidak satu sarang merpati terisi
oleh atau lebih merpati.
atau
Jika objek ditempatkan ke lokasi, maka terdapat paling sedikit satu lokasi yang
memuat sedikitnya objek.
Contoh 6.
Tentukan jumlah minimum mahasiswa di suatu kelas untuk memastikan bahwa 3 orang
diantaranya lahir pada bulan yang sama.
Jawab:
Di sini bulan sebagai sarang merpati. Memastikan minimal 3 orang lahir pada
bulan yang sama maka Jadi jumlah minimum mahasiswa di
dalam kelas itu adalah orang.
Latihan 1.
1. Suatu kelas terdiri dari 18 mahasiswa laki-laki dan 14 mahasiswa perempuan. Ada
berapa cara memilih :
a. 1 orang perwakilan kelas ?
b. 2 orang perwakilan kelas sebagai ketua kelas dan wakilnya ?
c. 2 orang perwakilan kelas dengan memperhatikan 1 orang laki-laki dan 1 orang
perempuan ?
2. Sebuah sandi-lewat (password) panjangnya 6 sampai 8 karakter. Karakter boleh
berupa huruf atau angka. Berapa banyak kemungkinan sandi-lewat yang dapat
dibuat ?
3. Berapa banyak plat nomor kendaraan di Jakarta dengan memuat satu huruf di
depan, kemudian diikuti 4 digit angka, dan diakhiri dengan 2 digit huruf ?
4. Untuk nomor telepon dengan 7 digit, berapa banyak nomor telepon yang berbeda,
jika tidak diperbolehkan angka 0 pada digit pertama ?
5. Berapa jumlah pengambilan minimum dari himpunan agar dua
bilangan yang dipilih berjumlah 10 ?
6. Terdapat selusin kaus kaki warna coklat dan selusin kaus kaki warna hitam di dalam
laci. Jika anda mengambil kaus kaki tanpa melihat, berapa kaus kaki yang harus anda
ambil dari laci agar memastikan bahwa anda akan memperoleh sepasang kaus kaki
sewarna ?
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 6
Sekilas Fungsi Faktorial
Hasil kali semua bilangan bulat positif dari 1 hingga n dinotasikan oleh n! (n faktorial)
Maka,
Didapat juga
dan .
Untuk besar, digunakan pendekatan Stirling:
Dalam perhitungan banyaknya cara pengaturan objek-objek, sering kali kita perlu
memperhatikan dua hal yaitu pengaturan dengan urutan dan pengaturan tanpa
memperhatikan urutan. Dua hal ini dikenal dengan Permutasi dan Kombinasi.
Perhatikan contoh soal berikut.
Contoh 7.
Misalkan terdapat 4 objek huruf A, B, C, dan D.
a. Berapa banyak cara kita mengambil 3 huruf dari antara 4 huruf tersebut ?
b. Berapa banyak cara kita menyusun 3 huruf (berbeda) dari antara 4 huruf tersebut ?
Jawab:
a. Mengambil 3 huruf dari 4 huruf A, B, C, dan D dapat dilakukan sebagai berikut :
ABC, ABD, ACD, dan BCD, jadi terdapat 4 cara.
Langkah ini hanya meminta pengambilan dengan memperhatikan perbedaan huruf-
huruf saja, tidak memperhatikan urutan penempatan huruf-huruf tersebut. Pada
penulisan ABC misalnya, itu diangg

Page 2

M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 1
KOMBINATORIAL
Kombinatorial merupakan cabang matematika yang mempelajari pengaturan objek-
objek. Dengan analisis kombinatorial, memungkinkan kita dapat menentukan
pengaturan objek-objek tanpa dihitung satu per satu (enumerasi).
A. TEKNIK PERHITUNGAN
Dalam kombinatorial dikembangkan teknik-teknik menghitung jumlah kemungkinan
munculnya suatu kejadian tertentu atau jumlah elemen dalam suatu himpunan.
Contoh 1.
Pada semester ini, mahasiswa semester IV jurusan PMT, memperoleh tawaran 4 mata
kuliah bidang ilmu matematika yang berbeda, 3 mata kuliah bidang ilmu kependidikan
yang berbeda, dan 2 mata kuliah bidang ilmu agama yang berbeda. Berapa banyak cara
seorang mahasiswa semester IV tersebut jika:
a) harus memilih satu mata kuliah dari setiap bidang ilmu yang ditawarkan ?
b) hanya perlu memilih satu mata kuliah dari seluruh mata kuliah yang ditawarkan ?
Jawab:
a) Jumlah cara mahasiswa harus memilih satu mata kuliah dari setiap bidang ilmu
yang ditawarkan adalah:
b) Jumlah cara mahasiswa hanya memilih satu mata kuliah dari seluruh mata kuliah
yang ditawarkan adalah:
Seperti pada ilustrasi Contoh 1, pada permasalahan perhitungan sesungguhnya
terdapat dua prinsip dasar perhitungan, yaitu:
1. Prinsip Perkalian.
2. Prinsip Penjumlahan.
Dua prinsip ini akan menjadi pondasi dari hampir seluruh teknik perhitungan dalam
penyelesaian masalah perhitungan.
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 2
1. PRINSIP PERKALIAN
Pada langkah pertama terdapat cara dan pada langkah kedua terdapat cara, maka
jika harus memilih satu pilihan dari langkah pertama dan langkah kedua, maka jumlah
seluruh kemungkin akan terdapat cara.
Jika prinsip perkalian ini diperluas dengan sejumlah langkah, yaitu
langkah 1, terdapat cara,
langkah 2, terdapat cara,
langkah 3, terdapat cara,
:
langkah , terdapat cara,
Maka banyaknya aktivitas berbeda yang dilakukan secara bersamaan yang mungkin
adalah cara.
Dalam masalah pada Contoh 1, perhitungan banyaknya cara mahasiswa memilih satu
mata kuliah dari setiap bidang ilmu yang ditawarkan, dilakukan sebagai berikut:
langkah pertama adalah memilih satu mata kuliah dari bidang ilmu matematika
yang terdapat pilihan, kemudian
langkah kedua adalah memilih satu mata kuliah dari bidang ilmu kependidikan yang
terdapat pilihan, dan

langkah ketiga adalah memilih satu mata kuliah dari bidang ilmu agama yang
terdapat pilihan,
Jadi dengan prinsip perkalian diperoleh cara.
Interpretasi teori himpunan dalam prinsip perkalian ini, misalkan sebagai
produk Kartesian dari himpunan-himpunan dan , serta notasi jumlah elemen
pada himpunan , maka
Contoh 2.
Suatu sistem komputer menetapkan password bagi pengguna terdiri dari 4 digit
bilangan. Ada berapa banyak password yang mungkin ?
Jawab:
Untuk menempatkan 4 digit sebagai password maka dapat dilakukan:
langkah 1, mempunyai 10 cara (memilih satu bilangan dari 0, 1, 2, , 9),
langkah 2, mempunyai 10 cara,
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 3
langkah 3, mempunyai 10 cara,
langkah 4, mempunyai 10 cara,
Jadi akan diperoleh password.
2. PRINSIP PENJUMLAHAN
Pada langkah pertama terdapat cara dan pada langkah kedua terdapat cara, maka
jika harus memilih satu pilihan dari langkah pertama atau langkah kedua, maka jumlah
seluruh kemungkin akan terdapat cara.
Jika prinsip penjumlahan ini diperluas dengan sejumlah langkah, yaitu
langkah 1, terdapat cara,
langkah 2, terdapat cara,
langkah 3, terdapat cara,
:
langkah , terdapat cara,
Maka banyaknya aktivitas berbeda namun tidak dapat dilakukan secara bersamaan
adalah cara.
Dalam masalah pada Contoh 1, perhitungan banyaknya cara mahasiswa memilih satu
mata kuliah dari seluruh mata kuliah yang ditawarkan, dilakukan sebagai berikut:
langkah pertama adalah memilih satu mata kuliah dari bidang ilmu matematika
yang terdapat pilihan, atau
langkah kedua adalah memilih satu mata kuliah dari bidang ilmu kependidikan yang
terdapat pilihan, atau
langkah ketiga adalah memilih satu mata kuliah dari bidang ilmu agama yang
terdapat pilihan,
Jadi dengan prinsip penjumlahan diperoleh cara.
Interpretasi teori himpunan dalam prinsip penjumlahan ini, misalkan adalah
himpunan-himpunan saling lepas, maka
Contoh 3.
Di jurusan PMT pada suatu perguruan tinggi akan dilakukan pemilihan ketua himpunan
mahasiswa. Data seluruh mahasiswanya diperoleh sebagai berikut. Pada semester 2
terdapat 99 mahasiswa, semester 4 terdapat 103 mahasiswa, semester 6 terdapat 112
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 4
mahasiswa, dan pada semester 8 terdapat 120 mahasiswa, Berapa banyak pilihan yang
mungkin untuk pemilihan ketua himpunan mahasiswa tersebut, jika peraturan
menetapkan bahwa hanya mahasiswa semester 4 dan 6 yang boleh dipilih ?
Jawab:
Untuk memilih satu ketua himpunan mahasiswa maka dapat dilakukan:
langkah 1, jika memilih mahasiswa dari semester 4, dimiliki 103 cara, atau
langkah 2, jika memilih mahasiswa dari semester 6, dimiliki 112 cara,
Jadi akan diperoleh mahasiswa yang dapat dipilih.
B. DIAGRAM POHON
Diagram pohon adalah alat bantu untuk menghitung semua kemungkinan yang
dihasilkan oleh suatu barisan kejadian dalam sejumlah terhingga cara.
Contoh 4.
A B C dimana A = {1,2}, B = {a,b}, dan C = {x,y}.
Maka diagram pohonnya diilustrasikan sebagai berikut.
C. PRINSIP SARANG MERPATI
Prinsip Sarang Merpati (Pigeon hole): Jika sarang merpati terisi oleh atau
lebih merpati, maka paling tidak satu sarang terisi oleh lebih dari satu ekor merpati.
Contoh 5.
Dari 13 orang mahasiswa, maka akan ada minimal dua dari mahasiswa tersebut lahir
pada bulan yang sama.
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 5
Prinsip Sarang Merpati secara Umum: Jika sarang merpati terisi oleh
merpati, dimana bilangan bulat positif, maka paling tidak satu sarang merpati terisi
oleh atau lebih merpati.
atau
Jika objek ditempatkan ke lokasi, maka terdapat paling sedikit satu lokasi yang
memuat sedikitnya objek.
Contoh 6.
Tentukan jumlah minimum mahasiswa di suatu kelas untuk memastikan bahwa 3 orang
diantaranya lahir pada bulan yang sama.
Jawab:
Di sini bulan sebagai sarang merpati. Memastikan minimal 3 orang lahir pada
bulan yang sama maka Jadi jumlah minimum mahasiswa di
dalam kelas itu adalah orang.
Latihan 1.
1. Suatu kelas terdiri dari 18 mahasiswa laki-laki dan 14 mahasiswa perempuan. Ada
berapa cara memilih :
a. 1 orang perwakilan kelas ?
b. 2 orang perwakilan kelas sebagai ketua kelas dan wakilnya ?
c. 2 orang perwakilan kelas dengan memperhatikan 1 orang laki-laki dan 1 orang
perempuan ?
2. Sebuah sandi-lewat (password) panjangnya 6 sampai 8 karakter. Karakter boleh
berupa huruf atau angka. Berapa banyak kemungkinan sandi-lewat yang dapat
dibuat ?
3. Berapa banyak plat nomor kendaraan di Jakarta dengan memuat satu huruf di
depan, kemudian diikuti 4 digit angka, dan diakhiri dengan 2 digit huruf ?
4. Untuk nomor telepon dengan 7 digit, berapa banyak nomor telepon yang berbeda,
jika tidak diperbolehkan angka 0 pada digit pertama ?
5. Berapa jumlah pengambilan minimum dari himpunan agar dua
bilangan yang dipilih berjumlah 10 ?
6. Terdapat selusin kaus kaki warna coklat dan selusin kaus kaki warna hitam di dalam
laci. Jika anda mengambil kaus kaki tanpa melihat, berapa kaus kaki yang harus anda
ambil dari laci agar memastikan bahwa anda akan memperoleh sepasang kaus kaki
sewarna ?
M a t e m a t i k a D i s k r i t
K o m b i n a t o r i a l 6
Sekilas Fungsi Faktorial
Hasil kali semua bilangan bulat positif dari 1 hingga n dinotasikan oleh n! (n faktorial)
Maka,
Didapat juga
dan .

Untuk besar, digunakan pendekatan Stirling:
Dalam perhitungan banyaknya cara pengaturan objek-objek, sering kali kita perlu
memperhatikan dua hal yaitu pengaturan dengan urutan dan pengaturan tanpa
memperhatikan urutan. Dua hal ini dikenal dengan Permutasi dan Kombinasi.
Perhatikan contoh soal berikut.
Contoh 7.
Misalkan terdapat 4 objek huruf A, B, C, dan D.
a. Berapa banyak cara kita mengambil 3 huruf dari antara 4 huruf tersebut ?
b. Berapa banyak cara kita menyusun 3 huruf (berbeda) dari antara 4 huruf tersebut ?
Jawab:
a. Mengambil 3 huruf dari 4 huruf A, B, C, dan D dapat dilakukan sebagai berikut :
ABC, ABD, ACD, dan BCD, jadi terdapat 4 cara.
Langkah ini hanya meminta pengambilan dengan memperhatikan perbedaan huruf-
huruf saja, tidak memperhatikan urutan penempatan huruf-huruf tersebut. Pada
penulisan ABC misalnya, itu diangg

Page 3

8/17/2019 01-03-Kombinatorial-2015 (1)
1/57
KOMBINATORIAL Bahan Kuliah : Matematika Diskrit
Oleh: Rinaldi Munir
Penambahan & Revisi : Imam Suhar! "#$%'
%
Source : Program Studi Teknik Informatika ITB Digunakan di Universitas Mercu Buana Yogyakarta
8/17/2019 01-03-Kombinatorial-2015 (1)
2/57
PENDAU!UAN
 Se"ua# sandi$%e&at ' password( )an*angnya + sam)ai , karakter- .arakter "o%e# "eru)a #uruf atau angka- Bera)a "anyak kemungkinan sandi$%e&at yang da)at di"uat/
abcdef
aaaade
a123fr
…
erhtgahn
yutresik
…
//// #
8/17/2019 01-03-Kombinatorial-2015 (1)
3/57
DE1INISI
 K!mbinat!rial ada%a# ca"ang matematika untuk meng#itung *um%a# )enyusunan o"*ek$ o"*ek tan)a #arus mengenumerasi semua kemungkinan susunannya-
(
8/17/2019 01-03-Kombinatorial-2015 (1)
4/57
KAIDAH DASAR MENGHITUNG
 .aida# )erka%ian 'rule of product (
Perco"aan 2: p #asi%
Perco"aan 3: q #asi%
Perco"aan 2 dan )erco"aan 3: p × q #asi%
 .aida# )en*um%a#an 'rule of sum(
Perco"aan 2: p #asi%
Perco"aan 3: q #asi%
Perco"aan 2 atau )erco"aan 3: p 4 q #asi%
)
8/17/2019 01-03-Kombinatorial-2015 (1)
5/57
 *!nt!h %+ .etua angkatan I1 3553 #anya 2 orang ')ria atau &anita6 tidak "ias gender(- 7um%a# )ria I13553 8 +9 orang dan *um%a# &anita 8 29 orang-
Bera)a "anyak cara memi%i# ketua angkatan/
Penye%esaian:
 *!nt!h #+ Dua orang )er&aki%an I13553 mendatangai Ba)ak Dosen untuk )rotes ni%ai u*ian- aki% yang di)i%i# 2 orang )ria dan 2 orang &anita- Bera)a "anyak cara memi%i# 3 orang &aki% tesre"ut/
Penye%esaian:

8/17/2019 01-03-Kombinatorial-2015 (1)
6/57
 *!nt!h %+ .etua angkatan I1 3553 #anya 2 orang ')ria atau &anita6 tidak "ias gender(- 7um%a# )ria I13553 8 +9 orang dan *um%a# &anita 8 29 orang-
Bera)a "anyak cara memi%i# ketua angkatan/
Penye%esaian: +9 4 29 8 ,5 cara-
 *!nt!h #+ Dua orang )er&aki%an I13553 mendatangai Ba)ak Dosen untuk )rotes ni%ai u*ian- aki% yang di)i%i# 2 orang )ria dan 2 orang &anita- Bera)a "anyak cara memi%i# 3 orang &aki% tesre"ut/
Penye%esaian: +9 × 29 8 ;
8/17/2019 01-03-Kombinatorial-2015 (1)
7/57
BE=APA 7UM!A .EMUN>.INA YAN> ADA/
Ada 9 )ria dan ? &anita :
 Per&aki%an 2 )ria dan 2 &anita : [email protected]? 835
 Per&aki%an 3 orang ')asangan "e"as( : ;@,
8
8/17/2019 01-03-Kombinatorial-2015 (1)
8/57
PERLUASAN KAIDAH DASAR
MENGHITUNG
Misa%kan ada n )erco"aan6 masing$masing dg pi #asi%
2- .aida# )erka%ian 'rule of product (
p2 × p3 ×  × pn #asi%
3- .aida# )en*um%a#an 'rule of sum(
p2 4 p3 4  4 pn #asi%
/
8/17/2019 01-03-Kombinatorial-2015 (1)
9/57
 *!nt!h (+ Bit "iner #anya 5 dan 2- Bera)a "anyak string "iner yang da)at di"entuk *ika:
'a( )an*ang string 9 "it
'"( )an*ang string , "it '8 2 byte(
Penye%esaian:
'a( 3 × 3 × 3 × 3 × 3 8 39 8 3 "ua# '"( 3, 8 39+ "ua#
0
8/17/2019 01-03-Kombinatorial-2015 (1)
10/57
 *!nt!h )+ Bera)a "anyak "i%angan gan*i% antara 2555 dan ;;;; 'termasuk 2555 dan ;;;; itu sendiri( yang
'a( semua angkanya "er"eda
'"( "o%e# ada angka yang "eru%ang-
Penye%esaian:
'a( )osisi satuan: 9 kemungkinan angka '26 6 96
8/17/2019 01-03-Kombinatorial-2015 (1)
11/57
 *!nt!h )+ Bera)a "anyak "i%angan gan*i% antara 2555 dan ;;;; 'termasuk 2555 dan ;;;; itu sendiri( yang
'a( semua angkanya "er"eda
'"( "o%e# ada angka yang "eru%ang-
Penye%esaian:
'a( )osisi satuan: 9 kemungkinan angka '26 6 96
8/17/2019 01-03-Kombinatorial-2015 (1)
12/57
%#
8/17/2019 01-03-Kombinatorial-2015 (1)

13/57
 *!nt!h + Sandi$%e&at ' password( sistem kom)uter )an*angnya + sam)ai , karakter- Tia) karakter "o%e# "eru)a #uruf atau angkaC #uruf "esar dan #uruf keci% tidak di"edakan- Bera)a "anyak sandi$%e&at yang da)at di"uat/
Penye%esaian: 7um%a# karakter )ass&ord 8 3+ 'A$( 4 25 '5$;( 8 + karakter-
7um%a# kemungkinan sandi$%e&at dengan )an*ang + karakter: '+('+('+('+('+('+( 8 ++ 8 3-2
8/17/2019 01-03-Kombinatorial-2015 (1)
14/57
!ati#an:
1. (a) Berapa banyak bilangan genap 2-angka?
(b) Berapa banyak bilangan ganjil 2-angka dengan setiap angka berbeda?
a. ( 9 ) x ( 5 ) = 45
Satuan  !"2"4"#"$ - ada 5
%ulu&an  1'..9  ada 9
a. ( $ ) x ( 5 ) = 4!
Satuan  1""5""9 ada 5
%ulu&an  1'..9  ada 9 - 1 = $
2. *ari 1!!.!!! bua& bilangan bulat p+siti, pertaa" berapa banyak bilanganyang mengandung tepat 
a. 1 bua& angka  
b. 1 bua& angka 4 
. 1 bua& angka 5 %)
8/17/2019 01-03-Kombinatorial-2015 (1)
15/57
- Tersedia + #uruf: a6 b6 c6 d6 e6 f - Bera)a *um%a# )engurutan  #uruf *ika:
'a( tidak ada #uruf yang diu%angC
'"( "o%e# ada #uruf yang "eru%angC 'c( tidak "o%e# ada #uruf yang diu%ang6 teta)i #uruf e #arus adaC
'd( "o%e# ada #uruf yang "eru%ang6 #uruf e
#arus ada
?- Tentukan "anyak cara )engaturan agar  orang ma#asis&a 7urusan Teknik Informatika 'I1(6 ? orang ma#asis&a Teknik .imia 'T.(6 ?
orang ma#asis&a Teknik >eo%ogi '>!(6 dan 3 orang ma#asis&a 1armasi '1A( da)at duduk da%am satu "aris se#ingga mereka dari de)artemen yang sama duduk "erdam)ingan/
%
8/17/2019 01-03-Kombinatorial-2015 (1)
16/57
%,
',('9( 8?5
8/17/2019 01-03-Kombinatorial-2015 (1)
17/57
PRINSIP INKLUSI-EKSKLUSI
%-
Setiap byte disusun +le& $-bit. Berapa banyak jula& byte yangdiulai dengan /110 atau berak&ir dengan /110?
%enyelesaian
isalkan
A = &ipunan byte yang diulai dengan /110"
B = &ipunan byte yang diak&iri dengan /110
A ∩  B = &ipunan byte yang beraal dan berak&ir dengan /110 aka
A ∪  B = &ipunan byte yang beraal dengan /110 atau berak&ir dengan /110
 A = 2# = #4"  B = 2# = #4"  A ∩  B = 24 = 1#. aka
 A ∪  B =  A 3  B   A ∩  B = 2
# 3 2
#  1# = #4 3 #4  1# = 112.
8/17/2019 01-03-Kombinatorial-2015 (1)
18/57
PERMUTASI
%/
B+la
m b p
+tak
1 2 
Berapa jula& urutan berbeda yang ungkin dibuat dari penepatan b+la ke dala k+tak-k+tak tersebut?
8/17/2019 01-03-Kombinatorial-2015 (1)
19/57
%0
+tak 1 +tak 2 +tak  6rutan
b p mbp
m
p b mpb
m p bmp
b
p m bpm
m b pmb
p
b m pbm
7ula& keungkinan urutan berbeda dari penepatan b+la ke
dala k+tak adala& ()(2)(1) = 8 = #.
8/17/2019 01-03-Kombinatorial-2015 (1)
20/57
 De1nisi: Permutasi ada%a# *um%a# urutan "er"eda dari )engaturan o"*ek$o"*ek-
 Permutasi meru)akan "entuk k#usus a)%ikasi kaida# )erka%ian-
 Misa%kan *um%a# o"*ek ada%a# n6 maka
 urutan )ertama di)i%i# dari n o"*ek6
 urutan kedua di)i%i# dari n F 2 o"*ek6
 urutan ketiga di)i%i# dari n F 3 o"*ek6
 
 urutan terak#ir di)i%i# dari 2 o"*ek yang tersisa-
Menurut kaida# )erka%ian6 )ermutasi dari n o"*ek ada%a#
n'n F 2( 'n F 3(  '3('2( 8 nG #$
8/17/2019 01-03-Kombinatorial-2015 (1)
21/57
HNT PE=MUTASI
*!nt!h ,+ Bera)a "anyak JkataK yang ter"entuk dari kata JAPUSK/
Penye%esaian:
Hara 2: '9('?('('3('2( 8 235 "ua# kata Hara 3: P'96 9( 8 9G 8 235 "ua# kata

*!nt!h -+ Bera)a "anyak cara mengurutkan nama 39 orang ma#asis&a/
Penye%esaian: P'396 39( 8 39G #%
8/17/2019 01-03-Kombinatorial-2015 (1)
22/57
P2RM3TASI R DARI N 2L2M2N Ada enam "ua# "o%a yang "er"eda &arnanya dan  "ua#
kotak- Masing$masing kotak #anya "o%e# diisi 2 "ua# "o%a- Bera)a *um%a# urutan "er"eda yang mungkin di"uat dari )enem)atan "o%a ke da%am kotak$kotak terse"ut/
Penye%esaian:
kotak 2 da)at diisi o%e# sa%a# satu dari + "o%a 'ada + )i%i#an(C
kotak 3 da)at diisi o%e# sa%a# satu dari 9 "o%a 'ada 9 )i%i#an(C
kotak  da)at diisi o%e# sa%a# satu dari ? "o%a 'ada ? )i%i#an(-
7um%a# urutan "er"eda dari )enem)atan "o%a 8 '+('9('?( 8 235 ##
B+la
m b p h k j
+tak
1 2 
8/17/2019 01-03-Kombinatorial-2015 (1)