Teknologi

Kombinatorika : Kaidah Dasar Menghitung, Permutasi & Kombinasi

Kombinatorika : permutasi & kombinasi merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.

Misalkan, Anda diminta untuk menghitung banyaknya kemungkinan yang dapat dibuat dari sandi-lewat (password) yang panjangnya 6 sampai 8 karakter, karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan sandi-lewat yang dapat dibuat?

  • abcdef
  • aaaade
  • a123fr
  • erhtgahn
  • yutresik
  • ????

Cara paling mudah untuk menyelesaikan persoalan semacam di atas adalah dengan mengenumerasi semua kemungkinan jawabannya. Mengenumerasi artinya mencacah atau menghitung (count) satu persatu setiap kemungkinan jawaban. Tetapi, mungkin Anda sudah lelah sebelum usaha mengenumerasi semua kemungkinan jawaban.

Di sinilah peran kombinatorial, yaitu seni berhitung menyelesaikan persoalan semacam ini dengan cepat.

A. Kaidah Dasar Menghitung

  1. Kaidah Perkalian (rule of product).
  2. Kaidah Penjumlahan (rule of sum).

1. Kaidah Perkalian

Misal :

  • Percobaan 1 :  p hasil
  • Percobaan 2 :  q hasil
  • Maka, percobaan 1 dan percobaan 2 = p x q hasil

2. Kaidah Penjumlahan

Misal :

  • Percobaan 1 :  p hasil
  • Percobaan 2 :  q hasil
  • Maka, percobaan 1 atau percobaan 2 = p + q hasil

Perluasan Kaidah Dasar Menghitung

Misalkan ada n percobaan, masing-masing dengan pi hasil.

  1. Kaidah perkalian (rule of product) :
    pi x pi x … pn hasil
  2. Kaidah penjumlahan (rule of sum) :
    pi + pi + … pn hasil

Contoh :

1. Ketua kelas TI-A hanya 1 orang (pria atau wanita, tidak bias gender). Jumlah pria = 65 orang dan jumlah wanita = 15 orang. Berapa banyak cara memilih ketua kelas?
Penyelesaian :
Karena yang dipilih hanya 1 orang dan tidak bias gender, maka ada 65 + 15 = 80 cara untuk memilih ketua kelas.
2. Dua orang perwakilan TI-A mendatangi dosen untuk protes nilai kuis. Wakil yang dipilih 1 orang pria dan 1 orang wanita. Berapa banyak cara untuk memilih 2 orang wakil tersebut?
Penyelesaian :
Setiap pria dipasangkan dengan masing-masing dengan 15 orang wanita, sehingga 65 orang pria dipasangkan masing-masing dengan 15 orang wanita. Artinya, ada 65 x 15 = 975 cara untuk memilih 2 orang wakil tersebut.
3. Bit biner hanya 0 dan 1. Berapa banyak string biner yang dapat dibentuk jika :
a. Panjang string 5 bit;
b. Panjang string 8 bit (=1 byte)
Penyelesaian :
a. 2 x 2 x 2 x 2 x 2 = 25 = 32
b. 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 28 = 256
4. Berapa banyak bilangan ganjil antara 1000 s.d. 9999 (termasuk 1000 dan 9999 itu sendiri), jika :
(i) Boleh ada angka berulang;
(ii) Tidak boleh ada angka berulang.
Penyelesaian :
(i) 9 x 10 x 10 x 5
(ii) 8 x 8 x 7 x 5
5. Sandi-lewat (password) sistem komputer panjangnya 6 s.d. 8 karakter Tiap karakter boleh berupa huruf atau angka; huruf besar kecil tidak dibedakan. Berapa banyak sandi-lewat yang dapat dibuat?
Penyelesaian :
Banyak huruf alfabet = 26 (A – Z), banyak angka desimal = 10 (0 – 9), jadi seluruhnya ada 36 karakter.
– Sandi-lewat 6 karakter = 36 x 36 x 36 x 36 x 36 x 36 = 366
– Sandi-lewat 7 karakter = 36 x 36 x 36 x 36 x 36 x 36 x 36 = 367
– Sandi-lewat 8 karakter = 36 x 36 x 36 x 36 x 36 x 36 x 36 x 36 = 368
Total ada 366 + 367 + 368 sandi-lewat yang bisa dibuat.

Latihan 1

  1. Jika ada 10 pertanyaan yang masing-masing bisa dijawab benar atau salah (B atau S), berapakah kemungkinan kombinasi jawaban yang dapat dibuat?
  2. Plat nomor memuat 2 huruf diikuti 3 angka dengan digit pertama tidak sama dengan 0. Ada berapa plat nomor berbeda ?
    • (i) Angka dan huruf boleh berulang;
    • (ii) Angka dan huruf tidak boleh berulang.
  3. Tentukan  cara agar sebuah organisasi yang terdiri dari 26 anggota dapat memilih ketua, sekretaris, dan bendahara dengan catatan tidak ada jabatan rangkap.
  4. Terdapat 4 jalur bus antara A dan B dan 3 jalur bus dari B ke C. Tentukan banyaknya cara agar seseorang dapat berpergian dengan bus dari A ke C melewati B.
    • (i) Hanya pergi saja;
    • (ii) Pulang dan pergi;
    • (iii) Tidak boleh pulang dengan jalur yang sama.
  5. Suatu kemeja merk tertentu memiliki 12 warna pilihan, memiliki versi untuk pria dan wanita, serta 2 ukuran untuk tiap-tiap versi. Berapa banyak tipe kemeja yang dibuat?
  6. Sebuah perpustakaan memiliki 6 buah buku berbahasa Inggris, 8 buah buku berbahasa Perancis, dan 10 buah buku berbahasa Jerman. Masing-masing buku berbeda judulnya.
    Berapa jumlah cara memilih :
    • (i) 3 buah buku, masing-masing dari tiap bahasa berbeda;
    • (ii) 1 buah buku (sembarang bahasa).
  7. Suatu bilangan dibentuk dari angka-angka 2, 3, 4, 5, 7, 8 dan 9. Misalkan pengulangan angka tidak dibolehkan, berapa banyak bilangan 4 angka yang kurang dari 5000 namun habis dibagi 5 yang dapat dibentuk dari angka-angka tersebut?
  8. Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan 1 1 atau berakhir dengan 1 1?
KUNCI JAWABAN
pass : foldertips.com

B. Permutasi

Permutasi adalah jumlah urutan 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 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!

1. Berapa jumlah urutan berbeda yang mungkin dibuat dari penempatan bola merah, biru, putih ke dalam kotak 1, 2, 3 ?
Permutasi Kombinatorial
Penyelesaian :
Jumlah kemungkinan urutan berbeda dari penempatan bola ke dalam kotak adalah: 3 x 2 x 1 = 3! = 6
2. Berapa banyak cara penyusunan 15 puzzle seperti contoh di bawah ini?
Contoh soal puzzle permutasi
Ingat, kotak kosong juga merupakan sebuah objek, sehingga ada : P(16,16) = 16!

1. Permutasi n dari r elemen

Permutasi r dari n elemen adalah jumlah kemungkinan urutan r buah elemen yang dipilih dari n buah elemen, dengan r n, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada elemen yang sama.

Jika jumlah objek dengan jumlah tempat berbeda, maka konsepnya sedikit bergeser, tidak n! (tidak sampai x 1), tetapi sebanyak jumlah objek dikurangi jumlah tempat karena akan ada objek yang tidak bisa dimasukkan ke dalam karena keterbatasan tempat.

Sehingga, rumus permutasi adalah :

rumus permutasi

Contoh :

1. 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.
Penyelesaian :
(i) P(5, 3) = 5! / (5 – 3)! = 5! / 2! = 60
(ii) Tidak dapat diselesaikan dengan rumus permutasi, tetapi dengan kaidah perkalian yaitu : 5 x 5 x 5 = 53 = 125
Catatan :
Persoalan 1.a juga bisa diselesaikan dengan kaidah perkalian, yaitu :
_ _ _ = ?
Digit pertama = ada 5 angka yaitu : 1, 2, 3, 4, 5
Digit kedua = ada 4 angka karena satu angka telah digunakan : 1, 2, 3, 4
Digit ketiga = ada 3 angka karena dua angka telah digunakan : 1, 2, 3
Sehingga, 5 x 4 x 3 = 60

2. Permutasi dengan perulangan

Permutasi dengan adanya elemen yang sama.

Banyaknya permutasi dari n objek dari n1 yang sama, n2 yang sama, … nr yang sama adalah :

rumus permutasi dengan perulangan

Contoh :

1. Tentukan banyaknya kata yang dapat dibentuk dari kata “DISKRIT”.
Penyelesaian :
Jumlah n karakter = 7
D = 1; I = 2; S = 1; K = 1; R = 1; T = 1
Sehingga :
7! / (1! 2! 1! 1! 1! 1!) = 7! / 2!
2. Berapa banyak string yang bisa dibentuk menggunakan huruf-huruf dari kata MISSISSIPPI?
Penyelesaian :
Jumlah n karakter = 11
M = 1; I = 4; S = 4; P = 2
Sehingga : 11! / (1! 4! 4! 2!)
3. Dua belas lembar karton akan diwarnai sehingga 3 diantaranya berwarna hijau, 2 berwarna merah, 2 berwarna kuning, dan sisanya berwarna biru. Berapa jumlah cara pengecatan?
Penyelesaian :
Jumlah n lembar = 12
Hijau = 3
Merah = 2
Kuning = 2
Biru = 5

= 12! / (3! 2! 2! 5!)

4. Dua belas buah lampu berwarna (4 merah, 3 putih, dan 5 biru) dipasang pada 18 buah soket dalam sebuah baris (sisanya 6 buah soket dibiarkan kosong). Berapa jumlah cara pengaturan lampu?
Penyelesaian :
Jumlah n buah soket = 18
Merah = 4
Putih = 3
Biru = 5
Kosong = 6

= 18! / (4! 3! 5! 6!)

5. Berapa banyak cara membagikan 8 buah buku berbeda kepada 3 orang mahasiswa, bila Billy mendapat 4 buah buku, Andi dan Toni masing-masing memperoleh 2 buah buku.
Penyelesaian :
Jumlah n buku = 8
Billy = 4
Andi = 2
Toni = 2

= 8! / (4! 2! 2!)

Latihan 2

  1. Kode buku di sebuah perpustakaan panjangnya 7 karakter, terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka yang berbeda pula.
  2. Berapa banyak bilangan berdigit 3 yang bisa dibentuk dari 6 angka 2, 3, 4, 5, 7, 9 dan pengulangan tidak diperbolehkan.
  3. Berapa banyak bilangan berdigit 3 kurang dari 400 yang bisa dibentuk dari 6 angka 2, 3, 4, 5, 7,9 dan pengulangan tidak diperbolehkan?
  4. Berapa banyak bilangan berdigit 3 yang genap dan bisa dibentuk dari 6 angka 2, 3, 4, 5, 7, 9 dan pengulangan tidak diperbolehkan?
  5. Berapa banyak bilangan berdigit 3 yang ganjil dan bisa dibentuk dari 6 angka 2, 3, 4, 5, 7, 9 dan pengulangan tidak diperbolehkan?
  6. Selesaikan soal berikut ini :
    • (i) Berapa banyak bilangan genap 2 angka?
    • (ii) Berapa banyak bilangan ganjil 2 angka dengan setiap angka berbeda?
  7. Suatu bilangan dibentuk dari angka 2, 3, 4, 5, 7, 8 dan 9. Berapa banyak bilangan 4 angka yang kurang dari 5000, namun habis dibagi 5?
    • (i) Angka boleh berulang;
    • (ii) Angka tidak boleh berulang.
  8. Jabatan ketua himpunan dapat diduduki oleh mahasiswa angkatan tahun 1997 atau angkatan tahun 1998. Jika terdapat 45 orang mahasiswa angkatan 1997 dan 52 orang mahasiswa angkatan 1998, berapa cara memilih pejabat ketua himpunan?
  9. Sekelompok mahasiswa terdiri atas 4 orang pria dan 3 orang wanita. Berapa jumlah cara memilih satu orang yang mewakili kelompok tersebut, tidak perduli pria atau wanita?
  10. Misalkan himpunan A = {a, b, c, d, e} dan himpunan B = {1, 2, 3}. Berapa banyak pasangan terurut (ordered pairs) yang dapat dibentuk antara anggota himpunan A dengan anggota himpunan B (yaitu A x B)?
  11. Kursi-kursi di aula akan diberi nomor dengan huru diikuti dengan bilangan bulat positf yang tidak lebih dari 50 (misalnya A12, B36, dst). Berapa jumlah maksimum kursi yang dapat diberi dinomori?
  12. Terdapat 4 rute yang dapat dilalui dari A ke B, dan 3 rute dari B ke C.
    • Berapa banyak cara seseorang dapat bepergian dari A ke C melalui B?
    • Berapa banyak cara seseorang dapat bepergian pulang-pergi dari A ke C melalui B?
    • Berapa banyak cara seseorang dapat bepergian pulang-pergi dari A ke C melalui B dengan syarat tidak boleh melalui rute yang sama?
  13. Berapa banyak jumlah kata 5 huruf yang dapat dibentuk dari huruf a, b, c, d, e jika :
    • Tidak boleh ada huruf yang berulang;
    • Boleh ada huruf yang berulang;
    • Pada soal (a), diawali huruf a?
    • Pada soal (a), tidak diawali huruf a?
  14. Sebuah perpustakaan memiliki 6 buah buku berbahasa Inggris, 8 buah buku berbahasa Perancis, dan 10 buah buku berbahasa Jerman. Masing-masing buku berbeda judulnya. Berapa jumlah cara memilih :
    • 3 buah buku, masing-masing dari tiap bahasa berbeda; dan
    • 1 buah buku sembarang bahasa.
  15. Berapa banyak “kata” yang terbentuk dari kata “BOSAN”?
  16. Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
  17. Tiga buah ujian dilakukan dalam suatu periode enam hari (Senin s.d. Sabtu). Berapa banyak pengaturan jadwal yang dapat dilakukan sehingga tidak ada dua ujian atau lebih yang dilakukan pada hari yang sama.
  18. Sebuah bioskop mempunyai jajaran kursi yang disusun per baris. Tiap baris terdiri dari 6 tempat kursi. Jika dua orang akan duduk, berapa banyak pengaturan tempat duduk yang mungkin pada suatu baris?
  19. Berapa banyak string yang dapat dibentuk yang terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka berbeda pula?
  20. Berapakah banyak string yang dibentuk dari permutasi huruf-huruf pada kata  sedemikian sehingga huruf-huruf vokal terletak pada posisi saling bersebelahan?
KUNCI JAWABAN
pass : foldertips.com

C. Kombinasi

Kombinasi merupakan bentuk khusus dari permutasi.

Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Misalnya, acb, bca, dan acb dianggap sama dan dihitung sekali.

Kombinasi Kombinatorial

Rumus Kombinasi :

rumus kombinasi kombinatorika

Interpretasi Kombinasi

1. Persoalan kombinasi, C(n, r) sama dengan menghitung banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dengan n elemen.
Dua atau lebih himpunan bagian dengan elemen-elemen yang sama dianggap sebagai himpunan yang sama, meski urutan elemen-elemennya berbeda.
Misalkan A = {1, 2, 3}. Jumlah himpunan bagian dengan 2 elemen yang dapat dibentuk dari himpunan A ada 3 buah, yaitu :
{1, 2} = (2, 1}
{1, 3} = (3, 1}
{2, 3} = {3, 2}

Ingat bahwa anggota pada himpunan tidak memperhatikan urutannya.

Dengan rumus kombinasi diperoleh :
C(3, 2) = 3! / (3-2)! 2! = 3

2. Persoalan kombinasi C(n, r) dapat dipandang sebagai cara memilih r buah eleman dari n buah elemen yang ada, tetapi urutan elemen di dalam susunan hasil pemilihan tidak penting.

Contoh :
Sebuah club memiliki 25 orang anggota. Kita akan memilih lima orang sebagai panitia. Panitia atau komite adalah kelompok yang tidak terurut, artinya setiap anggota di dalam panitia kedudukannya sama. Misalnya jika ada 5 orang terpilih, A,B,C,D, dan E, maka urutan penempatan masing-masingnya di dalam panitia tidak penting (ABCDE sama saja dengan BACED, ADCEB, dst).

Penyelesaian :
C(25, 5) = 25! / (25-5)! 5! = 53.150 cara

Kombinasi dengan Pengulangan

Meninjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.

  • Jika masing-masing kotak hanya boleh diisi paling banyak 1 bola, maka jumlah cara memasukkan bola ke dalam kotak adalah C(n, r);
  • Jika masing-masing kotak boleh lebih dari 1 bola (tidak ada jumlah pembatasan bola), maka jumlah cara memasukkan bola ke dalam kotak adalah C(n + r – 1, r).

Contoh :

1. Persamaan x1 + x2 + x3 + x4 = 12, xi adalah bilangan bulat ≥ 0. Berapa jumlah kemungkinan solusi?
Penyelesaian :
Analogikan 12 buah bola akan dimasukkan ke dalam 4 buah kotak (n = 4 dan r = 12). Setiap kotak mungkin akan diisi 1 bola, atau 2 bola, atau .., atau +12 bola, atau tidak sama sekali, yang penting jumlah seluruh bola di dalam seluruh kotak tetap 12 buah.
Banyak sekali jumlah susunan yang mungkin, tetapi seluruhnya bisa dihitung :
C(n + r – 1, r) = C(4 + 12 – 1, 12) = C(15, 12)
2. Melanjutnya soal pertama, bila dipersyaratkan x1 > x2 > x3 > 2 dan x4 ≥ 0 ? Berapa kemungkinan solusi?
Penyelesaian :
Kotak 1, diisi minimal 1 bola;
Kotak 2, diisi minimal 2 bola;
Kotak 3, diisi minimal 3 bola;
Kotak 4, boleh kosong.
Mula-mula, isi kotak 1,2,3 masing-masing 1,2,3 bola. Sisa bola ada 6, untuk diisi ke 4 kotak, sehingga C(n + r – 1, r) = C(4 + 6 – 1, 6) = C(9, 6)
3. Dua puluh buah apel dan 15 buah jeruk dibagikan kepada 5 orang anak, tiap anak boleh mendapat lebih dari 1 buah apel dan jeruk, atau tidak sama sekali. Berapa jumlah pembagian yang dapat dilakukan?
Penyelesaian :
Untuk pembagian apel = C(5 + 20 – 1, 20) = C(24, 20)
Untuk pembagian jeruk = C(5 + 15 – 1, 15) = C(19, 15)
Karena setiap anak mendapat apel dan jeruk, maka pembagian kedua buah tersebut adalah : C(24, 20) x C(19, 15)
4. Toko roti “Enak” menjual 8 jenis roti. Berapa jumlah cara mengambil 1 lusin roti ?
Penyelesaian :
Analogikan 8 jenis roti sebagai 8 kotak. Kita akan mendistribusikan 12 roti ke dalam 8 kotak. Setiap kotak mungkin berisi lebih dari 1 buah roti. Di sini n = 8 dan r = 12, maka jumlah cara memilih 12 buah roti itu sama dengan jumlah cara memasukkan 12 buah roti ke dalam 8, yaitu : C(8 + 12 – 1, 12) = C(19, 12)
5. Andaikan terdapat kumpulan bola yang berwarna merah, biru, dan hijau. Jumlah bola dari masing-masing warna paling sedikit jumlahnya 8 buah.
(i) Berapa banyak cara memilih 8 buah bola (tanpa ada batasan warna)?
(ii) Berapa banyak cara memilih 8 buah bola jika paling sedikit 1 bola dari masing-masing warna terwakili?
Penyelesaian :
(i) n = 3, r = 8, maka C(10, 8)
(ii) Ambil terlebih dahulu 1 bola dari masing-masing warna, kemudian ambil 5 bola sisanya. Jadi jumlah cara seluruhnya adalah C(3 + 5 – 1, 5) = C(7, 5)

Latihan 3

  1. Ada berapa cara kita dapat memilih 3 dari 4 elemen himpunan A = {a, b, c, d}?
  2. Berapa banyak cara menyusun menu nasi goreng tiga kali seminggu untuk sarapan pagi?
  3. String biner yang panjangnya 32 bit disusun oleh angka 1 dan 0. Berapa banyak string biner yang tepat berisi 7 buah bit 1?
  4. Sebuah koin yang mempunyai sisi A dan sisi B dilempar ke atas sebanyak 4 kali. Berapakah jumlah kemungkinan munculnya sisi A sebanyak 3 kali?
  5. Sebuah karakter dalam sistem ASCII berukuran 1 byte atau 8 bit (1 atau 0).
    • Berapa banyak pola bit yang terbentuk? (atau berapa banyak karakter yang dapat dipresentasikan)
    • Berapa banyak pola bit yang mempunyai 3 bit 1?
    • Berapa banyak pola bit yang mempunyai bit 1 sejumlah genap?
  6. Diantara 10 orang mahasiswa, berapa banyak cara membentuk perwakilan 5 orang sedemikian sehingga :
    • mahasiswa bernama A selalu termasuk di dalamnya;
    • mahasiswa bernama A tidak termasuk di dalamnya;
    • mahasiswa bernama A selalu termasuk di dalamnya, tetapi B tidak;
    • mahasiswa bernama B selalu termasuk di dalamnya, tetapi A tidak;
    • mahasiswa A dan B termasuk di dalamnya;
    • setidaknya salah satu dari mahasiswa yang bernama A dan B termasuk di dalamnya.
  7. 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?
  8. Tiga buah apartemen A, B, C disewakan untuk mahasiswa. Tiap unit apartemen dapat menampung 3 orang atau 4 orang mahasiswa. Berapa jumlah cara menyewakan apartemen kepada 10 orang mahasiswa?
KUNCI JAWABAN
PASS : Foldertips.com

Demikian artikel Kombinatorika : Kaidah Dasar Menghitung, Permutasi & Kombinasi.

Semoga bermanfaat..!

The post Kombinatorika : Kaidah Dasar Menghitung, Permutasi & Kombinasi appeared first on F-Tips.