A.Kombinatorial
Kombinatorial (combinatoric) adalah cabang matematika yang mempelajari pengaturan objek-objek. Solusi yang ingin kita peroleh dengan kombinatorial ini adalah jumlah cara pengaturan objek-objek tertentu di dalam himpunan. Tiga buah contoh ilustrasi berikut dikemukakan untuk memperjelas masalah seperti apa yang akan dipecahkan dengan kombinatorial.
(i)Contoh pertama, misalkan nomor plat mobil di negara X terdiri atas 5 angka, angka diikuti dengan 2 huruf. Angka pertama tidak boleh 0. Berapa banyak plat mobil yang dapat di buat ?
(ii)Contoh kedua, sandi-lewat (password) sistem komputer panjangnya enam sampai delapan karakter. Tiap karakter boleh berupa huruf atau angka; huruf besar dan huruf kecil tidak di bedakan. Berapa banyak sandi-lewat yang dapat dibuat?
(iii)Dari 20 angka fraksi X di DPR, akan dibentuk sebuah komisi yang beranggotakan 6 orang. Berapa banyak cara memilih anggota komisi bila seorang anggota yang bernama A harus termasuk di dalam komisi tersebut ?
Cara yang paling sederhana untuk menyelesaikan persoalan semacam di atas adalah dengan mengenumerasi semua kemungkinan jawabannya. Mengenumerasi artinya mencacah atau menghitung (count) satu persatu setiap kemungkinan jawaban. Untuk persoalan dengan jumlah objek sedikit, mengenumerasi setiapa kemungkinan jawaban masih dapat dilakukan, tetapi untuk persoalan dengan dengan jumlah objek yang banyak, cara enumerasi jelas tidak sangkil. Misalnya pada persoalan pertama, bila kita mengenumerasi semua kemungkinan jawabannya adalah seperti di bawah ini.
12345AB
12345AC
12345BC
...
34567MT
34568ML
...
Dan seterusnya...
Mungkin kita sudah lelah sebelum usaha mengenumerasi semua kemungkinan nomor plat mobil selesai,karena nomor palt mobil yang dibentuk sangat banyak. Di sinilah peran kombinatorial, yang merupakan “seni berhitung”, menyelesaikan persoalan semacam ini dengan cepat. Kombinatorial dapat digunakan untuk menjawab persoalan semacam ini tanpa kita perlu mengenumerasi semua kemungkinan jawabannya. Hal ini dapat dilakukan karena di dalam kombinatorial terdapat kaidah dasar menghitung. Dengan kaidah ini, berbagai persoalan menghitung jumlah cara pengaturan objek dapat diselesaikan. Kita juga menggunakan kaidah dasar menghitung untuk mengetahui berapa jumlah kemungkinan sandi-lewat yng harus dicoba oleh seorang penyusup (intruder) untuk memasuki sebuah sistem komputer. Terakhir, kombinatorial digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.
B.Percobaan
Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan (experimen). Percobaan adalah proses fisik yang hasilnya dapat diamati.
Contoh-contoh percobaan dan hasilnya (outcome) adalah :
1.Melempar dadu
Enam hasil percobaan yang mungkin untuk pelempar dadu adalah muka dadu 1, 2, 3, 4, 5, 6
2.Melempar koin uang Rp 100
Hasil percobaan melempar koin 100 ada dua kemungkinan: muka koin yang bergambar rumag gadang atau muka koin yang bergambar wayang
3.Memilih lima orang wakil dari 100 oang mahasiswa
Hasil yang diperoleh adalah perwakilan yang beranggotakan lima orang mahasiswa. Kemungkinan perwakilan yang dapat dibentuk banyak sekali.
4.Menyusun jumlah kata yang panjangnya 5 huruf yang dapat dibentuk dari huruf-huruf a, b, c, d, e, tidak boleh ada huruf yang berulang di dalam kata. Hasil yang di peroleh adalah string yang disusun oleh huruf-huruf tersebut, misalnya accde, abced, acdeb, dan seterusnya.
C.Kaidah Dasar Menghitung (Counting)
Di dalam kombinatorial, kita harus menghitung (counting) semua kemungkinan pengaturan objek.dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan(rule of sum). Kedua kaidah ini dapat digunakan untuk memecahkan banyak masalah persoalan menghitung.
1.Kaidah Perkalian (rule of product)
Bila percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi (atau menghasilkan p kemungkinan jawaban), percobaan 2 mempunyai q hasil percobaan yang nungkin terjadi (atau menghasilkan q kemungkinan jawaban), maka bila percobaan 1 dan percobaan 2 dilakukan, maka terdapat p x q hasil percobaan (atau menghasilkan p x q kemungkinan jawaban).
Contoh :
Tersedia angka 0 – 9
a). Tentukan banyak cara pembentukan 3 angka
b). Tentukan banyak cara pembentukan angka ratusan
c). Tentukan banyak cara pembentukan ratusan genap
Penyelesaian :
a). 10 x 10 x 10
b). 9 x 10 x 10
c). 8 x 8 x 5
2.Kaidah Penjumlahan (rule of sum)
Bila percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi (atau menghasilkan p kemungkinan jawaban), percobaan 2 mempunyai q hasil percobaan yang mungkin terjadi (atau menghasilkan q kemungkinan jawaban), maka bila hanya satu percobaan saja yang dilakukan (percobaan1 atau percobaan 2), terdapatp + q kemungkinan hasil percobaan (menghasilkan p + q kemungkinan jawaban) yang mungkin terjadi.
Perhatikanlah kata yang digarisbawahi pada kedua di atas: dan serta atau. Kedua kata ini adalah kata kunci untuk mengidentifikasi apakah suatu persoalan menghitung diselesaikan dengan kaidah perkalian atau kaidah penjumlahan. Kaidah perkalian meyatakan bahwa kedua percobaan dilakukan secara simultan atau serempak, sedangkan pada kaidah penjumlahan, kedua percobaan dilakukan tidak simultan.
Teorema
Jika suatu operasi dapat diselesaikan dengan k alternatif.
Alternatif pertama dengan n1 cara dan selanjutnya sampai alternatif ke k. Maka operasi tersebut dapat dilakukan dengan
n1 + n2 + .... + nk cara
contoh :
Ada 500 mahasiswa dan 30 dosen. berapa banyak cara sebuah laptop dapat diberikan
Penyelesaian :
n1 = 500 , n2 = 30
n1 + n2 = 500 + 30 = 530 cara
Contoh Soal
1.Sekelompok mahasiswa terdiri dari 4 orang pria dan 3 orang wanita. Berapa jumlah cara memilih satu orang wakil pria dan satu orang wakil wanita ?
Penyelesaian :
Ada 4 kemungkinan memilih satu wakil pria
Ada 3 kemungkinan memilih satu wakil wanita
Jika dua orang wakil harus dipilih, masing-masing 1 pria dan 1 wanita
Maka jumlah kemungkinan perwakilan yang dapat dipilih adalah 4 x 3 = 12.
2.Sekelompok mahasiswa terdiri atas 8 orang pria dan 9 orang wanita. Berapa jumlah cara memilih satu orang yang mewakili kelompok tersebut (tidak peduli pria atau wanita) ?
Penyelesaian :
Ada 8 kemungkinan memilih satu wakil pria
Ada 9 kemungkinan memilih satu wakil wanita
Jika hanya satu orang wakil yang dipilih (pria atau wanita)
Maka jumlah kemungkinan wakil yang dipilih adalah 8 + 9 = 17.
3.Plat kendaran untuk kota tangerang
- Terdiri dari 8 digit
- Digit pertama harus huruf B
- 4 digit berikutnya angka boleh berulang
- Angka pertama tidak boleh angka 0
- 3 digit terakhir adalah huruf yang pertama huruf C
Penyelesaian :
Jumlah huruf afjat = 26
Bilangan desimal 0 – 9
1 x 9 x 10 x 10 x 10 x 1 x 26 x 26 = 6.084.00
4.Ada 2 kendaraan yaitu mobil dan kereta api akan berangkat dari Jakarta menuju Yogyakarta. Mobil tersebut dapat melewati 3 jalur dan kereta api dapat melewati 1 jalur. Berapa banyak cara yang dapat ditempuh dari Jakarta menuju Yogyakarta ?
Penyelesaian :
n1 = 3 n2 = 1
n1 + n2 = 3 + 1 = 4 cara
5.Ada berapa bilangan ganjil dari 1.000 sampai 9.999
a.Boleh berulang
b.Tidak boleh berulang
Penyelesaian :
Bilangan ganjil dari 0 – 9 = ada 5 (1, 3, 5, 7, 9)
Angka awal tidak boleh 0, karena jika 0 akan kurang dari ribuan
a.9 x 10 x 10 x 5 = 4.500 cara
b.8 x 8 x 7 x 5 = 2.240 cara
D.Prinsip Sarang Merpati
Misalkan kita mempunyai kandang burung merpati (pigeon) yang memiliki pintu masuk berupa lubang-lubang (hole). Satu lubang berarti satu sarang . Setiap sarang biasanya ditempati oleh seekor burung merpat. Misalkan merpati ada 16 ekor sedangkan kandang hanya 14 buah sarang. Prinsip sarang merpati (pigeonhole principle) menyatakan bahwa paling sedikit terdapat satu sarang yang ditempati oleh dua ekor merpati.
Teorema I : Jika n + 1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Bukti : Misalkan tidak ada kotak yang berisi lebih dari dua objek. Maka, total jumlah objek paling banyak adalah n. Ini kontradiksi, karena jumlah objek paling sedikit n + 1.
Prinsip sarang merpati dikemukakan oleh G. Lejeune Dirichlet, seorang matematikawan jerman, sehingga kadang-kadang dinamakan juga Prinsip Kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya. Prinsip sarang merpati, jika diterapkan dengan baik, akan memberikan hanya objek-objek yang ada, dan bukan memberitahukan bagaimana mencari objek tersebut dan berapa banyak [JOH97]. Pada masalah sarang burung merpati, prinsip ini tidak memberitahukan di sarang merpati mana yang berisi lebih dari dua ekor merpati.
Contoh soal
1.Misalkan terdapat banyak bola merah, bola putih, dan bola biru di dalam sebuah kotak. Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat ke dalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil ?
Penyelesaian :
Jika setiap warna dianggap sebagai sarang merpati, maka n = 3.
Karena itu, jika orang mengambil paling sedikit n + 1 = 4 bola, Maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.
Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.
Jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjaminterambil sepasang bola yang berwarna sama.
2.Misalkan sebuah turnamen basket diikuti oleh n buah tim yang dalam hal ini setiap tim bertanding dengan setiap tim lainnya dan setiap tim menang paling sedikit satu kali. Tunjukkan bahwa paling sedikit ada 2 tim yang mempunyai jumlah kemenangan yang sama.
Penyelesaian :
Jumlah kemenangan setiap tim paling sedikit 1 kali dan paling banyak n – 1 kali.
Angka n – 1 berkoresponden dengan n – 1 buah sarang merpati untuk menampung nekor merpati (tim basket).
Jadi, paling sedikit ada 2 tim basket yang mempunyai jumlah kemenangan sama.
Prinsip sarang merpati dapat dirampatkan (generalized) sedemikian sehingga jumlah objek dapat merupakan kelipatan jumlah kotak. Misalkan jika terdapat 20 sarang merpati dan 41 ekor merpati, maka terdapat satu buah sarang merpati ynag berisi lebih dari 2 ekor merpati. Hal ini dinyatakan dalam teorema berikut.
Teorema II : jika M objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi minimal [M/n] objek.
Bukti teorema : tidak diberikan di sini dan ditinggalkan kepada pembaca sebagai latihan. Teorema II juga menyatakan bahwa jika n buahkotak akan diisi dengan M = nk + 1 objek, yang dalam hal ini k adalah bilangan bulat positif maka paling sedikit terdapat 1 kotak yang berisi minimal k + 1 objek.
Contoh soal
1.Terdapat banyak bola merah, bola putih, dan bola hijau di dalam sebuah kotak . Berapa paling sedikit jumlah bola yang harus diambil dari dalam kotak sehingga 3 pasang bola yang setiap pasangnya berwarna sama terambil ?
Penyelesaian :
Tiga pasang bola yang setiap pasang berwarna sama = jumlah 6 buah bola
N = 3 (jumlah warna). Kita perlu mengambil paling sedikit M buah bola untuk memastikan bahwa [M/3] = 6 (bola mengandung setiap pasang bola yang berwarna sama).
M = 3 . 5 + 1 = 16
Jika kita hanya mengambil 15 bola, maka kemungkinan hanya terambil 2 macam bola yang berwarna sama.
Jadi jumlah 16 buah bola adalah jumlah minimal yang perlu kita ambil dari kotak untuk memastikan bahwa ada 3 pasang bola yang setiap pasang berwarna sama terambil.
Sekian dari tugas 3 proses stokastik, mohon dikoreksi apabila ada kesalahan.
Wassalamualaikum wr.wb.
Muhammad_Eko_Prasetyo_16050874005_TE_A_2016
