Kombinatorik

KOMBINATORIKA

Purwanto

Matematika UM

ISI

aturan jumlah, aturan kali, permutasi, kombinasi, barisan, dan multiset, fungsi pembangkit, relasi rekurensi, koefisien binomial, pigeon hole, inklusi-eklusi, paritas, juga teknik pembuktian, antara lain induksi matematika, bukti dengan kontradiksi.

Prinsip pigeon hole: Jika ada n + 1 burung dara masuk ke dalam n sangkar, maka ada paling sedikit satu sangkar berisi lebih dari satu burung.

Aturan Jumlah: Andaikan A dan B adalah peristiwa yang saling asing, yaitu tidak pernah terjadi bersamaan. Lebih lanjut andaikan dapat A terjadi dalam m cara dan B dapat terjadi dalam n cara. Maka peristiwa A atau B dapat terjadi dalam m + n cara.

Aturan Kali: Aturan Jumlah: Andaikan peristiwa C dapat terjadi dalam dua tahap A dan tahap B, tahap A dapat terjadi m cara dan tahap B dapat terjadi dalam n cara. Maka peristiwa C dapat terjadi dalam mn cara.

Prinsip Inklusi Eksklusi:

,

,

Dua Model Pencacahan:

Model Sampel:

Misalkan diketahui himpunan , akan diambil 3 anggotanya. Ada berapa cara pengambilannya?

Jawaban soal dia atas masih terlalu luas. Apa syarat pengambilannya?

- Urutan diperhatikan atau tidak

- Pengambilan suatu anggota boleh diulangi (dengan pengembalian) atau tidak

Jika dibuat tabel akan menjadi sebagai berikut.

Pengulangan Tanpa Pengulangan

urutan	barisan …	permutasi …
pemilihan	multiset …	kombinasi

Model Distribusi:

Diketahui ada 4 lobang berlainan dan 3 bola. Ada berapa cara pendistribusian 3 bola ke dalam 4 lobang tersebut? Seperti pada model sampel, perlu syarat bolanya:

- Bola sama atau berlainan

- Satu lobang boleh lebih dari satu bola atau tidak

Jika dibuat tabel akan menjadi sebagai berikut.

Boleh lebih satu bola Maks. satu bola

perlobang perlobang

urutan	| | | | | | | | | | barisan | | | | | … | | | | |	| | | | | | | | | | permutasi | | | | | ... | | | | |
pemilihan	| | | | | | | | | | multiset | | | | | … | | | | |	| | | | | | | | | | kombinasi | | | | | | | | | |

Pencacahan dengan Bijeksi:

Diketahui dua himpunan A dan B, serta diketahui , tetapi tidak diketahui. Jika kita dapat mengkonstruksi bijeksi , maka .

Binomial:

Relasi rekurensi.

Barisan 1, 4, 7, 10, 13, ... suku ke n nya adalah , . Barisan ini dapat dinyatakan dengan relasi rekurensi:

, , untuk .

Diketahui barisan duku , , dan , untuk . Tentukan rumus suku ke n dalam n,

= ?

Tentukan rumus suku ke n barisan Fibonacci.

MULAI DARI KASUS SEDERHANA

Soal 1. Ada berapa cara mengeja MATEMATIKA pada daftar berikut ini dengan menggunakan huruf-huruf yang berdekatan?

M

A A

T T T

E E E E

M M M M M

A A A A A A

T T T T T T T

I I I I I I I I

K K K K K K K K K

A A A A A A A A A A

Pada contoh Soal I di atas yang dicari adalah cacah atau banyaknya cara mengeja MATEMATIKA, yang diketahui adalah daftar atau tabel dari huruf-huruf dengan susunan tertentu, syaratnya adalah dengan menggunakan huruf-huruf yang berdekatan.

Bagaimana memulai menyelesaikan soal di atas? Untuk menyelesai-kannya kita harus tahu apa yang ditanyakan, apa yang diketahui, dan apa syaratnya. Dipikirkan atau diingat soal yang mirip yang pernah dapat dikerjakan. Dapat pula dicari penyelesaian dari soal yang lebih sederhana yang dapat diselesaikan, kemudian meningkat ke soal yang lebih sulit seperti aslinya, dicari kemungkinan hasilnya (perkiraan/konjektur), dan kemudian dibuktikan.

Misalnya untuk mengeja MA, MAT, dan MATE dari

M M M

A A A A A A

T T T T T T

E E E E

berturut-turut ada 2, 4, dan 8 cara. Mungkin polanya 2¹, 2², 2³, …. Akibatnya, pada soal no.I jawabnya adalah 2⁹ (perkiraan). Jawaban ini perlu dibuktikan atau diberikan alasannya. Misalnya, dari M ke A perlu bergerak ke bawah kiri atau kebawah kanan satu kali, dari A ke T perlu bergerak ke bawah kiri atau kebawah kanan satu kali, dan seterusnya, sehingga untuk mengeja MATEMATIKA perlu bergerak ke kiri bawah atau ke kanan bawah sebanyak 9 kali, ada 2⁹ cara.

SOAL BERBEDA JAWABAN SAMA

Soal 2a. Ada berapa cara mengeja MATEMATIKA pada daftar berikut ini dengan menggunakan huruf-huruf yang berdekatan?

M

A A

T T T

E E E E

M M M M

A A A A

T T T T

I I I

K K

A

Soal 2b. Tentukan banyaknya cara bergerak dari A ke B dengan melewati ruas garis-ruas garis dengan jarak minimum.

A

B

Soal 2c. Ada berapa himpunan bagian yang mempunyai tiga anggota dari .

Soal 2d. Ada berapa barisan binar berbeda dengan sembilan suku yang memuat tepat tiga 0?

Soal 2e. Tentukan koefisien pada .

Soal 2f. Ada berapa cara memperoleh enam sisi muka pada pengetosan satu koin sembilan kali?

Soal 2g. Ada berapa cara memilih tiga orang dari sembilan orang?

Soal 2h. Ada berapa bilangan enam angka, tanpa 0, dengan ?

Soal 2i. Seorang penjual menjual gorengan tempe, tahu, menjes, pisang, nanas, weci, ketela rambat, pohung, dan mendol. Ia akan membungkus makanannya dengan setiap bungkus berisi enam makanan berbeda. Ada berapa variasi bungkus, menurut isinya, yang mungkin?

Soal 2j. Ada berapa barisan binar dengan delapan suku dan hanya memuat satu 01?

Soal 2k. ....................

SOAL BERVARIASI, DARI SANGAT SEDERHANA SAMPAI CUKUP SULIT

Soal 3a. Seorang anak mempunyai dua baju batik dan tiga baju polos. Ia akan memakai suatu baju. Ada berapa pilihan?

Soal 3b. Seorang anak mempunyai empat baju berturut-turut berwarna putih, bitu, kuning, dan merah, serta mempunyai tiga celana berturut-turut berwarna merah biru dan hitam. Ia akan memakai baju dan celana. Ada berapa pasangan baju dan celana yang mungkin?

Soal 3c. Ada 15 kursi berjajar ke samping. Akan dipilih lima kursi secar acak. Ada berapa pilihan?

Soal 3d. Ada 15 kursi berjajar ke samping. Ada lima orang akan menempatinya. Ada berapa cara mereka menempatinya?

Soal 3e. Ada 15 kursi berjajar ke samping. Akan dipilih lima kursi yang tidak berdekatan. Ada berapa pilihan?

Soal 3f. Ada 15 kursi berjajar ke samping. Ada lima orang akan menempatinya. Ada berapa cara menempatinya dengan i) tidak ada yang berdekatan? ii) di antara dua orang paling sedikit ada dua kursi?

Soal 3g. Satu set soal terdiri dati 20 soal pilihan B atau S dan 30 soal pilihan ganda dengan empat pilihan. Seseorang mengerjakan semua soal secara acak. berapa probabilitas ia menjawab

i) benar semua soal?

ii) salah semua soal?

iii) benar hanya tiga soal?

iv) benar hanya 30 soal?

Soal 3h. Ada 2n pemain pada suatu turnamen tenis. Pemain tersebut dipasang-pasangkan untuk dipertandingkan. Ada berapa cara pemasangannya?

Soal 3h. Tunjukkan bahwa

Soal 3j. Tujuh belas orang saling berkorespondensi dengan surat, masing-masing orang dengan semua yang lain. Hanya ada tiga topik yang yang didiskusikan. Masing-masing pasang hanya mendiskusikan satu topik. Buktikan bahwa ada paling sedikit tiga orang yang berkorespondensi dengan topik yang sama.

Soal 3k. Buktikan bahwa dari suatu himpunan sepuluh bilangan berlainan yang masing-masing terdiri dari dua digit dapat dipilih dua himpunan bagian saling asing dengan jumlah anggotanya sama.

Soal 3l. Ada berapa barisan berlainan naik turun naik turun ... yang suku-sukunya 1, 2, 3, 4, 5, 6, atau 7?