Teori Peluang Diskrit — Catatan Kuliah Samaran

Kaidah Dasar Menghitung • Pigeonhole Principle • Permutasi & Kombinasi • Inklusi–Eksklusi • Peluang Diskrit • Catatan Kuliah Samaran • Edisi 1965 • Kaidah Dasar Menghitung • Pigeonhole Principle • Permutasi & Kombinasi • Inklusi–Eksklusi • Peluang Diskrit • Catatan Kuliah Samaran • Edisi 1965 •

Catatan Kuliah Samaran

Teori Peluang Diskrit

Dari menghitung susunan sandi 4-digit, meja makan 8 kursi, sampai mengapa dua orang pasti berulang tahun di kelas 35 siswa — semua dimulai dari satu kaidah sederhana: hitung, bagi, simpulkan.

Subbab 5.1 – 5.5

Contoh Kafe "Karsa" Surakarta

Estimasi ± 45 menit

Prasyarat Pecahan & logika dasar

5.1 Kaidah Dasar 5.2 Pigeonhole 5.3 Permutasi & Kombinasi 5.4 Inklusi–Eksklusi 5.5 Peluang Diskrit Mesin Interaktif

5.1

Subbab Satu · Fondasi

Kaidah Dasar Menghitung — penjumlahan & perkalian

Kafe "Karsa" — contoh pegangan

Sebuah kafe kecil di Solo punya 2 pintu masuk (depan, belakang), 4 meja di teras, dan 3 menu sarapan. Sepanjang bab ini, kita akan kembali ke kafe ini untuk setiap konsep.

Di kafe "Karsa" ada 2 pintu masuk dan 4 meja. Seorang pelanggan harus memilih satu pintu lalu satu meja. Berapa banyak pilihan tempat duduk yang berbeda dimiliki pelanggan? Jawaban cepat: $2 \times 4 = 8$ cara. Tetapi mengapa perkalian, bukan penjumlahan? Itulah inti dari Kaidah Dasar.

Dua prinsip kecil ini — penjumlahan dan perkalian — adalah dua batu bata pertama dari seluruh bangunan kombinatorika. Salah satu menangani pilihan yang saling lepas, satu menangani pilihan yang bertahap. Banyak siswa mencampurnya; bab ini menyelesaikannya.

⸻ ⸻ ⸻

Aturan Penjumlahan

Bila sebuah tugas dapat dilakukan dengan salah satu dari $k$ cara berbeda, dan cara-cara ini saling lepas (tidak tumpang tindih), maka banyak cara total adalah jumlah keduanya.

$n_{\text{total}} = n_1 + n_2 + \cdots + n_k$

Logika: "ATAU" → jumlahkan. Tugas: masuk kafe melalui pintu depan ATAU pintu belakang. Maka $2$ cara. Tidak ada ketergantungan.

Aturan Perkalian

Bila sebuah tugas terdiri dari tahap-tahap berurutan, dan tahap $i$ dapat dilakukan dengan $n_i$ cara tak peduli pilihan tahap sebelumnya, maka banyak cara total adalah perkalian.

$n_{\text{total}} = n_1 \times n_2 \times \cdots \times n_k$

Logika: "LALU" → kalikan. Pintu depan/belakang LALU meja 1–4. Maka $2 \times 4 = 8$.

⸻

Skema Input → Output

Visualisasi sederhana: pelanggan masuk, pilih pintu, pilih meja, dapat kursi.

Pelanggan

1 orang

→

Pilih Pintu

2 cara

Pilih Meja

4 cara

Total

8 cara

Contoh Bertahap — PIN 4 Digit

Berapa banyak kode PIN 4-digit berbeda yang mungkin? Tiap digit boleh 0–9 (sepuluh kemungkinan), dan tiap digit bebas — pilihan pertama tidak memengaruhi pilihan kedua, ketiga, keempat.

Gunakan aturan perkalian, karena pilihan tersusun bertahap (digit 1, lalu digit 2, dst.):

$10 \times 10 \times 10 \times 10 = 10^4 = 10000 \text{ PIN}$

Tahun digital: di dunia nyata bank sering membatasi PIN tidak boleh berulang (misal 1111 dilarang). Itu soal berbeda — bukan aturan dasar, melainkan permutasi di subbab 5.3.

Jawaban Kafe

Pelanggan pilih pintu & meja:

$2 \times 4 = 8$ cara duduk

Jawaban PIN 4-digit

Tiap digit 0–9, bebas berulang:

$10^4 = 10000$ kode

Hati-hati — Jangan Campur

Kunci pembeda: ATAU (pilihan lepas, biasanya hanya satu yang terjadi) → jumlahkan. LALU (pilihan berurutan, semua terjadi) → kalikan. Kalau ragu, tanyakan: "Apakah pilihan kedua terjadi setelah pilihan pertama?"

Mesin 01 · Kalkulator Bertahap

Geser tiap slider untuk menghitung banyak cara bertahap. Aturan perkalian berlaku: tiap tahap bebas, hasilnya perkalian seluruh tahap.

TAHAP 1 2

TAHAP 2 4

TAHAP 3 3

HASIL = 24

Lanjut ke 5.2 — Pigeonhole →

5.2

Subbab Dua · Eksistensi

Prinsip Sarang Burung Merpati — Pigeonhole Principle

Jika banyak burung melebihi banyak sarang…

…maka pasti ada sarang yang berisi minimal dua burung. Prinsip ini sederhana, tetapi koneksi ke teori peluang & ilmu komputer sangat dalam.

Kafe "Karsa" punya 7 kursi. Pada suatu Senin pagi datang 8 pelanggan serempak. Pertanyaan: apakah mungkin setiap kursi hanya berisi satu orang? Tentu tidak — ada 8 orang untuk 7 kursi, jadi paling tidak satu kursi harus berisi dua orang. Inilah inti Pigeonhole.

Prinsip ini hanya menjamin keberadaan, bukan menunjukkan sarang mana. Ini menjadi alat bukti yang kuat di kombinatorika, teori bilangan, dan ilmu komputer.

⸻ ⸻ ⸻

Rumus Umum Pigeonhole

Bentuk Dasar

$$\text{Jika } n > m, \text{ dan } n \text{ objek dimasukkan ke } m \text{ wadah,}$$ $$\text{maka paling tidak satu wadah berisi } \geq 2 \text{ objek.}$$

Asal-usul logis: jika tiap wadah maksimal berisi 1 objek, total maksimal $= m$. Karena $n > m$, terjadi kontradiksi. Maka minimal satu wadah berisi $\geq 2$.

Bentuk Lebih Umum

Pigeonhole dengan $k$-lebih

$$\text{Jika } n \text{ objek dimasukkan ke } m \text{ wadah,}$$ $$\text{maka paling tidak satu wadah berisi } \geq \left\lceil \frac{n}{m} \right\rceil \text{ objek.}$$

Lambang $\lceil \cdot \rceil$ adalah fungsi pembulatan ke atas (ceiling). Contoh: $\lceil 8/7 \rceil = \lceil 1.14 \rceil = 2$, sehingga paling tidak satu kursi berisi 2 orang.

Mesin 02 · Pigeonhole Simulator

Atur banyak burung (pelanggan) dan sarang (kursi). Mesin akan mendistribusikan burung secara merata dan menyorot sarang yang wajib berisi lebih dari satu.

BURUNG (n) 8

SARANG (m) 7

Bukti: paling tidak satu sarang berisi ≥ 2 burung

Benar

Kelas 36 siswa, hari dalam setahun ada 365. Karena $366 > 365$, pasti ada dua siswa berulang tahun di hari yang sama. Ini tidak menjamin siapa — hanya keberadaan.

Salah

"Berapa peluang dua orang di kelas berulang tahun sama?" — itu soal peluang (subbab 5.5), bukan Pigeonhole. Pigeonhole hanya bicara kepastian, bukan kemungkinan.

Kombinatorika adalah seni menghitung yang tak terhitung; prinsip sarang merpati adalah seni membuktikan yang tak terlihat.

— Catatan Dosen Tua, halaman 47

Contoh Klasik — 13 Orang, 12 Bulan

Di suatu ruangan ada 13 orang. Apakah pasti ada dua orang yang lahir di bulan yang sama? Bulan hanya 12. Karena $13 > 12$, jawabannya: ya, pasti. Tidak peduli bulan apa — Pigeonhole hanya menjamin keberadaan.

$n = 13, \; m = 12 \;\Rightarrow\; \left\lceil \frac{13}{12} \right\rceil = 2$

Lanjut ke 5.3 — Permutasi & Kombinasi →

5.3

Subbab Tiga · Susunan

Permutasi & Kombinasi — urutan vs tidak

Apa beda AB dan BA?

Bab inti kombinatorika. Kafe "Karsa" punya 4 staf: Ani, Budi, Cici, Dono. Berapa cara menyusun jadwal shift pagi & sore?

Kita ingin menyusun 2 dari 4 staf untuk dua shift (pagi, sore). Pertanyaannya: apakah urutan penting? Ani pagi, Budi sore berbeda dengan Budi pagi, Ani sore — ya, jelas berbeda. Maka ini soal permutasi.

Tetapi kalau kita hanya ingin memilih 2 dari 4 untuk hadiah (tanpa urutan), maka pasangan $\{A,B\}$ sama dengan $\{B,A\}$. Ini soal kombinasi. Pembeda tunggal: apakah urutan memengaruhi makna?

⸻ ⸻ ⸻

Rumus Inti · Permutasi

Banyak susunan r objek dari n objek berbeda

$$P(n,r) = \frac{n!}{(n-r)!}$$

Asal-usul: aturan perkalian bertahap. Pilih objek pertama: $n$ cara. Kedua: $n-1$ (satu sudah terpakai). Ketiga: $n-2$. Sampai ke-$r$: $n-r+1$. Total: $n(n-1)(n-2)\cdots(n-r+1)$. Ditulis ulang jadi $\frac{n!}{(n-r)!}$.

Rumus Inti · Kombinasi

Banyak pilihan r objek dari n (tanpa urutan)

$$C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$$

Asal-usul: dari permutasi, bagi dengan banyak susunan internal $r$ objek terpilih (yang jumlahnya $r!$). Sebab $r$ objek dapat disusun ulang dalam $r!$ cara tanpa mengubah "isi" himpunan. Maka $C(n,r) = \frac{P(n,r)}{r!}$.

⸻

Permutasi — Jadwal Shift

4 staf (A,B,C,D), pilih 2 untuk shift pagi & sore. Urutan penting.

$P(4,2) = \frac{4!}{(4-2)!} = \frac{24}{2} = 12$ cara

Sebut: (A,B), (A,C), (A,D), (B,A), (B,C), (B,D), (C,A), (C,B), (C,D), (D,A), (D,B), (D,C) — genap 12.

Kombinasi — Pilih Hadiah

4 staf, pilih 2 untuk dapat bonus. Urutan tidak penting.

$C(4,2) = \binom{4}{2} = \frac{4!}{2!\,2!} = 6$ pasangan

Sebut: {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D} — genap 6. Setengah dari permutasi: wajar, sebab tiap pasangan dapat disusun dalam 2 urutan.

Hubungan Penting

Permutasi & kombinasi terkait:

$P(n,r) = r! \times C(n,r)$

Mesin 03 · Permutasi vs Kombinasi

n (total objek) 4

r (dipilih) 2

P(n,r) = 12

C(n,r) = 6

Catatan: jika r > n, hasil dianggap 0 — tidak mungkin memilih lebih banyak dari yang tersedia.

Tabel Ringkas — Simbol

Simbol	Nama	Makna	Contoh
$n!$	Faktorial n	$n \times (n-1) \times \cdots \times 1$	$4! = 24$
$P(n,r)$ atau ${}_nP_r$	Permutasi	Susunan berurutan r dari n	$P(4,2)=12$
$C(n,r)$ atau $\binom{n}{r}$	Kombinasi	Pilihan tanpa urutan r dari n	$C(4,2)=6$
$0!$	Faktorial nol	Konvensi: $0! = 1$ (agar rumus konsisten)	$0! = 1$

Pakai Permutasi jika

Urutan hasil memengaruhi makna: posisi, peringkat, jadwal, kode sandi, susunan kata, antrian.

Pakai Kombinasi jika

Urutan tidak memengaruhi makna: anggota tim, pasangan, pilihan menu, undian, kartu tangan.

Lanjut ke 5.4 — Inklusi–Eksklusi →

5.4

Subbab Empat · Irisan

Prinsip Inklusi–Eksklusi — hitung, kurangi, tambah

Kafe "Karsa" — survei pelanggan

Survei 100 pelanggan: 60 suka kopi, 50 suka teh, 25 suka keduanya. Berapa pelanggan yang suka salah satu (atau keduanya)?

Jika kita jumlahkan $60 + 50 = 110$, hasilnya lebih besar dari 100 — jelas salah, sebab 25 pelanggan yang suka keduanya terhitung dua kali (sekali di kelompok kopi, sekali di kelompok teh). Prinsip Inklusi–Eksklusi (PIE) memperbaikinya: jumlahkan, lalu kurangi irisan yang terhitung ganda.

Jawaban sebenarnya: $60 + 50 - 25 = 85$ pelanggan suka kopi atau teh (atau keduanya). Sisanya, $100 - 85 = 15$, tidak suka keduanya.

⸻ ⸻ ⸻

PIE · Dua Himpunan

Identitas Irisan untuk $|A \cup B|$

$$|A \cup B| = |A| + |B| - |A \cap B|$$

Asal-usul logis: saat menjumlahkan $|A| + |B|$, elemen di $A \cap B$ dihitung dua kali. Kurangi sekali agar tepat satu perhitungan.

PIE · Tiga Himpunan

Identitas Irisan untuk $|A \cup B \cup C|$

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

Asal-usul: pola selang-seling — tambah, kurangi, tambah. Irisan dua himpuna dikurangi karena terhitung tiga kali (sudah masuk tanda +, tapi sebenarnya hanya boleh sekali). Irisan tiga dikurangi terlalu banyak, jadi ditambah kembali. Pola ini berlanjut ke $n$ himpunan.

Mesin 04 · Diagram Venn Survei Kafe

Atur banyak pelanggan di tiga kategori: Kopi, Teh, Camilan. Mesin menghitung $|A \cup B \cup C|$ dengan PIE. Klik region pada Venn untuk menyorot area.

A — KOPI 60

B — TEH 50

C — CAMILAN 40

|A∪B∪C| = 95

Penerapan pada Kafe "Karsa"

$|A \cup B| = 60 + 50 - 25 = 85 \text{ pelanggan.}$

Jika total pelanggan disurvei 100, maka $100 - 85 = 15$ pelanggan tidak suka kopi maupun teh.

Simbol	Makna	Operasi pada PIE
$\|A\|$	Banyak elemen himpunan A	+ (tambah)
$\|A \cap B\|$	Irisan A dan B	− (kurangi)
$\|A \cap B \cap C\|$	Irisan ketiganya	+ (tambah balik)
$\|A \cup B \cup C\|$	Gabungan	Hasil akhir

Lanjut ke 5.5 — Peluang Diskrit →

5.5

Subbab Lima · Peluang

Peluang Diskrit & Bersyarat — kemungkinan terjadi

Kafe "Karsa" — undian mingguan

Setiap Sabtu, kafe mengundi 1 gelas dari 8 gelas (6 di antaranya berisi kopi, 2 teh). Peluang seorang pelanggan dapat teh? $\tfrac{2}{8} = \tfrac{1}{4}$.

Peluang adalah rasio antara banyaknya hasil yang diinginkan dengan banyaknya seluruh hasil yang mungkin. Konsep ini menyatukan seluruh bab sebelumnya: aturan perkalian, permutasi, kombinasi, dan PIE, semuanya menjadi alat untuk menghitung angka di pembilang dan penyebut.

Catatan penting: di peluang diskrit, ruang sampel berhingga atau terhitung — dadu, koin, kartu, undian, kursi. Kebalikannya, peluang kontinus (yang menangani tinggi badan, suhu, waktu) memakai integral, di luar lingkup bab ini.

⸻ ⸻ ⸻

Definisi Klasik · Peluang

Ruang Sampel & Kejadian

$$P(E) = \frac{|E|}{|S|} = \frac{\text{banyak hasil yang diinginkan}}{\text{banyak seluruh hasil mungkin}}$$

Syarat: semua hasil di $S$ equiprobable (sama mungkinnya). Inilah sebabnya kita harus berhati-hati: dadu beresi tidak memenuhi syarat ini, jadi definisi klasik tidak berlaku begitu saja.

Definisi · Peluang Bersyarat

Peluang $E$ jika $F$ sudah terjadi

$$P(E \mid F) = \frac{P(E \cap F)}{P(F)} \;,\quad P(F) > 0$$

Asal-usul: Begitu $F$ terjadi, ruang sampel kita "menyempit" menjadi $F$ saja. Di ruang baru ini, kejadian $E$ hanya berlaku untuk bagian $E \cap F$. Pembilang diubah ke $|E \cap F|$, penyebut ke $|F|$.

⸻

Mesin 05 · Simulasi Lempar Dadu

Lihat empirik vs teoritis. Tiap klik tombol "Lempar" menambahkan 1 lemparan dadu dan menghitung peluang empirik tiap sisi. Bandingkan dengan nilai teoritis $\tfrac{1}{6}$.

1
0%

2
0%

3
0%

4
0%

5
0%

6
0%

Lemparan terakhir: — Total: 0

Nilai teoritis = 16,67% tiap sisi

Peluang Kopi

8 gelas, 6 berisi kopi:

$P(K) = \frac{6}{8} = \frac{3}{4}$

Peluang Teh Bersyarat

Jika sudah tahu bukan kopi (2 gelas tersisa), peluang teh:

$P(T \mid \neg K) = \frac{2}{2} = 1$

Teorema Penting

T1
Komplementer: $P(E^c) = 1 - P(E)$. Peluang tidak kejadian = 1 dikurangi peluang kejadian.
Asal: total peluang ruang sampel = 1, dan $E$ dengan $E^c$ saling lepas dan menyelimuti $S$.
T2
Aturan Penjumlahan Peluang: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$.
Saudara kembar PIE — sebab peluang adalah ukuran, dan irisan terhitung dua kali.
T3
Independensi: $A$ dan $B$ independen $\iff P(A \cap B) = P(A) \cdot P(B)$.
Artinya: mengetahui $A$ terjadi tidak mengubah peluang $B$. Contoh: dua dadu dilempar terpisah.
T4
Aturan Perkalian: $P(A \cap B) = P(B) \cdot P(A \mid B)$.
Karena $P(A \mid B) = P(A \cap B)/P(B)$, cukup kalikan balik.

Contoh Pegangan — Undian Bersyarat

Kafe "Karsa" punya 8 gelas: 6 kopi, 2 teh. Pelanggan pertama ambil 1 gelas tanpa mengembalikan, lalu pelanggan kedua ambil 1 gelas.

(a) Peluang pelanggan kedua dapat teh, jika pelanggan pertama dapat kopi?

Setelah pelanggan pertama ambil kopi, tersisa 7 gelas: 5 kopi, 2 teh. Maka:

$P(T_2 \mid K_1) = \frac{2}{7} \approx 0{,}286$

(b) Peluang keduanya dapat teh?

Peluang pertama dapat teh = $\frac{2}{8}$. Lalu peluang kedua dapat teh (jika pertama teh) = $\frac{1}{7}$. Gunakan aturan perkalian:

$P(T_1 \cap T_2) = P(T_1) \cdot P(T_2 \mid T_1) = \frac{2}{8} \times \frac{1}{7} = \frac{2}{56} = \frac{1}{28}$

Catatan: ini bukan independensi. Karena pengambilan tanpa pengembalian, kejadian pertama mempengaruhi peluang kedua.

Peluang bukan tentang meramal masa depan — ia adalah disiplin mengakui ketidakpastian dengan cara yang terukur.

— Catatan Kuliah Samaran, halaman 92

Lanjut ke Laboratorium →

★

Laboratorium · Mesin Kombinatorika

Mesin Pengatur Kursi — visualisasi langsung

Berikut mesin interaktif yang menyatukan seluruh konsep: aturan perkalian (banyak cara menyusun), permutasi (susunan kursi), dan peluang (menghitung konfigurasi yang memenuhi syarat). Atur slider, klik "Jalankan", dan saksikan kursi tersusun secara langsung.

Mesin 06 · Pengatur Kursi Kafe

JUMLAH KURSI 5

URUTAN DITAMPILKAN 1

Konfigurasi saat ini

P(n,n) = 120

Susunan # 1 dari 120

↑ Kembali ke awal