Belajar Matematika Diskrit Live #8

Teori Pencacahen (counting theory)

Teori pencacahan adalah bagian dari matematika diskrit yang membahasa bagaimana cara berhitung dalam jumlah kemungkinan atau cara menyusun object-object diskrit tanpa harus kita baca satu persatu.

ada sebanyak 2 prisip fondasi yang ada di counting theory

Rule of sum (aturan dalam penjumlahan)

Prinsip utama dalam rule of sum, jika ada 2 kejadian yang saling ekslusif (tidak bisa terjadi secara bersamaan) jumlah total cara sama dengan jumlah total cara pertama ditambah jumlah cara kedua

Jika terdapat n cara untuk melakukan suatu tindakan pertama, dan m cara untuk melakukan tindakan kedua, dan kedua tindakan tersebut tidak dapat dilakukan pada saat yang bersamaan (saling lepas atau mutually exclusive), maka total cara untuk memilih salah satu dari tindakan tersebut adalah n + m cara. 

Contoh: saat makan singa ada nasi goreng terdapat pada 3 warung atau mie ayam terdapat pada 4 warung tapi kita hanya bisa memilih satu, total pilihan tempat makan siang nya berarti 3 + 4 = 7 tempat

Rule of product (aturan dalam perkalian)

jika ada 2 kejadian yang terjadi secara berurutan, dan saling independen total cara nya ini sama dengan cara kejadian pertama dikali kejadian kedua

Prinsip ini menyatakan bahwa jika suatu tugas dapat diselesaikan dalam a cara, dan setelah tugas pertama selesai, tugas kedua dapat diselesaikan dalam b cara, maka kedua tugas tersebut dapat diselesaikan secara berurutan dalam a x b cara yang berbeda.

Contoh: saat memakai outfit terdapat 3 kemeja dan 2 celana jadi kombinasinya adalah 3 x 2 = 6 kombinasi

Jantung dari counting theory

INI WAJIB PAHAM

1. permutasi (permutation)

adalah konsep dimana kita menghitung jumlah cara menyusun object dengan memperhatikan sebuah urutan

Rumus Permutasi:
n -> object
r -> object
P(n, r) = n! / (n - r)!

Rumus permutasi adalah \(P(n,r)=\frac{n!}{(n-r)!}\) yang digunakan untuk menghitung banyaknya cara menyusun 'r' objek dari himpunan 'n' objek berbeda ketika urutan menjadi penting

Contoh: punya 5 microservice -> A, B, C, D, E
deploy 3 dari 5 microservice dengan urutan yang penting. A dulu, baru si B, baru C.
jumlah caranya: P(5, 3) = 5 x 4 x 3 = 60 cara.

Langkah 1: Mengidentifikasi variabel Dalam kasus ini:
 Total microservice yang Anda miliki adalah \(n=5\) (A, B, C, D, E).
Jumlah microservice yang akan di-deploy adalah \(r=3\).
 Langkah 2: Menggunakan rumus permutasi Rumus permutasi adalah:
\(P(n,r)=\frac{n!}{(n-r)!}\)
Substitusikan nilai \(n=5\) dan \(r=3\) ke dalam rumus:
\(P(5,3)=\frac{5!}{(5-3)!}\)
Langkah 3: Melakukan perhitungan Pertama, hitung bagian dalam kurung:
\((5-3)!=2!\).\(P(5,3)=\frac{5!}{2!}\)
Selanjutnya, jabarkan nilai faktorialnya:
\(P(5,3)=\frac{5\times 4\times 3\times 2\times 1}{2\times 1}\)
Langkah 4: Menyederhanakan dan menemukan jawaban Anda dapat menyederhanakan perhitungan dengan mencoret angka yang sama di pembilang dan penyebut.
\(P(5,3)=\frac{5\times 4\times 3\times \cancel{2\times 1}}{\cancel{2\times 1}}\)
Hasilnya adalah:\(P(5,3)=5\times 4\times 3\)
Jawaban: Hasil akhir dari perhitungan tersebut adalah:
\(5\times 4\times 3=\mathbf{60}\)

Tambahan: Perhitungan permutasi untuk kata "BANANA" disebut permutasi dengan unsur berulang atau permutasi multiset.
Hal ini karena kata tersebut memiliki beberapa huruf yang sama atau berulang. 
Berikut adalah cara menghitungnya: Rumus Rumus yang digunakan untuk permutasi dengan unsur berulang adalah: 
\(P=\frac{n!}{n_{1}!n_{2}!\dots n_{k}!}\)
Di mana: \(n\) adalah jumlah total objek (huruf).
\(n_{1},n_{2},\dots ,n_{k}\) adalah jumlah kemunculan setiap objek (huruf) yang berulang.
 Perhitungan untuk kata "BANANA" Identifikasi jumlah total huruf (\(n\)):
Kata "BANANA" terdiri dari 6 huruf, jadi \(n=6\).
Identifikasi huruf yang berulang dan jumlah kemunculannya:
Huruf 'B' muncul 1 kali (\(n_{1}=1\)).
Huruf 'A' muncul 3 kali (\(n_{2}=3\)).
Huruf 'N' muncul 2 kali (\(n_{3}=2\)).
Terapkan rumus:\(P=\frac{6!}{1!\times 3!\times 2!}\)
Hitung nilai faktorialnya:\(6!=6\times 5\times 4\times 3\times 2\times 1=720\)
\(1!=1\)
\(3!=3\times 2\times 1=6\)
\(2!=2\times 1=2\)
Selesaikan perhitungan:\(P=\frac{720}{1\times 6\times 2}=\frac{720}{12}=60\) 
Jadi, terdapat 60 cara berbeda (unik) untuk menyusun huruf-huruf dalam kata "BANANA".

2. kombinasi (combination)

kombinasi adalah menghitung jumlah cara dalam memilih object tanpa memperhatikan urutan

Rumus kombinasi:
n -> object
r -> object
C(n, r) = n! / (r! x (n-r)!)

Contoh: kita pilih 2 dari 5 teman untuk main bareng, gak peduli siapa duluan yang kita pilih

jumlah caranya: C(5, 2) = 10 cara.

Soal: Memilih 2 teman dari total 5 teman, tanpa memperhatikan urutan.
 n = jumlah total teman = 5
r = jumlah teman yang dipilih = 2
 Rumus:\(C(n,r)=\frac{n!}{r!(n-r)!}\)
Langkah 1: Substitusikan nilai n dan r
Masukkan nilai \(n=5\) dan \(r=2\) ke dalam rumus:
\(C(5,2)=\frac{5!}{2!(5-2)!}\)
Langkah 2: Masukkan kembali ke rumus dan coret Gantikan \(5!\) dengan uraiannya di dalam rumus: 
\(C(5,2)=\frac{5\times 4\times \cancel{3!}}{2!\times \cancel{3!}}\)
Langkah 3: Lakukan perhitungan sisa Rumusnya menjadi jauh lebih sederhana:
 \(C(5,2)=\frac{5\times 4}{2!}\)
Hitung nilai \(2!=2\times 1=2\):
 \(C(5,2)=\frac{20}{2}\)
Hasil Akhir: \(C(5,2)=10\)

Soal:
1. kamu ngadain meeting zoom dengan 5 enginer, mereka duduk melingkar di meja virtual (posisi relatif penting, tapi rotasi sama). Ada berapa banyak cara mereka "duduk"?
2. kamu ada 10 dev dalam tim, kamu harus pilih 4 orang buat ikut lomba, tapi idris dan si abulucu gak mau ikut bareng (paling tidak salah satu dari mereka tidak boleh ikut). Berapa banyak dalam memilih timnya?
penyelesaian:
1. A-B-C-D-E-A = B-C-D-E-A
jumlah cara penyusunan yang berbeda: (n - 1)!
n = 5
(5 - 1)! = 4! = 24
2. jumlah cara memilih 4 dari 10 orang: C(n, r) = n! / (r! x (n-r)!)
n = 10 dev, r = 4,
C(10,4) = 10! / 4!(10-4)! = 10! / 4! x 6! = 210
kasus terlarang (Idris dan abulucu terpilih semua)
C(8,2) = 8! / 2!(8-2)! = 8! / 2! x 6! = 28
total = semua kemungkinan - kasus terlarang = 210 - 28 = 182