Matematika Diskrit : Prinsip Inklusi-Ekslusi, Permutasi, Kombinasi, dan Contoh Soal
Prinsip Inklusi - Eksklusi
Misalkan A dan B yaitu himpunan berhingga yang saling lepas (disjoint), maka
Misalkan A dan B yaitu himpunan berhingga, maka
berhingga dan
Misalkan A, B, dan C yaitu himpunan berhingga, maka
berhingga dan
Misalkan A dan B yaitu himpunan berhingga, maka
Misalkan A, B, dan C yaitu himpunan berhingga, maka
berhingga dan
Contoh :
Informasi terkecil di memori komputer disimpan dalam byte. 1 byte = 8-bit (0 atau 1). Berapa banyaknya byte yang diawali dengan ‘11’ atau diakhiri dengan ‘11’?
A = himpunan byte yang diawali dengan ‘11’
B = himpunan byte yang diakhiri dengan ‘11’
= himpunan byte yang diawali dan diakhiri dengan ‘11’
Akan ditentukan
Akan ditentukan |A|
Akan ditentukan |B|
Akan ditentukan
Maka
Latihan 1
Berapa banyak nomor polisi kendaraan beroda empat yang mungkin, yang diawali dengan 2 aksara dan diikuti dengan 4 angka, dengan aksara pertama B atau angka terakhir 3? Asumsikan semua aksara sanggup dipakai pada nomor polisi.
Latihan 2
Permutasi
Permutasi yaitu banyaknya urutan berbeda dari pengaturan objek-objek. Misalkan ada n objek, maka banyaknya urutan yang mungkin yang sanggup dibentuk, atau permutasi n dari n objek yaitu :
Contoh :
Berapa banyak “kata” yang sanggup dibuat dari kata “BOSAN”?
Maka banyak “kata” yang sanggup dibuat :
P(5,5)= 5.4.3.2.1 = 5! = 120 kata
Latihan 3
Tiga buah bola dengan warna merah, kuning, dan hijau akan dimasukkan ke dalam 3 buah kotak. Berapa banyak urutan berbeda yang sanggup dibuat dari penempatan bola ke dalam kotak? Apa saja urutan tersebut ?
Permutasi r dari n objek berbeda P(n,r) yaitu jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek,
Contoh :
Enam buah bola berwarna merah, kuning, hijau, biru, ungu, dan hitam akan dimasukkan ke dalam 3 buah kotak. Berapa banyak urutan yang mungkin dari penempatan bola ke dalam kotak?
Latihan 4
Berapa banyak bilangan terdiri atas 4 angka yang sanggup dibuat dari 1,2,3,4,5,6,7,8?
Permutasi Melingkar
Permutasi melingkar dari n objek yaitu penyusunan objek-objek yang mengelilingi sebuah lingkaran. Banyaknya susunan objek yang mengelilingi lingkaran yaitu (n-1)!
Contoh :
Ada 5 mahasiswa yang duduk di sebuah meja bundar. Berapa banyaknya susunan duduk mahasiswa tersebut?
(n-1)! = (5-1)! = 4! = 4.3.2.1 = 24 susunan
Permutasi Bentuk Umum
Jika ada n bola yang tidak semuanya berbeda warna.
Misalnya :
n1 bola berwarna merah
n2 bola berwarna hijau
…
nk bola berwarna kuning
maka permutasi n bola ini dirumuskan sebagai berikut :
Contoh :
Berapa banyak “kata” atau string yang sanggup dibuat dari huruf-huruf pada kata MISSISSIPPI?
S = {M, I, S, S, I, S, S, I, P, P, I}
- Huruf M = 1 buah (n1)
- Huruf I = 4 buah (n2)
- Huruf S = 4 buah (n3)
- Huruf P = 2 buah (n4)
n = 1 + 4 + 4 + 2 = 11 buah
Maka :
Latihan 5
Sepuluh lembar kertas akan diwarnai dengan sebagai berikut :
3 lembar dengan warna merah,
4 lembar dengan warna hijau, dan
3 lembar dengan warna kuning.
Berapa banyaknya cara pewarnaan ?
3 lembar dengan warna merah,
4 lembar dengan warna hijau, dan
3 lembar dengan warna kuning.
Berapa banyaknya cara pewarnaan ?
Kombinasi
Kombinasi r elemen dari n elemen yaitu banyaknya pemilihan yang tidak terurut r elemen yang diambil dari n elemen.
Notasi
Dengan
Contoh 1 :
Berapa banyaknya himpunan bab dari A = {1,2,3,4,5} yang terdiri atas 3 elemen?
Jadi banyaknya himpunan bab dari A yang beranggotakan 3 elemen yaitu 10 buah, yaitu:
{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}
Contoh 2 :
Di antara 10 mahasiswa Teknik Informatika angkatan 2010, berapa banyaknya cara membentuk perwakilan yang beranggotakan 5 orang ?
Jadi ada 252 cara untuk membentuk perwakilan beranggotakan 5 orang yang diambil dari 10 orang.
Contoh 3:
Salah satu mahasiswa dari 10 mahasiswa tersebut yaitu Adi. Berapa banyaknya cara membentuk perwakilan yang terdiri atas 5 orang sedemikian sehingga Adi selalu menjadi bab dari perwakilan?
Karena Adi diasumsikan selalu terpilih, maka tinggal 4 orang anggota yang harus dipilih dari 9 orang.
Contoh 4 :
Terdapat 5 mahasiswi dan 3 mahasiswa. Berapa banyak cara membentuk kelompok yang terdiri atas 2 mahasiswi dan 2 mahasiswa?
Banyaknya cara menentukan 2 mahasiswi dari 5 mahasiswi yaitu C(5,2) = 10 cara.
Banyaknya cara menentukan 2 mahasiswa dari 3 mahasiswa yaitu C(3,2) = 3 cara
Maka banyaknya cara menentukan 2 mahasiswi dan 2 mahasiswa yaitu C(5,2).C(3,2)=10.3=30 cara.
Latihan 6
Ada 7 orang mahasiswa dari Jurusan Matematika dan 8 orang mahasiswa jurusan Informatika. Akan dibuat kelompok beranggotakan 4 orang. Bagaimana cara membentuk kelompok jikalau banyaknya mahasiswa jurusan Matematika yang terpilih harus sama dengan banyaknya mahasiswa jurusan Informatika ?
Kombinasi Bentuk Umum
Jika ada n bola yang tidak semuanya berbeda warna.
Misalnya :
n1 bola berwarna merah
n2 bola berwarna hijau
…
nk bola berwarna kuning
maka kombinasi n bola ini dirumuskan sebagai berikut :
Contoh :
Terdapat 8 buah buku. Bagaimana cara membagi buku sehingga A akan menerima 4 buku, B menerima 2 buku, dan C menerima 2 buku?
Kombinasi dengan Pengulangan
Banyaknya kombinasi dari r buah objek yang diambil dari n buah objek dimana pengulangan diperbolehkan yaitu C(n+r-1,r).
Contoh 1 :
Akan dibagikan 10 jeruk kepada 3 orang anak sedemikian sehingga setiap anak boleh menerima lebih dari 1 jeruk. Berapa banyaknya cara pembagian ini?
n = 3, r = 10
Banyaknya cara pembagian yaitu C(3+10-1,10) = C(12,10)
Contoh 2 :
Terdapat kumpulan bola berwarna merah, hijau, kuning. Banyaknya masing-masing bola setidaknya 8 buah. Berapa banyak cara menentukan 8 buah bola jikalau paling sedikit 1 bola dari masing-masing warna terpilih ?
Diketahui n = 3 dan r = 8.
Karena setidaknya 1 bola dari masing-masing warna harus terpilih, maka tinggal 5 bola yang harus dipilih.
Maka cara menentukan 5 bola ini yaitu C(3+5-1,5)=C(7,5)
Latihan 7
Dari sejumlah besar CD berisi aktivitas aplikasi A, B, C, D, dan E, berapa banyak cara 10 CD sanggup diambil ?
EmoticonEmoticon