Makalah Matematika Diskrit Kelompok 10
Makalah Matematika Diskrit Kelompok 10
Makalah Matematika Diskrit Kelompok 10
KOMBINATORIAL
Dosen Pengampu :
Disusun Oleh :
Nalagusriani (A1C221013)
Apriansyah (A1C221105)
Kelas :
R-003
UNIVERSITAS JAMBI
2022
KATA PENGANTAR
Puji syukur atas rahmat Allah SWT, berkat rahmat dan karunia-Nya sehingga laporan
”Makalah Matematika Diskrit Materi Kombinatorial” dapat terselesaikan dengan baik.
Penulisan makalah ini dibuat dengan tujuan memenuhi tugas perkuliahan mata kuliah
Matematika Diskrit. Selain itu, penyusunan makalah ini bertujuan dapat meningkatkan
pemahaman para pembaca. Kami selaku penulis menyampaikan ucapan terima kasih kepada
Ibu Ade Kumalasari, M.Pd dan Ibu Dr. Nizlel Huda, M.Kes. selaku dosen mata kuliah
Matematika Diskrit karena berkat tugas yang diberikan ini, wawasan kami berkaitan dengan
topik yang diberikan dapat bertambah.
Kami menyadari bahwa dalam penyusunan dan penulisan masih terdapat banyak
kesalahan. Oleh karena itu, kami mohon maaf atas kesalahan yang pembaca temukan dalam
laporan ini. Kami juga mengharap adanya kritik serta saran dari pembaca apabila menemukan
kesalahan dalam makalah ini.
Penulis
i
DAFTAR ISI
BAB I ................................................................................................................................... 1
1.1 Latar Belakang .......................................................................................................... 1
1.2. Rumusan Masalah .................................................................................................... 1
1.3 Tujuan ........................................................................................................................ 1
BAB II.................................................................................................................................. 2
2.1 Kaidah Dasar Menghitung. ....................................................................................... 2
2.2. Perluasan Kaidah Menghitung. ................................................................................ 4
2.3. Prinsip Inklusi-Eksklusi ........................................................................................... 5
BAB III ................................................................................................................................ 7
3.1. Kesimpulan ............................................................................................................... 7
3.2. Saran ......................................................................................................................... 7
DAFTAR PUSTAKA .......................................................................................................... 8
ii
BAB I
PENDAHULUAN
1.3 Tujuan
Adapun tujuan dari pembuatan makalah ini adalah sebagai berikut :
1. Untuk mengetahui kaidah dasar menghitung dalam kombinatorial
2. Untuk mengetahui perluasan kaidah menghitung dalam kombinatorial
3. Untuk mengetahui prinsip inklusi-eksklusi dalam kombinatorial
1
BAB II
PEMBAHASAN
Perhatikan kata yang digaris bawahi pada kedua di atas dan serta atau. Kedua kata ini
adalah kata kunci untuk mengidentifikasi apakah suatu persoalan menghitung diselesaikan
dengan kaidah perkalian atau kaidah penjumlahan. Kaidah perkalian menyatakan bahwa kedua
percobaan dilakukan secara simultan atau serempak, sedangkan pada kaidah penjumlahan,
kedua percobaan dilakukan tidak simultan.
Contoh 1
Misalkan himpunan A = (a, b, c, d, e) dan himpunan B = (1, 2, 3). Berapa banyak pasangan
terurut (ordered pairs) yang dapat dibentuk antara anggota himpunan A dengan anggota
himpunan B (yaitu A X B) ?
2
Penyelesaian :
Nyatakan pasangan terurut sebagai (a, b), yang dalam hal ini a € A dan B. Karena anggota
himpunan A yang mungkin menjadi elemen pertama pasangan ada 5 buah dan anggota
himpunan B yang mungkin menjadi elemen kedua pasangan ada 3 buah, maka banyaknya
pasangan yang dapat terbentuk adalah 5 x 3 = 15, yang merupakan jumlah elemen himpunan
hasil operasi A X B (cartesian product).
Contoh 2
Terdapat empat rute yang dapat dilalui kendaraan dari Jakarta ke Bandung dan tiga rute dari
Bandung ke Yogya. Tentukan :
a) Banyak cara seseorang bepergian dengan kendaraan dari Jakarta ke Yoyga melalui
Bandung?
b) Banyak cara seseorang bepergian pulang pergi dengan kendaraan dari Jakarta ke Yogya
melalui Bandung?
Penyelesaian :
a) Seorang dari Jakarta ke Yogya harus melewati rute Jakarta – Bandung dan rute Bandung –
Yogya. Ada 4 pilihan rute dari Jakarta ke Bandung dan 3 pilihan rute dari Bandung ke Yogya,
sehingga jumlah pilihan rute dari Jakarta ke Yogya via Bandung adalah 4 x 3 = 12
b) Ada 12 rute Jakarta ke Yogya via Bandung dan 12 rute dari Yogya ke Jakarta via Bandung.
Karena perjalanan pulang pergi (Jakarta-Yogya dan Yogya-Jakarta), maka jumlah pilihan rute
seluruhnya adalah 12 x 12 = 144 cara untuk berkendaraan pulang pergi.
Contoh 2.3.
Jembatan ketua himpunan diduduki oleh mahasiswa Angkatan tahun 1997 atau Angkatan tahun
1998. Jika terdapat 45 orang mahasiswa Angkatan 1997 dan 52 orang mahasiswa Angkatan
1998, berapa cara memillih penjabat ketua himpunan?
Penyelesaian:
Jabatan yang ditawarkan hanya ada satu, yang dapat diduduki oleh salah seorang mahasiswa
dari dua Angkatan yang ada. Ada 45 cara memilih satu orang mahasiswa dari Angkatan 1997,
dan 52 cara memilih satu orang dari Angkatan 1998, namun hanya satu dari kedua Angkatan
itu yang terpilih (Angkatan 1997 atau Angkatan 1998). Dalam kombinatorial, dari kedua
kejadian, hanya satu dari dua kejadian yang dilakukan, sehingga dengan mengunakan kaidah
3
penjumlahan, jumlah cara memilih penjabat ketua himpunan tersebut sama dengan jumlah
mahasiswa pada kedua Angkatan, yaitu 45 + 52 = 97 cara.
Contoh 2.4
Sekelompok mahasiswa terdiri atas 4 orang pria,dan 3 orang wanita. Berapa jumlah cara
memilih 1 orang yang mewakili kelompok tersebut (tidak peduli pria atau wanita) ?
Penyelesaian:
Ada 4 kemungkinan memilih satu wakil pria,dan tiga kemungkinan memilih satu wakil Wanita,
jika hanya satu orang wakil yang harus dipilih( pria atau Wanita),maka jumlah kemungkinan
wakil yang dapat dipilih adalah 4 + 3 = 7.
Contoh 1 :
Berapa banyak bilangan ganjil antara 1000 dan 999 (yang termasuk 1000 dan 999 itu sendiri)
yang boleh ada angka yang berulang ?
Penyelesaian :
Posisi satuan : 5 kemungkinan angka yaitu (1, 3, 5, 7 dan 9)
Posisi ribuan : 9 kemungkinan angka yaitu (1 sampai 9)
Posisi ratusan : 10 kemungkinan angka yaitu (0 sampai 9)
Posisi puluhan : 10 kemungkinan angka yaitu (0 sampai 9)
Banyak bilangan ganjil seluruhnya : (5) (9) (10) (10) = 4500
Contoh 2
Jika ada sepuluh pertanyaan yang masing-masing bisa dijawab benar atau salah (B atau S),
berapakah kemungkinan kombinasi jawaban yang dapat dibuat ?
4
Penyelesaian :
Andaikan 10 pertanyaan tersebut sebagai 10 buah kotak, masing-masing kotak hanya berisi 2
kemungkinan jawabannya bisa B atau S :
𝐵/𝑆 𝐵/𝑆 𝐵/𝑆 𝐵/𝑆 𝐵/𝑆 𝐵/𝑆 𝐵/𝑆 𝐵/𝑆 𝐵/𝑆 𝐵/𝑆
, , , , , , , , ,
1 2 3 4 5 6 7 8 9 10
Menggunakan kaidah perkalian, karena kesepuluh kotak ini harus terisi dengan jawaban B
atau S (kotak 1, 2, 3, … kotak 10). Maka jumlah kombinasi jawabannya adalah :
(2) (2) (2) (2) (2) (2) (2) (2) (2) (2) = 210
Contoh 1 :
Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte
disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan 2-bit “11” atau berakhir
dengan 2-bit “11”.
Penyelesaian :
Misalkan :
A = Himpunan byte yang dimulai dengan 2-bit “11”.
B = Himpunan byte yang diakhiri dengan 2-bit “11”.
A ∩ B = Himpunan byte yang berawal dan berakhir dengan 2-bit “11”.
Maka :
Jumlah byte yang dimulai dengan 2-bit “11” adalah 26 = 64. 2-bit pertama sudah diisi oleh “11”
sehingga kita cukup mengisi 6 posisi bit sisanya. Oleh karena itu diperoleh :
|𝐴| = 64.
Dengan cara yang sama, diperoleh pula jumlah byte yang 2-bit terakhirnya diisi oleh “11”,
yaitu :
|𝐵| = 64.
5
Jumlah byte dengan 2-bit pertamanya “11” dan 2-bit terakhirnya “11” adalah 24 = 16. 2-bit
pertama dan 2-bit terakhir sudah diisi oleh “11” sehingga kita cukup mengisi 4 posisi bit
sisanya. Oleh karena itu diperoleh :
|A ∩ B| = 16.
Dengan menggunakan prinsip inklusi-eksklusi, maka jumlah byte yang dimulai dengan “11”
atau berakhir dengan “11” adalah sebanyak :
|A ∪ B| = |𝐴| + |𝐵| − |A ∩ B| = 64 + 64 – 16 = 112 buah.
Jadi, jumlah byte yang dimulai dengan “11” atau berakhir dengan “11” ada 112 buah.
6
BAB III
PENUTUP
3.1. Kesimpulan
Adapun kesimpulan yang diperoleh dari makalah ini adalah :
1. Di dalam kombinatorial, kita harus menghitung (counting) semua kemungkinan
pengaturan objek. Dua kaidah dasar yang digunakan sebagai Teknik menghitung dalam
kombinatorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan
(rule of sum).
2. Kaidah perkalian dan penjumlahan diatas dapat diperluas hingga mengandung lebih
dari dua buah percobaan.
3. Prinsip inklusi-eksklusi dapat digunakan untuk menghitung kombinatorial.
3.2. Saran
Penulis menyadari jika dalam penyusunan makalah di atas masih banyak ada kesalahan
serta jauh dari kata sempurna. Adapun nantinya penulis akan segera melakukan perbaikan
susunan makalah itu dengan menggunakan pedoman dari beberapa sumber dan kritik yang bisa
membangun dari para pembaca.
7
DAFTAR PUSTAKA
Munir, R. (2005). Matematika Diskrit. Bandung: Informatika Bandung