Materi Kombinatorik SMA 2019 [PDF]

Citation preview

LEMBAGA OLIMPIADE PENDIDIKAN INDONESIA Jl. Raya Jatiwaringin No. 8, Jakarta Timur, DKI Jakarta 13620 Telp: 021-8605257, 0813 24000 5000, www.lopi.co.id| [email protected]



LECTURE 4 PROBABILITAS DAN KOMBINATORIK Kombinasi dan Permutasi Kombinasi merupakan banyak cara menyusun sejumlah objek tanpa memperhatikan urutan objek tersebut. Jenis – Jenis Kombinasi: 



Kombinasi Tidak Berulang Apabila tidak terdapat objek yang dihitung secara berulang – ulang maka: 𝑇𝑜𝑡𝑎𝑙 𝐾𝑜𝑚𝑏𝑖𝑛𝑎𝑠𝑖 = 𝐶𝑘𝑛 =







𝑛! 𝑘! (𝑛 − 𝑘)!



Kombinasi Berulang Apabila terdapat objek yang dihitung secara berulang – ulang maka: 𝑇𝑜𝑡𝑎𝑙 𝐾𝑜𝑚𝑏𝑖𝑛𝑎𝑠𝑖 = 𝐶𝑘𝑛+𝑘−1 =



(𝑛 + 𝑘 − 1)! 𝑘! (𝑛 − 1)!



Permutasi merupakan banyaknya cara menyusun sejumlah objek dengan memperhatikan urutan dari objek tersebut. Jenis – Jenis Permutasi: 



Permutasi Tidak Berulang Apabila tidak terdapat objek yang dihitung secara berulang – ulang maka: 𝑇𝑜𝑡𝑎𝑙 𝑃𝑒𝑟𝑚𝑢𝑡𝑎𝑠𝑖 = 𝑃𝑘𝑛 =



𝑛! (𝑛 − 𝑘)!



Apabila terdapat beberapa objek sama di dalam 𝑛 objek maka: 𝑇𝑜𝑡𝑎𝑙 𝑃𝑒𝑟𝑚𝑢𝑡𝑎𝑠𝑖 = 𝐶𝑛𝑛𝑖 = 



𝑛! , 𝑛1 ! 𝑛2 ! … 𝑛𝑘 !



𝑖 = 1,2,3, … , 𝑘



Permutasi berulang Apabila terdapat objek yang dihitung secara berulang – ulang maka: 𝑇𝑜𝑡𝑎𝑙 𝑃𝑒𝑟𝑚𝑢𝑡𝑎𝑠𝑖 = 𝑛𝑘







Permutasi siklis Apabila susuna objek berbentuk siklis maka: 𝑇𝑜𝑡𝑎𝑙 𝑃𝑒𝑟𝑚𝑢𝑡𝑎𝑠𝑖 = (𝑛 − 1)!



1



LEMBAGA OLIMPIADE PENDIDIKAN INDONESIA Jl. Raya Jatiwaringin No. 8, Jakarta Timur, DKI Jakarta 13620 Telp: 021-8605257, 0813 24000 5000, www.lopi.co.id| [email protected] Prinsip Inklusi – Eksklusi (PIE) Prinsip Inklusi – Eksklusi merupakan suatu cara untuk menyusun objek sehingga menghindari perhitungan ganda (Double Counting). Bentuk umum: 𝑛



(𝐸1 ∪ 𝐸2 ∪ … ∪ 𝐸𝑛 ) = ∑ 𝐸𝑖 − 𝑖=1



∑ (𝐸𝑖 ∩ 𝐸𝑗 ) + ⋯ + (−1)𝑛+1 (𝐸1 ∩ 𝐸2 ∩ … ∩ 𝐸𝑛 ) 1≤𝑖 𝑥 − 1 maka paling sedikit terdapat salah satu dari 𝑥𝑖 ≥ 𝑥 untuk 𝑖 = 1, 2, … , 𝑛



3



LEMBAGA OLIMPIADE PENDIDIKAN INDONESIA Jl. Raya Jatiwaringin No. 8, Jakarta Timur, DKI Jakarta 13620 Telp: 021-8605257, 0813 24000 5000, www.lopi.co.id| [email protected] Baye’s Theorem Misalkan peluang kejadian 𝐴 dan kejadian 𝐵 berturut – turut dapat dinyatakan dengan 𝑃(𝐴) dan 𝑃(𝐵), jika kejadian 𝐴 bergantung pada kejadian 𝐵 maka: 𝑃(𝐴|𝐵) =



𝑃(𝐴 ∩ 𝐵) , 𝑃(𝐵) ≠ 0 𝑃(𝐵)



Dimana 𝑃(𝐴 ∪ 𝐵) = 𝑃(𝐴) + 𝑃(𝐵) + 𝑃(𝐴 ∩ 𝐵). Dengan menggunakan Baye’s Theorem maka berlaku: 𝑃(𝐴|𝐵) =



𝑃(𝐴)𝑃(𝐵|𝐴) , 𝑃(𝐵) ≠ 0 𝑃(𝐵)



Untuk tiga kejadian, 𝑃(𝐴 ∩ 𝐵 ∩ 𝐶) = 𝑃(𝐴) ∙ 𝑃(𝐵|𝐴) ∙ 𝑃(𝐶|𝐴 ∩ 𝐵). Teori Graf Suatu graf 𝐺 didefinisikan sebagai pasangan 𝑉(𝐺) dan 𝐸(𝐺) dengan 𝑉(𝐺) merupakan himpunan berhingga elemen – elemen titik (vertice) dan 𝐸(𝐺) merupakan himpunan pasangan – pasangan dari elemen 𝑉(𝐺) yang disebut sisi (edge). Setiap garis yang berhubungan dengan satu atau dua titik disebut titik ujung. Garis yang berhubungan dengan satu titik disebut loop. Dua garis yang menghubungkan titik yang sama disebut garis paralel. Dua titik dikatakan berhubungan apabila terdapat garis yang menghubunkan keduanya. Titik yang tidak memiliki garis yang berhubungan dengan titik tersebut disebut titik terasing. Graf kosong merupakan graf yang tidak memiliki titik maupun garis. Graf berarah merupakan graf yang semua garisnya memiliki arah (Directed Graph). Graf tak berarah merupakan graf yang semua garisnya tidak memiliki arah. Graf sederhana (Simple Graph) merupakan graf tak berarah yang tidak memiliki loop maupun garis paralel. Graf lengkap (Complete Graph) merupakan graf sederhana 𝑛 titik dengan setiap 2 titik berbeda selalu dihubungkan dengan suatu garis. Notasi: 𝐾𝑛 . Banyaknya garis dalam suatu graf lengkap dengan 𝑛 titik adalah



𝑛(𝑛−1) . 2



Misalkan titik 𝑣 sebagai suatu titik dalam graf 𝐺. Derajat (Degree) titik 𝑣 merupakan jumlah sisi (edge) yang berhubungan dengan titik 𝑣. Notasi: 𝑑(𝑣). Derajat titik yang berhubungan pada sebuah loop adalah 2. Derajat total suatu graf 𝐺 merupakan jumlah derajat semua titik di dalam 𝐺. Derajat total suatu graf selalu genap, dapat dinyatakan: ∑ 𝑑(𝑣) = 2|𝐸| 𝑣∈𝑉



Untuk sembarang graf 𝐺, jumlah titik yang berderajat ganjil selalu genap. 4



LEMBAGA OLIMPIADE PENDIDIKAN INDONESIA Jl. Raya Jatiwaringin No. 8, Jakarta Timur, DKI Jakarta 13620 Telp: 021-8605257, 0813 24000 5000, www.lopi.co.id| [email protected] Graf lingkaran merupakan graf sederhana yang memiliki titik berderajat 2. Notasi: 𝐶𝑛 . Banyak sisi dari graf lingkaran adalah 𝑛. Graf teratur (Reguler Graph) merupakan graf yang memiliki titik berderajat sama. Untuk derajat setiap titik 𝑑, maka banyak sisi dari graf teratur adalah



𝑛𝑑 . 2



Graf bipartit (Bipartite Graph) merupakan graf yang himpunan titiknya dapat dipisahkan menjadi dua himpunan 𝑣1 dan 𝑣2 sedemikian rupa sehingga setiap sisi pada 𝐺 menghubungkan sebuah titik di 𝑣1 ke sebuah titik di 𝑣2 . Misalkan graf dapat dibagi menjadi ke dalam dua bagian yang jumlah titiknya 𝑚 dan 𝑛 sehingga dapat dinyatakan sebagai 𝐾𝑚,𝑛 . Graf planar (Planar Graph) merupakan graf yang dapat dibentuk ulang pada suatu bidang datar dengan sisi – sisi yang tidak saling memotong (bersilangan). Turan’s Theorem Untuk sembarang graf dengan 𝑛 titik sehingga graf 𝐺 tidak memiliki titik 𝑟 + 1 maka banyak sisi dari 𝐺 paling banyak: 𝑟 − 1 𝑛2 1 𝑛2 ( ) = (1 − ) 𝑟 2 𝑟 2



5