Kombinatorial KELSON VINCIEN

DAFTAR ISI KOMBINATORIAL A. Definisi B. Contoh Masal ah Kombina tor ial

...01 ...01

KAIDAH DASAR MENGHI TUNG A. Kaidah Per kal ian (rule of product) B. Kaidah Penjumlahan (rule of sum)

...03 ...04 ...04

PERLUASAN KAI DAH DASA R MENGH ITUNG

...05

PRINSIP INKLUSI-EKSKLUSI

...07

PERMUTASI A. Permutasi n objek B. Permutasi r objek dari n ob jek

...08 ...08 ...09

KOMBINASI A. Kombinasi n objek B. Kombinasi r objek dari n obj ek

...11 ...11 ...12

PRINSIP SARANG MERPATI

...13

DAFTAR PUSTAKA

...14

























KOMBINATORIAL

APA ITU KOMBINATORIAL? Kombinatorial adalah cabang matematika yang mempelajari tentang pengaturan objek-objek. Hal ini meliputi cara menghitung jumlah permutasi dan kombinasi dari objek-objek yang berbeda. Kombinatorial sangat penting dalam berbagai bidang, termasuk matematika, ilmu komputer, dan statistik. Dalam kombinatorial, fokus utamanya adalah pada menghitung jumlah cara yang berbeda untuk memilih, mengatur, atau mengelompokkan objek-objek yang berbeda.

Untuk memahami kombinatorial dengan lebih jelas, berikut ini adalah beberapa contoh masalah kombinatorial: Dalam suatu kelas, terdapat 3 siswa dan 3 kursi. Berapa banyak cara yang berbeda untuk ketiga siswa tersebut duduk di 3 kursi yang ada? Nomor PIN HP adalah 6 angka. Berapa jumlah PIN yang dapat dibuat? Berapa banyak cara membentuk 5 kelompok dari 35 siswa di suatu kelas? Ada 4 buku dalam suatu rak buku di perpustakaan. Berapa banyak cara yang berbeda untuk menyusun keempat buku tersebut? Nomor plat negara A terdiri dari 4 angka dan diikuti dengan 2 huruf. Berapa banyak nomor plat yang dapat dibuat?

01

KOMBINATORIAL

Dari contoh-contoh masalah tersebut, pastinya sudah ada gambaran yang lebih jelas mengenai kombinatorial. Cara yang paling mudah untuk menyelesaikan masalah-masalah di atas adalah dengan mencacah atau menghitung satu per satu setiap kemungkinan jawaban yang ada. Cara ini sering disebut dengan mengenumerasi. Misalkan, untuk contoh masalah pertama, menghitung dengan menghitung atau kemungkinannya satu per satu.

kita dapat menggambar

Dari hasil tersebut, didapatkan bahwa ada 6 cara yang berbeda untuk ketiga siswa tersebut duduk di 3 kursi yang ada. Metode enumerasi merupakan metode yang mudah untuk digunakan dan sangat jelas untuk hasilnya. Namun, metode enumerasi sangat sulit untuk digunakan jika kemungkinan atau cara yang berbeda sangat banyak. Misalkan, untuk contoh masalah terakhir, sangat sulit jika menggunakan metode enumerasi. Meskipun masih memungkinkan untuk dihitung satu per satu, tetapi waktu yang diperlukan sangat banyak dan cara pengerjaan sangat tidak efektif. Dari kasus seperti ini, peran kombinatorial menjadi sangat penting untuk menyelesaikan masalah-masalah ini secara tepat tanpa mengenumerasi semua kemungkinan jawaban. Kombinatorial dapat digunakan karena memiliki kaidah dasar menghitung,

02

KAIDAH DASAR MENGHITUNG

KAIDAH DASAR MENGHITUNG Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).

Sebelum masuk ke dua kaidah dasar menghitung tersebut, perlu diingat kembali konsep peluang dan probabilitas. Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan yang dapat diamati. Probabilitas suatu peristiwa adalah angka yang menunjukkan seberapa besar kemungkinan peristiwa itu terjadi. Hal ini dinyatakan sebagai angka dalam kisaran dari 0 dan 1, atau, menggunakan notasi persentase dalam kisaran dari 0% hingga 100%.

Contoh: 1. Melempar koin Dari 1 percobaan, hasil yang bisa didapatkan ada 2, yaitu angka atau gambar. Peluang untuk mendapatkan angka adalah 0,5 dan gambar adalah 0,5. 2. Melempar dadu Dari 1 percobaan, hasil yang bisa didapatkan ada 6, yaitu 1, 2, 3, 4, 5, atau 6. Peluang untuk mendapatkan 1 adalah ⅙ , 2 adalah ⅙, dan seterusnya.

03

KAIDAH DASAR MENGHITUNG

A. Kaidah Perkalian (rule of product) Bila percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi, percobaan 2 mempunyai q hasil percobaan yang mungkin terjadi, maka percobaan 1 dan percobaan 2 mempunyai p x q hasil percobaan yang mungkin terjadi. Contoh: Sekelompok mahasiswa terdiri dari 4 orang pria dan 4 orang wanita. Berapa jumlah cara memilih satu orang wakil pria dan satu orang wakil wanita? Penyelesaian: Ada 4 kemungkinan memilih satu wakil pria, dan 4 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 4 = 16.

B. Kaidah Penjumlahan (rule of sum) Bila percobaan 1 mempunyai p hasil percobaan yang mungkin terjadi, percobaan 2 mempunyai q hasil percobaan yang mungkin terjadi, maka percobaan 1 atau percobaan 2 mempunyai p + q hasil percobaan yang mungkin terjadi. Contoh: Sekelompok mahasiswa terdiri atas 4 orang pria dan 4 orang wanita. Berapa jumlah cara memilih satu orang yang mewakili kelompok tersebut (tidak peduli pria atau wanita)? Penyelesaian: Ada 4 kemungkinan memilih satu wakil pria, dan 4 kemungkinan memilih satu wakil wanita. Jika hanya satu orang wakil yang harus dipilih (tidak memperhatikan gender), maka jumlah kemungkinan wakil yang dapat dipilih adalah 4 + 4 = 8 cara.

04

PERLUASAN KAIDAH DASAR MENGHITUNG

PERLUASAN KAIDAH DASAR MENGHITUNG Kaidah perkalian dan kaidah penjumlahan di atas dapat diperluas hingga mengandung lebih dari 2 buah percobaan. Misalkan ada n percobaan, maka : Kaidah perkalian (rule of product) : p1 x p2 x … pn hasil Kaidah penjumlahan (rule of sum) : p1 + p2 + … pn hasil

Contoh 1: Berapa banyak kata yang terdiri dari 3 huruf yang dibentuk dari huruf A, K, U jika pengulangan diperbolehkan? Penyelesaian: Dalam permasalahan ini terdapat 3 kegiatan percobaan, yaitu percobaan 1 memilih huruf pertama, percobaan 2 memilih huruf kedua, dan percobaan 3 memilih huruf ketiga. Masingmasing percobaan tersebut memiliki 3 kemungkinan jawab, karena

pengulangan

diperbolehkan.

Huruf

pertama,

kedua,

ataupun ketiga dapat diisi dengan huruf A, K, atau U. Untuk mencari

banyaknya

kata

yang

terdiri

dari

3

huruf

dapat

dibentuk berarti percobaan 1, percobaan 2, dan percobaan 3 dilakukan secara serentak sehingga terdapat 3 x 3 x 3 = 27 kemungkinan jawab.

05

PERLUASAN KAIDAH DASAR MENGHITUNG

Contoh 2: Sebuah perpustakaan kecil memiliki 4 buku Matematika, 3 buku Bahasa Indonesia, 5 buku Bahasa Inggris. Masing-masing buku berbeda judulnya. Berapa banyak cara memilih 1 buku? Penyelesaian: Dalam permasalahan tersebut, memilih 1 buku dapat berupa buku Matematika atau Bahasa Indonesia atau Bahasa Inggris, sehingga terdapat 3 percobaan dimana percobaan 1 memilih buku Matematika (ada 4 kemungkinan), percobaan 2 memilih buku Bahasa Indonesia (ada 3 kemungkinan), percobaan 3 memilih buku Bahasa Inggris (ada 5 kemungkinan). Jadi, kemungkinan memilih 1 buku terdapat 4 + 3 + 5 = 12 kemungkinan pemilihan.

Latihan Soal 1 Sandi-lewat (password) sistem komputer panjangnya 6 s.d. 8 karakter. Tiap karakter boleh berupa huruf atau angka; huruf besar dan kecil tidak dibedakan. Berapa banyak sandi-lewat yang dapat dibuat?

Silahkan kerjakan latihan soal terlebih dahulu. Untuk melihat penjelasan mengenai cara pengerjaannya, silahkan menonton video berikut ini: Latihan Soal 1.mp4 (silahkan klik pada nama file atau scan QR Code)

06

PRINSIP INKLUSI-EKSKLUSI

PRINSIP INKLUSI-EKSKLUSI Prinsip inklusi-eksklusi (inclusion-exclusion principle) merupakan perluasan konsep dari diagram Venn yang melibatkan operasi irisan dan gabungan dalam himpunan.

Contoh: Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’? Penyelesaian: Misalkan A = himpunan byte yang dimulai dengan ‘11’ 1 1 _ _ _ _ _ _ B = himpunan byte yang diakhiri dengan ‘11’ _ _ _ _ _ _ 1 1 A B = himpunan byte yang berawal dan berakhir dengan ‘11’ 1 1 _ _ _ _ 1 1 A B = himpunan byte yang berawal atau berakhir dengan ‘11’

→ →

∩ → ∪

∩

|A| = 2^6 = 64, |B| = 2^6 = 64, |A B| = 2^4 = 16 |A B| = |A| + |B| - |A B| = 64 + 64 - 16 = 112

∪

07

∩

PERMUTASI

PERMUTASI Permutasi

adalah

objek-objek.

jumlah

Permutasi

urutan

berbeda

merupakan

bentuk

dari

pengaturan

khusus

aplikasi

kaidah perkalian. nPr = permutasi n = total jumlah objek r

=

jumlah

objek

yang

dipilih

A. Permutasi n objek Misalkan jumlah objek adalah n, maka urutan pertama dipilih dari n objek, urutan kedua dipilih dari n – 1 objek, urutan ketiga dipilih dari n – 2 objek, … urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian, permutasi dari n objek adalah : n(n – 1)(n – 2) … (2)(1) = n! Permutasi dari n objek sering disimbolkan dengan P(n,n) atau nPn

Contoh: Misalkan, ada 3 buah bola yang berbeda warnanya, yaitu merah (m), biru (b) dan putih (p). Kita akan memasukkan ketiga buah bola tersebut ke dalam 3 buah kotak, masing-masing 1 buah bola. Berapa jumlah urutan berbeda yang mungkin dibuat dari penempatan bola merah, biru, putih ke dalam kotak 1, 2, 3 ?

08

PERMUTASI

Penyelesaian: Misalkan urutan itu kita simbolkan xyz. Urutan pertama (x) mungkin ditempati oleh salah satu dari 3 bola, urutan kedua (y) mungkin ditempati oleh salah satu dari 2 buah bola (karena 1 bola sudah dipakai untuk x), dan urutan ketiga (z) ditempati oleh 1 buah bola yang tersisa, sehingga jumlah kemungkinan urutan berbeda dari penempatan bola ke dalam kotak adalah : 3 x 2 x 1 = 3! = 6

B. Permutasi r objek dari n objek Banyaknya urutan/cara dari penempatan r objek yang dipilih dari n objek yang berbeda dengan r≤n seperti di atas disebut sebagai permutasi r dari n objek atau sering disimbolkan dengan P(n,r) atau nPr.

Contoh: Berapa banyak cara menempatkan 5 objek berbeda (merah, biru, kuning, hitam, hijau) ke dalam 2 tempat kosong, sedemikian sehingga setiap tempat berisi 1 objek?

09

PERMUTASI

Penyelesaian: Untuk mengetahui Banyak cara menempatkan 5 objek berbeda (merah, biru, kuning, hitam, hijau) kedalam 2 tempat kosong maka diperlukan 2 percobaan. Percobaan 1 adalah mengisi tempat pertama dan percobaan 2 mengisi tempat kedua. Percobaan 1 ada 5 kemungkinan, sedangkan percobaan 2 hanya 4 kemungkinan karena satu objek telah ditempatkan pada tempat pertama. Maka banyaknya kemungkinan atau cara untuk menempatkan 5 objek berbeda (merah, biru, kuning, hitam, hijau) ke dalam 2 tempat kosong, adalah 5 × 4 = 2.

Latihan Soal 2 Berapa banyak jumlah kemungkinan 3 angka dari 5 angka berikut: 1, 2, 3, 4, 5 jika: (i) Tidak boleh ada pengulangan angka, dan (ii) Boleh ada pengulangan angka.

Silahkan kerjakan latihan soal terlebih dahulu. Untuk melihat penjelasan mengenai cara pengerjaannya, silahkan menonton video berikut ini: Latihan Soal 2.mp4 (silahkan klik pada nama file atau scan QR Code)

10

KOMBINASI

KOMBINASI Bentuk

khusus

permutasi

urutan

permutasi

adalah

kemunculan

kombinasi.

diperhitungkan,

Jika

pada

maka

pada

kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali. nCr = kombinasi n = total jumlah objek r

=

jumlah

objek

yang

dipilih

A. Kombinasi n objek Kombinasi n objek adalah banyaknya urutan dari pengaturan n obyek-obyek yang sama/identik. Pada pengaturan ini urutan objek tidak diperhatikan. Kombinasi n objek disimbolkan dengan C(n,n) atau nCn.

Contoh: Berapa banyak cara menempatkan 3 objek identik (warna sama) ke dalam tiga tempat kosong sedemikian sehingga masing-masing tempat memuat 1 objek? Penyelesaian: Jika objek berbeda, banyaknya cara penempatan 3 objek berbeda ke dalam 3 tempat merupakan peristiwa permutasi 3 objek atau P(3,3) = 3! = 6. Namun, karena 3 objek yang ada identik maka keenam cara yang diperoleh tadi ternyata sama semua (tidak berbeda) sehingga untuk menempatkan 3 objek identik ke dalam 3 tempat kosong ada 1 cara atau C(3, 3).

11

KOMBINASI

B. Kombinasi r objek dari n objek Kombinasi r objek dari n obyek adalah Banyaknya urutan dari pengaturan r objek dari n obyek yang sama (r≤n) . Kombinasi r objek dari n objek disimbolkan dengan C(n,r) atau nCr.

Contoh: Berapa banyak cara menempatkan 2 objek identik (warna sama) ke dalam tiga tempat kosong sedemikian sehingga masing-masing tempat paling banyak memuat 1 objek? Penyelesaian: Banyak cara penempatan 2 objek berbeda ke dalam 3 tempat sedemikian sehingga setiap tempat paling banyak memuat 1 objek merupakan peristiwa kombinasi 2 objek dari 3 objek atau C(3, 2). Sehingga, banyaknya cara adalah 3 cara.

Latihan Soal 3 Sebuah klub beranggotakan 8 pria dan 10 wanita. Berapa banyak cara memilih panitia yang terdiri dari 6 orang dengan jumlah wanita lebih banyak dari pria? Silahkan kerjakan latihan soal terlebih dahulu. Untuk melihat penjelasan mengenai cara pengerjaannya, silahkan menonton video berikut ini: Latihan Soal 3.mp4 (silahkan klik pada nama file atau scan QR Code)

12

PRINSIP SARANG MERPATI

PRINSIP SARANG MERPATI Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.

Contoh: 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 orang mengambil paling sedikit n + 1= 4 bola (merpati) 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 menjamin terambil sepasang bola yang berwarna sama.

13

DAFTAR PUSTAKA https://spada.uns.ac.id/pluginfile.php/551017/mod_resource/ content/1/KOMBINATORIAL.pdf https://mkazis.medium.com/3-8-kombinatorial-dan-peluangdiskrit26140f1257fa#:~:text=Dua%20kaidah%20dasar%20yang%20di gunakan,penjumlahan%20(rule%20of%20sum).&text=Kaidah %20perkalian%20dan%20penjumlahan%20diatas,lebih%20d ari%20dua%20buah%20percobaan. https://www.foldertips.com/tik/kombinatorika/ https://mathcyber1997.com/prinsip-inklusieksklusi/#:~:text=Prinsip%20inklusi%2Deksklusi%20(inclusio n%2D,diaplikasikan%20secara%20variatif%20pada%20kombi natorika.