Makalah Matematika Diskrit Teori Kombinatorikal
07.12.00
MAKALAH
MATEMATIKA DISKRIT
“ TEORI KOMBINATORIKAL”
Disusun
Oleh:
1. Nurus Syarifatul
Ngaeni
2.
Eman Setiaji
STIMIK
Tunas Bangsa Banjarnegara
Mata
Kuliah : Matematika Diskrit
Dosen : Bu Ismi
TEORI KOMBINATORIAL
Teori Kombinatorial merupakan salah satu pokok bahasan Matematika Diskrit yang telah banyak dikembangkan dan diaplikasikan dalam berbagai bidang. Dalam perkembangan Matematika, dapat dilihat bahwa kajian kombinatorial sangat menarik bagi sebagian orang. Salah satu contoh permasalahan yang dapat diselesaikan dengan kombinatorial adalah menghitung banyaknya kombinasi angka nomor polisi mobil, di mana nomor polisi terdiri atas lima angka dan diikuti dua huruf, serta angka pertama bukan nol.
Cara paling sederhana untuk menyelesaikan persolan sejenis adalah dengan mengenumerasi semua kemungkinan jawabannya. Mengenumerasi berarti mencacah atau menghitung satu per satu setiap kemungkinan jawaban. Akan tetapi enumerasi masih mungkin dilakukan jika jumlah objek sedikit, sedangkan untuk persoalan di atas, cara enumerasi jelas tidak efisien. Misalnya untuk menjawab persoalan di atas, apabila kita melakukan enumerasi, maka kemungkinan jawabannya adalah sebagai berikut:
12345AB
12345AC
12345BC
…
34567MT
34567ML
…
dan seterusnya…
Sangatlah mungkin bahwa kita sudah lelah sebelum proses enumerasi selesai dilakukan. Di sinilah peran kombinatorial, yang merupakan “seni berhitung”, menyelesaikan persoalan semacam ini dengan cepat..
Teori Kombinatorial merupakan salah satu pokok bahasan Matematika Diskrit yang telah banyak dikembangkan dan diaplikasikan dalam berbagai bidang. Dalam perkembangan Matematika, dapat dilihat bahwa kajian kombinatorial sangat menarik bagi sebagian orang. Salah satu contoh permasalahan yang dapat diselesaikan dengan kombinatorial adalah menghitung banyaknya kombinasi angka nomor polisi mobil, di mana nomor polisi terdiri atas lima angka dan diikuti dua huruf, serta angka pertama bukan nol.
Cara paling sederhana untuk menyelesaikan persolan sejenis adalah dengan mengenumerasi semua kemungkinan jawabannya. Mengenumerasi berarti mencacah atau menghitung satu per satu setiap kemungkinan jawaban. Akan tetapi enumerasi masih mungkin dilakukan jika jumlah objek sedikit, sedangkan untuk persoalan di atas, cara enumerasi jelas tidak efisien. Misalnya untuk menjawab persoalan di atas, apabila kita melakukan enumerasi, maka kemungkinan jawabannya adalah sebagai berikut:
12345AB
12345AC
12345BC
…
34567MT
34567ML
…
dan seterusnya…
Sangatlah mungkin bahwa kita sudah lelah sebelum proses enumerasi selesai dilakukan. Di sinilah peran kombinatorial, yang merupakan “seni berhitung”, menyelesaikan persoalan semacam ini dengan cepat..
Teori
Kombinatorial
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.
Kaidah Dasar
Menghitung
1. Kaidah Perkalian (rule of product)
Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 dan percobaan 2 dilakukan akan terdapat p × q hasil percobaan.
2. Kaidah Penjumlahan (rule of sum)
Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 atau percobaan 2 dilakukan (hanya salah satu percobaan saja yang
dilakukan) akan terdapat p + q hasil percobaan.
Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi kaidah perkalian.
Misalkan jumlah objek adalah n, maka
Urutan pertama dipilih dari n objek,
urutan kedua dipilih dari (n – 1) objek,
urutan kedua 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!
Rumus permutasi-r (jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek), dilambangkan dengan P(n,r):
1. Kaidah Perkalian (rule of product)
Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 dan percobaan 2 dilakukan akan terdapat p × q hasil percobaan.
2. Kaidah Penjumlahan (rule of sum)
Misalkan percobaan 1 mempunyai p hasil percobaan, dan percobaan 2 mempunyai q hasil, maka bila percobaan 1 atau percobaan 2 dilakukan (hanya salah satu percobaan saja yang
dilakukan) akan terdapat p + q hasil percobaan.
Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi kaidah perkalian.
Misalkan jumlah objek adalah n, maka
Urutan pertama dipilih dari n objek,
urutan kedua dipilih dari (n – 1) objek,
urutan kedua 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!
Rumus permutasi-r (jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek), dilambangkan dengan P(n,r):
Kombinasi
Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan.
Rumus kombinasi-r (jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen), dilambangkan dengan C(n,r) atau ( n r ) .
Interpretasi Kombinasi
1. C(n, r) = banyaknya himpunan bagian yang terdiri atas r elemen yang dapat dibentuk dari
himpunan dengan n elemen.
2. C(n, r) = cara memilih r buah elemen dari n elemen yang ada, tetapi urutan elemen di dalam
susunan hasil pemilihan tidak penting.
Permutasi dan Kombinasi Bentuk Umum
Misalkan terdapat n buah bola yang tidak seluruhnya berbeda warna (ada beberapa bola berwarna sama – indistinguishable).
n1 bola di antaranya berwarna 1,
n2 bola di antaranya berwarna 2,
…
nk bola di antaranya berwarna k,
dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimal 1 buah bola)?
Penyelesaian:
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n buah bola ke dalam n buah kotak adalah P(n, n) = n!
Dari pengaturan n buah bola itu,
Terdapat n1! cara memasukkan bola berwarna 1,
terdapat n2! cara memasukkan bola berwarna 2,
…
terdapat nk! cara memasukkan bola berwarna k.
Permutasi n buah bola yang mana n1 di antaranya berwarna 1, n2 bola berwarna 2, …, nk bola berwarna k adalah
Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan.
Rumus kombinasi-r (jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen), dilambangkan dengan C(n,r) atau ( n r ) .
Interpretasi Kombinasi
1. C(n, r) = banyaknya himpunan bagian yang terdiri atas r elemen yang dapat dibentuk dari
himpunan dengan n elemen.
2. C(n, r) = cara memilih r buah elemen dari n elemen yang ada, tetapi urutan elemen di dalam
susunan hasil pemilihan tidak penting.
Permutasi dan Kombinasi Bentuk Umum
Misalkan terdapat n buah bola yang tidak seluruhnya berbeda warna (ada beberapa bola berwarna sama – indistinguishable).
n1 bola di antaranya berwarna 1,
n2 bola di antaranya berwarna 2,
…
nk bola di antaranya berwarna k,
dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maksimal 1 buah bola)?
Penyelesaian:
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan n buah bola ke dalam n buah kotak adalah P(n, n) = n!
Dari pengaturan n buah bola itu,
Terdapat n1! cara memasukkan bola berwarna 1,
terdapat n2! cara memasukkan bola berwarna 2,
…
terdapat nk! cara memasukkan bola berwarna k.
Permutasi n buah bola yang mana n1 di antaranya berwarna 1, n2 bola berwarna 2, …, nk bola berwarna k adalah
Kombinasi
dengan Pengulangan
Misalkan terdapat r buah bola yang semua warnanya sama dan terdapat n buah kotak, serta ketentuan sebagai berikut:
1. Masing-masing kotak hanya boleh diisi paling banyak satu buah bola.
Jumlah cara memasukkan bola adalah C(n, r).
2. Masing-masing kotak boleh diisi lebih dari satu buah bola (tidak ada pembatasan jumlah bola).
Jumlah cara memasukkan bola adalah:
Misalkan terdapat r buah bola yang semua warnanya sama dan terdapat n buah kotak, serta ketentuan sebagai berikut:
1. Masing-masing kotak hanya boleh diisi paling banyak satu buah bola.
Jumlah cara memasukkan bola adalah C(n, r).
2. Masing-masing kotak boleh diisi lebih dari satu buah bola (tidak ada pembatasan jumlah bola).
Jumlah cara memasukkan bola adalah:
Teori
Peluang
Kombinatorial dan teori peluang (probability) berkaitan sangat erat. Teori peluang banyak menggunakan konsep-konsep dalam kombinatorial. Sebenarnya kedua bidang ini lahir dari arena judi (gambling games) – salah satu kasusnya adalah menghitung peluang munculnya nomor lotre tertentu. Meskipun demikian, aplikasi kombinatorial dan teori peluang saat ini telah meluas ke berbagai bidang ilmu lain maupun dalam kehidupan nyata seperti ilmu statistika, fisika, ekonomi, biologi, dan berbagai bidang ilmu lainnya.
Terminologi
Dasar
Ruang Contoh (sample space)
Ruang Contoh dari suatu percobaan adalah himpunan semua kemungkinan hasil percobaan yang bersangkutan.
Titik Contoh (sample point)
Titik Contoh adalah setiap hasil percobaan di dalam ruang contoh. Hasil-hasil percobaan tersebut bersifat saling terpisah (mutually exclusive) karena dari seluruh ruang contoh, hanya satu titik contoh yang muncul.
Ruang Contoh
Diskrit (discrete sample space)
Ruang Contoh Diskrit adalah ruang contoh yang jumlah anggotanya terbatas. Misalkan ruang contoh dilambangkan dengan S dan titik-titik contohnya dilambangkan dengan x1, x2, …, maka
S = { x1, x2, …, xi, … }Menyatakan ruang contoh S yang terdiri atas titik-titik contoh x1, x2, …, xi, dan seterusnya.
Ruang Contoh Diskrit adalah ruang contoh yang jumlah anggotanya terbatas. Misalkan ruang contoh dilambangkan dengan S dan titik-titik contohnya dilambangkan dengan x1, x2, …, maka
S = { x1, x2, …, xi, … }Menyatakan ruang contoh S yang terdiri atas titik-titik contoh x1, x2, …, xi, dan seterusnya.
Peluang Diskrit
Peluang Diskrit adalah peluang terjadinya sebuah titik contoh, dan disimbolkan dengan p(xi).
Kejadian (event)
Kejadian
–disimbolkan dengan E– adalah himpunan bagian dari ruang contoh. Misalnya pada
percobaan melempar dadu, kejadian munculnya angka ganjil adalah E = {1,3,5},
kejadian munculnya angka 1 adalah E = {1}.
Kejadian yang hanya mengandung satu titik contoh disebut kejadian sederhana (simple event), sedangkan kejadian yang mengandung lebih dari satu titik contoh disebut kejadian majemuk (compound event).
Kejadian yang hanya mengandung satu titik contoh disebut kejadian sederhana (simple event), sedangkan kejadian yang mengandung lebih dari satu titik contoh disebut kejadian majemuk (compound event).
Peluang
Kejadian
Peluang Kejadian E di dalam ruang contoh S dapat diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa
Peluang Kejadian E di dalam ruang contoh S dapat diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa
.jpg)
0 komentar