Muqodimah Kombinatorika dan Kaidah Pencacahan

"Combinatorics is an art of counting without counting", terjemah:

"Kombinatorika adalah seni menghitung (berapa banyak) tanpa menghitung (satu per satu)"

Kombinatorika merupakan cabang matematika yang mempelajari tentang pengaturan objek-objek, didasarkan pada hasil yang diperoleh melalui percobaan (proses fisik yang hasilnya dapat diamati). 

Solusi yang ingin dicapai dalam kombinatorika adalah jumlah cara pengaturan objek-objek tertentu dalam himpunannya.

1. Kaidah Penjumlahan

kata kunci untuk kaidah penjumlahan adalah "atau"

A. Kejadian saling asing

Misalkan kejadian A dapat dilakukan dengan m cara dan kejadian B dapat dilakukan dengan n cara, Jika kejadian A dan B kejadian yang saling asing (tidak mungkin terjadi bersamaan), maka banyaknya cara kejadian A atau B adalah m + n cara.

Ingat kembali bahwa n(A ∪ B) = n(A) + n(B) untuk A dan B yang memenuhi A ∩ B = ∅.

contoh:

Di dalam sebuah kotak terdapat 3 bola merah, 4 bola biru, dan 5 bola hitam, dengan semua bola berwarna tunggal. Berapa banyak bola yang berwarna merah atau biru?

Karena semua bola berwarna tunggal, tidak ada bola yang berwarna merah dan biru sekaligus, sehingga keduanya saling asing, banyak bola merah atau biru adalah 3 + 4 = 7.

B. Kejadian tidak saling asing

Ingat kembali bahwa n(A ∪ B) = n(A) + n(B) − n(A ∩ B).

contoh:

Ada berapa cara memilih sebuah kartu As atau kartu merah dari setumpuk kartu resmi?

Jawab: 

Banyak cara memilih kartu As : 4 cara

Banyak cara memilih kartu merah : 26 cara

Tapi ada 2 kartu yang merupakan kartu As sekaligus berwarna merah, yang jika langsung dijumlahkan 4 + 26 akan ada dua kartu yang dihitung dua kali yaitu As hati dan As wajik sehingga harus dikurangi dengan 2.

Jadi banyak cara memilih kartu As atau merah adalah 4 + 26 − 2 = 28 cara

2. Kaidah Perkalian

Misalkan kejadian C dapat dipecah menjadi dua tahap A dan B, di mana A dpt terjadi sebanyak m cara dan B dapat terjadi sebanyak n cara. Dengan syarat B terjadi tanpa dipengaruhi hasil dari A, maka C dapat terjadi sebanyak  m × n cara.

Misalkan ada n tempat tersedia dengan k₁ adalah banyaknya cara mengisi tempat pertama, k₂ adalah banyaknya cara mengisi tempat kedua, dan seterusnya hingga k_n adalah banyaknya cara mengisi tempat ke-n. Maka banyaknya cara mengisi tempat adalah k₁ × k₂ × ⋅⋅⋅ × k_n. 

Cara ini disebut sebagai aturan pengisian tempat dan sering disebut dengan kaidah perkalian.

contoh:

1. Misalkan dari kota A ke kota B ada tiga bus dengan jalur berbeda, dari B ke C ada dua bus dengan jalur berbeda. Ada berapa cara kita pergi dari A ke C? 3 × 2 = 6 cara.

2. Misalkan dari kota A ke kota B ada 5 bus dengan jalur berbeda, dari B ke C ada 4 bus dengan jalur berbeda dan 3 bus dari A ke C langsung. Ada berapa cara kita pergi dari A ke C dan kembali ke A dengan syarat tidak boleh menggunakan bus yang sama lebih dari sekali?

a) Berangkat lewat B

Banyak Cara Berangkat = 5 × 4 = 20 cara

Banyak cara pulang = - lewat B: 3 × 4 =12, ATAU 

                                    - langsung ke A = 3

Banyak cara pulang= 12 + 3 =15 cara

Banyak cara pergi pulang = 20 × 15 = 300

b) Berangkat tidak lewat B, langsung ke C

Banyak cara berangkat = 3

Banyak cara pulang = - lewat B: 4 × 5 = 20, ATAU 

                                    - langsung ke A = 2

Banyak cara pulang = 20 + 2 = 22

Banyak cara pergi pulang = 3 × 22 = 66

Banyak cara perjalanan = 300 + 66 = 366 cara.

3. Faktorial (Diskrit)

Misal suatu bilangan asli n. Faktorial dari n, ditulis n!, adalah perkalian mundur dari n sampai 1.

0! = 1

1! = 1

2! = 2 × 1 = 2

3! = 3 × 2 × 1 = 6

...

n! = n × (n − 1) × (n − 2) × ... × 2 × 1

Dalam bentuk rekursif, kita dapat menuliskan:

n! = n(n − 1)! = n(n − 1)(n − 2)! = n(n − 1)(n − 2)(n − 3)!, dan seterusnya.

Secara umum, hasil faktorial dari n menyatakan banyaknya kemungkinan susunan n elemen berbeda tanpa aturan tambahan.

contoh:

Banyaknya susunan dari a, b, c, d, e, f adalah 6 × 5 × 4 × 3 × 2 × 1 = 720.

4. Faktorial (Kontinu)

Misal didefinisikan suatu fungsi

masukkan n = 0 ke fungsi ini, dan diperoleh

nilai f(0) adalah 1.
Misal dilakukan integral parsial

u = xⁿ, du = (nxⁿ⁻¹)dx

v = −e^−x, dv = (e^−x)dx

Jadi, bentuk tereduksi untuk f(n) adalah f(n) = n × f(n − 1).

Dikarenakan f(0) = 1 dan f(n) = n × f(n − 1), fungsi ini memenuhi definisi faktorial.

Jadi, f(n) = n!, dengan kata lain fungsi ini merupakan fungsi faktorial.

Fungsi ini dapat digunakan untuk menghitung faktorial dari bilangan berapapun, selain bilangan bulat negatif, dikarenakan f(0) = 1 dan f(n) = n × f(n − 1), apabila dimasukkan n = 0 ke bentuk reduksi

f(0) = 0 × f(0 − 1) = 0 × f(−1)

1 = 0 × f(−1), tidak ada f(−1) yang memenuhi, begitu juga semua bilangan bulat sebelumnya, dimana

f(−1) = −1 × f(−2) yang mana f(−1) tidak terdefinisikan, sehingga f(−2) dan seterusnya tidak terdefinisikan.

D_f = {x ∈ ℝ | x ∉ ℤ ∨ x ≥ 0}, berikut grafik fungsinya:

untuk setiap x bilangan bulat negatif, menjadi asimtot tegak.

Mungkin diantara Sixtyfourians ada yang mengetahui jokes ini:

"Terdapat sebanyak ½√π cara menyusun ½ objek"

lalu muncul pertanyaan: "Bagaimana menyusun objek yang tidak utuh?", tetapi ternyata dengan memasukkan n = ½ ke fungsi faktorial yang diperumum, akan diperoleh hasil ½√π.

Mula-mula gunakan rumus reduksi

misal x = u² → dx = 2u du

Kuadratkan

mengapa boleh? karena u dan v hanya dummy variable. Ubah ke koordinat polar
misal u = r.cos(θ), v = r.sin(θ), sehingga u² + v² = r².[cos²(θ) + sin²(θ)] = r²

Daerah integrasinya terbatas di kuadran I, dimana

S = {(u, v) | u ≥ 0; v ≥ 0} = {(r, θ) | r ≥ 0; 0 ≤ θ ≤ π/2}

sehingga

Jadi, jokes ini sesuai dengan rumus faktorial yang diperumum.