Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 3.5 Menghitung Multihimpunan

Subbagian Pratinjau Bagian

Selidiki!
Skittles tersedia dalam lima “rasa”. Ada berapa kemungkinan segenggam 8 Skittles yang berbeda?
🔗
Misalkan Anda telah memanggang 8 kue mangkuk identik untuk diberikan kepada lima dosen matematika diskret favorit Anda. Ada berapa cara untuk membagikan kue mangkuk tersebut?
🔗
Mengapa jawaban kedua pertanyaan pencacahan di atas sama?
🔗
🔗
Sekarang kita telah mengetahui cara menyelesaikan berbagai jenis masalah pencacahan. Jika setiap hasil dalam himpunan hasil yang kita cacah dapat direpresentasikan oleh suatu barisan, kita menghitungnya sebagai permutasi (jika suku-suku dalam barisan tidak berulang) atau menggunakan prinsip perkalian (jika berulang). Jika kita mencacah hasil yang susunan suku-sukunya tidak dibedakan (jika urutan tidak penting), kita memandang hasil itu sebagai himpunan dan menghitungnya sebagai kombinasi. Namun, himpunan tidak pernah mengizinkan suatu elemen berulang; setiap elemen berada dalam himpunan atau tidak.
🔗
Jadi, terdapat kekosongan yang mencolok dalam perangkat pencacahan kita. Bagaimana jika kita ingin mencacah hasil berupa koleksi suku yang urutan kemunculannya tidak kita bedakan, tetapi dapat memuat suatu suku lebih dari sekali? Dengan kata lain, bagaimana kita dapat melengkapi tabel berikut?
🔗
Susunan Dibedakan?
Ya Tidak
Pengulangan boleh Barisan
Prinsip Perkalian
\(n^k\)
Tanpa pengulangan Barisan
Permutasi
\(P(n,k)\) 		Himpunan
Kombinasi
\(\binom{n}{k}\)
Yang ingin kita cacah adalah sejenis struktur mirip himpunan, tetapi struktur yang memang mengizinkan elemen di dalamnya muncul lebih dari sekali. Struktur seperti itu disebut multihimpunan.
🔗

Definisi 3.5.1.

Multihimpunan adalah koleksi elemen tak terurut yang setiap elemennya dapat muncul berapa kali pun. Banyaknya kemunculan suatu elemen disebut multiplisitas elemen tersebut.
🔗
Multihimpunan ditulis dengan notasi yang sama seperti himpunan: daftar yang dipisahkan koma di dalam kurung kurawal, seperti \(\{1, 2, 2, 5\}\text{.}\)
🔗
🔗
Dalam bagian ini, kita akan menelaah bagaimana multihimpunan dapat digunakan untuk merepresentasikan beragam masalah pencacahan. Kemudian kita akan mengembangkan cara menerjemahkan multihimpunan menjadi jenis khusus string bit agar kita dapat menggunakan bilangan-bilangan dalam Segitiga Pascal untuk menghitung banyaknya multihimpunan.
🔗

Lembar Kerja Kegiatan Pratinjau

1.
Carilah koleksi benda-benda identik, misalnya uang logam atau gula batu. Ambil juga beberapa pemisah, yang dapat berupa tusuk gigi, batang korek api, atau pena.
🔗
Susun uang logam dalam satu baris. Kita akan membagi baris itu menjadi sejumlah kelompok dengan menempatkan tusuk gigi pada celah di antara uang logam. Kita akan membedakan urutan kelompok-kelompok tersebut. Sebagai contoh, dua cara berbeda untuk membagi 7 uang logam menjadi 4 kelompok akan tampak seperti berikut:
🔗
dua baris yang masing-masing berisi 7 uang logam, dipisahkan menjadi 4 kelompok oleh 3 batang
Kita mengizinkan satu atau lebih kelompok tidak berisi uang logam (dengan menempatkan dua tusuk gigi berdampingan, atau menempatkannya sebelum atau sesudah semua uang logam).
🔗
Dengan menyusun uang logam dan batang dalam jumlah yang tepat, hitung banyaknya cara membagi sebaris uang logam menjadi sejumlah kelompok yang diberikan.
🔗
(a)
Jika Anda ingin membagi sebaris uang logam menjadi 4 kelompok, berapa tusuk gigi yang Anda perlukan?
🔗
🔗
(b)
Ada berapa cara untuk memisahkan sebaris tiga uang logam menjadi dua kelompok?
🔗
🔗
(c)
Ada berapa cara untuk memisahkan sebaris empat uang logam menjadi dua kelompok?
🔗
🔗
(d)
Ada berapa cara untuk memisahkan sebaris lima uang logam menjadi dua kelompok?
🔗
🔗
(e)
Ada berapa cara untuk memisahkan sebaris tiga uang logam menjadi tiga kelompok?
🔗
🔗
(f)
Ada berapa cara untuk memisahkan sebaris empat uang logam menjadi tiga kelompok?
🔗
🔗
(g)
Ada berapa cara untuk memisahkan sebaris lima uang logam menjadi tiga kelompok?
🔗
🔗
(h)
Berdasarkan jawaban Anda di atas, buatlah konjektur tentang banyaknya cara untuk memisahkan sebaris tujuh uang logam menjadi empat kelompok.
🔗
Petunjuk.
Carilah bilangan-bilangan yang Anda peroleh pada pertanyaan sebelumnya di Segitiga Pascal.
🔗
🔗
🔗
🔗
🔗
🔗

Subbagian Silakan Ambil Kue

Perhatikan masalah pencacahan berikut:
🔗
Anda memiliki 7 kue untuk diberikan kepada 4 anak. Ada berapa cara untuk melakukannya?
🔗
🔗
Luangkan waktu sejenak untuk memikirkan cara menyelesaikan masalah ini. Anda boleh menganggap bahwa seorang anak boleh tidak memperoleh kue sama sekali. Selain itu, semua kue identik dan urutan pembagiannya tidak penting (jadi, memberikan kue kepada anak kedua sebelum anak pertama tidak dihitung sebagai hasil yang berbeda dari urutan sebaliknya).
🔗
Sebelum menyelesaikan masalah ini, berikut sebuah jawaban yang salah: Anda mungkin menduga bahwa jawabannya adalah \(4^7\) karena, untuk masing-masing dari 7 kue, terdapat 4 pilihan anak yang dapat menerima kue tersebut. Dugaan ini masuk akal, tetapi salah. Untuk melihat alasannya, perhatikan beberapa kemungkinan hasil: kita dapat memberikan enam kue pertama kepada anak A dan kue ketujuh kepada anak B. Hasil lain memberikan kue pertama kepada anak B dan enam kue yang tersisa kepada anak A. Kedua hasil itu tercakup dalam jawaban \(4^7\text{.}\) Namun, bagi masalah pencacahan kita, kedua hasil itu sebenarnya sama – anak A memperoleh enam kue dan anak B memperoleh satu kue. Jawaban tersebut akan benar jika semua kue berbeda, padahal kue-kue itu identik.
🔗
Seperti apa sebenarnya hasil-hasil itu? Bagaimana kita dapat merepresentasikannya? Salah satu pendekatan adalah menuliskan suatu hasil sebagai string empat bilangan seperti berikut:
\begin{equation*} 3112\text{,} \end{equation*}
yang merepresentasikan hasil ketika anak pertama memperoleh 3 kue, anak kedua dan ketiga masing-masing memperoleh 1 kue, dan anak keempat memperoleh 2 kue. Dalam representasi ini, urutan kemunculan bilangan-bilangannya penting. String 1312 merupakan hasil yang berbeda karena anak pertama memperoleh satu kue, bukan 3. Setiap bilangan dalam string dapat berupa bilangan bulat apa pun dari 0 hingga 7. Namun, jawabannya bukan \(7^4\text{.}\) Kita memerlukan jumlah bilangan-bilangan itu sama dengan 7.
🔗
Cara lain untuk merepresentasikan hasil adalah menuliskan string tujuh huruf:
\begin{equation*} \text{ABAADCD}\text{,} \end{equation*}
yang merepresentasikan bahwa kue pertama diberikan kepada anak A, kue kedua kepada anak B, kue ketiga dan keempat kepada anak A, dan seterusnya. Sebenarnya, hasil ini identik dengan hasil sebelumnya—A memperoleh 3 kue, B dan C masing-masing memperoleh 1, dan D memperoleh 2. Setiap huruf dalam string tersebut dapat berupa salah satu dari 4 huruf yang mungkin (satu untuk setiap anak), tetapi banyaknya string seperti itu bukan \(4^7\) karena di sini urutan tidak penting. Bahkan, cara lain untuk menuliskan hasil yang sama adalah
\begin{equation*} \text{AAABCDD}\text{.} \end{equation*}
🔗
Inilah representasi hasil yang akan kita utamakan. Karena kita dapat menuliskan huruf-huruf itu dalam urutan apa pun, untuk keperluan pencacahan kita dapat menuliskannya dalam urutan alfabetis. Jadi, kita akan menuliskan semua A terlebih dahulu, kemudian semua B, dan seterusnya. Karena kita tidak membedakan susunan yang berbeda, ini sebenarnya seperti menuliskan sebuah himpunan, hanya saja multihimpunan ini dapat memuat suatu elemen lebih dari sekali.
🔗
Jadi, sekarang kita memiliki dua cara yang berguna untuk memandang hasil-hasil tersebut.
  1. Sebagai multihimpunan yang memuat 7 elemen, yang masing-masing merupakan salah satu dari empat anak (atau huruf yang mewakili nama mereka). Sebagai contoh,
    \begin{equation*} \{A, A, A, B, C, D, D\}\text{.} \end{equation*}
    Setiap kemunculan seorang anak dalam multihimpunan berarti anak itu memperoleh satu kue, sehingga multiplisitas anak tersebut dalam multihimpunan adalah banyaknya kue yang diperolehnya.
    🔗
    🔗
  2. Sebagai string 4 bilangan taknegatif yang jumlahnya 7. Sebagai contoh,
    \begin{equation*} 3112\text{.} \end{equation*}
    Posisi bilangan dalam string merepresentasikan anaknya, sedangkan bilangan itu sendiri merepresentasikan banyaknya kue yang diperoleh anak tersebut.
    🔗
    🔗
🔗
Sebelum memikirkan cara menghitung banyaknya hasil yang direpresentasikan dengan cara ini, perhatikan beberapa contoh lain masalah pencacahan yang dapat kita representasikan dengan kedua cara tersebut.
🔗

Contoh 3.5.2.

Anda mengambil segenggam sepuluh permen jeli dari kantong yang berisi enam rasa. Tuliskan tiga kemungkinan hasil dengan menggunakan multihimpunan dan string bilangan.
🔗
Penyelesaian.
Multihimpunan merupakan cara yang lebih alami untuk memandang masalah ini karena setiap genggam merupakan multihimpunan rasa. Sebagai contoh, kita dapat memperoleh
\begin{equation*} \{R, R, G, G, G, B, B, B, B, Y\} \end{equation*}
yang berarti Anda memperoleh dua permen jeli merah, tiga hijau, empat biru, dan satu kuning (serta tidak memperoleh yang ungu atau jingga), atau
\begin{equation*} \{R, R, R, R, R, R, R, R, R, R\} \end{equation*}
yang berarti Anda memperoleh sepuluh permen jeli merah. Anda juga dapat memperoleh
\begin{equation*} \{R, G, B, Y, P, O, O, O, O, O\} \end{equation*}
yang berarti Anda memperoleh masing-masing satu permen jeli merah, hijau, biru, kuning, dan ungu, serta lima permen jeli jingga.
🔗
Barisan enam bilangan yang bersesuaian dan berjumlah 10 adalah
\begin{equation*} 2,3,4,1,0,0; \qquad 10,0,0,0,0,0; \qquad 1,1,1,1,1,5\text{.} \end{equation*}
(Kita menambahkan koma di antara bilangan karena tidak setiap bilangan hanya terdiri atas satu digit.) Perhatikan bahwa untuk representasi ini kita harus menyepakati urutan rasa yang tetap; dalam hal ini urutannya tidak alfabetis, tetapi sama dengan urutan yang digunakan saat menuliskan multihimpunan.
🔗
🔗
🔗

Contoh 3.5.3.

Anda memiliki 12 eksemplar identik buku Matematika Diskret favorit yang ingin Anda letakkan pada 5 rak buku. Tuliskan tiga kemungkinan hasil dengan menggunakan multihimpunan dan string bilangan.
🔗
Penyelesaian.
Di sini barisan bilangan lebih alami karena kita cukup menyatakan banyaknya buku pada setiap rak. Kita memerlukan 5 bilangan yang jumlahnya 12. Sebagai contoh, kita dapat memperoleh
  1. \(3,3,3,2,1\text{,}\) yang berarti 3 buku pada rak pertama, 3 pada rak kedua, 3 pada rak ketiga, 2 pada rak keempat, dan 1 pada rak kelima.
    🔗
    🔗
  2. \(0,0,12,0,0\text{,}\) yang berarti semua 12 buku berada pada rak tengah.
    🔗
    🔗
  3. \(1,1,1,1,8\text{,}\) yang berarti satu buku pada masing-masing dari empat rak pertama dan 8 pada rak terakhir.
    🔗
    🔗
🔗
Multihimpunan yang bersesuaian adalah
  1. \(\{1,1,1,2,2,2,3,3,3,4,4,5\}\text{,}\) yang berarti rak 1 diberi buku tiga kali, rak 2 diberi buku tiga kali, dan seterusnya. Perhatikan bahwa terdapat 12 elemen dalam multihimpunan, satu untuk setiap buku. Bilangan-bilangan di sini merepresentasikan rak; multiplisitas suatu bilangan adalah banyaknya buku pada rak tersebut.
    🔗
    🔗
  2. \(\{3,3,3,3,3,3,3,3,3,3,3,3\}\text{.}\) Satu-satunya rak dalam multihimpunan adalah rak 3, dengan multiplisitas 12, yang berarti rak 3 memperoleh 12 buku.
    🔗
    🔗
  3. \(\{1,2,3,4,5,5,5,5,5,5,5,5\}\text{.}\) Di sini rak 1 memperoleh satu buku, rak 2 satu buku, rak 3 satu buku, rak 4 satu buku, dan rak 5 memperoleh sisanya.
    🔗
    🔗
🔗
🔗
🔗
Contoh terakhir ini juga dapat diajukan sebagai pertanyaan tentang penyelesaian persamaan dengan solusi bilangan bulat taknegatif. Secara khusus, kita dapat mencari solusi persamaan \(a+b+c+d+e = 12\text{.}\) Pandang setiap variabel sebagai bilangan yang menyatakan banyaknya buku pada setiap rak. Kita akan mengajukan pertanyaan secara langsung dalam bentuk seperti ini, tetapi mengetahui cara merepresentasikan pertanyaan lain sebagai persamaan semacam itu juga berguna.
🔗
🔗

Subbagian Merepresentasikan Multihimpunan dengan String Bit

Sekarang mari kita kembali ke masalah semula, yaitu membagikan 7 kue kepada 4 anak, dan benar-benar menghitung banyaknya hasil.
🔗
Ketika mencacah himpunan biasa, kita melihat bahwa bilangan-bilangan dalam Segitiga Pascal memberikan hasil pencacahannya. Hal ini benar karena kita dapat merepresentasikan setiap himpunan sebagai string bit. Setiap kali suatu elemen berada dalam himpunan, kita menandainya dengan 1; jika elemen itu tidak berada dalam himpunan, kita menandai ketidakhadirannya dengan 0.
🔗
Pada dasarnya, inilah yang kita lakukan dengan multihimpunan, tetapi kita harus menggunakan string bilangan taknegatif yang tidak terbatas pada 0 dan 1 karena suatu elemen dalam multihimpunan dapat muncul lebih dari nol atau satu kali. Namun, jika kita dapat menerjemahkan string bilangan tersebut menjadi jenis string bit lain, kita dapat menggunakan Segitiga Pascal untuk menghitung banyaknya multihimpunan.
🔗
Berikut cara melakukannya. Diberikan multihimpunan seperti
\begin{equation*} \{A, A, A, B, C, D, D\} \end{equation*}
kita memiliki representasi barisan bilangan
\begin{equation*} 3,1,1,2\text{.} \end{equation*}
Alih-alih menggunakan bilangan satu per satu, tuliskan masing-masing sebagai barisan angka 1 sebanyak bilangan tersebut. Jadi, contoh ini menjadi
\begin{equation*} 111,1,1,11\text{.} \end{equation*}
Bentuk ini agak canggung karena kita menggunakan koma untuk memisahkan bilangan. Agar lebih jelas, mari kita beralih ke dua simbol yang berbeda. Kita akan menyebutnya batang dan batu, dengan batu merepresentasikan angka 1 dan batang merepresentasikan koma. Jadi, barisan
\begin{equation*} 111,1,1,11 \end{equation*}
menjadi
\begin{equation*} \o\o\o|\o|\o|\o\o\text{.} \end{equation*}
Ini adalah string sepuluh simbol, yang terdiri atas 7 batu dan 3 batang.
🔗
Ini luar biasa! Apa pun kedua simbol yang kita gunakan (metode ini mungkin juga disebut bintang dan batang atau bola dan kotak), kita dapat menggunakan Segitiga Pascal untuk menghitung banyaknya cara menyusun simbol-simbol tersebut. Banyaknya string 10-bit berbobot 3 (atau berbobot 7) adalah \(\binom{10}{3} = 120\text{.}\)
🔗
Dalam konteks kue, kita dapat memandang diagram batang dan batu ini sebagai penunjuk setelah berapa kue kita berhenti memberikan kue kepada anak pertama dan mulai memberikannya kepada anak kedua. Lalu setelah berapa kue kita berpindah ke anak ketiga? Dan setelah berapa kue kita berpindah ke anak keempat? Jadi,
\begin{equation*} \o\o\o|\o|\o|\o\o \end{equation*}
berarti tiga kue diberikan kepada anak pertama; kemudian kita berpindah dan memberikan satu kue kepada anak kedua, berpindah lagi dan memberikan satu kepada anak ketiga, lalu berpindah dan memberikan dua kepada anak keempat. Perhatikan bahwa kita memerlukan 7 batu dan 3 batang – satu batu untuk setiap kue dan satu batang untuk setiap perpindahan antaranak, sehingga jumlah batang satu lebih sedikit daripada jumlah anak (kita tidak perlu berpindah setelah anak terakhir – kita sudah selesai).
🔗
Sekalian, kita juga dapat menjawab pertanyaan terkait: ada berapa cara untuk membagikan 7 kue kepada 4 anak sehingga setiap anak memperoleh sedikitnya satu kue? Apa yang dapat Anda katakan tentang diagram batang dan batu yang bersesuaian? Diagram tersebut harus diawali dan diakhiri dengan sedikitnya satu batu (agar anak A dan D memperoleh kue), dan tidak boleh ada dua batang yang berdampingan (agar anak B dan C tidak dilewati). Salah satu cara untuk memastikan hal ini adalah menempatkan batang hanya pada celah di antara batu-batu. Dengan 7 batu, terdapat 6 celah di antaranya, sehingga kita harus memilih 3 dari 6 celah tersebut untuk diisi batang. Jadi, terdapat \({6 \choose 3}\) cara untuk membagikan 7 kue kepada 4 anak dengan memberikan sedikitnya satu kue kepada setiap anak.
🔗
Cara lain (dan lebih umum) untuk menangani masalah yang dimodifikasi ini adalah terlebih dahulu memberikan satu kue kepada setiap anak. Kini 3 kue yang tersisa dapat dibagikan kepada 4 anak tanpa batasan. Jadi, kita memiliki 3 batu dan 3 batang, sehingga jumlahnya 6 simbol dan 3 di antaranya harus berupa batang. Sekali lagi, kita melihat bahwa terdapat \({6 \choose 3}\) cara untuk membagikan kue-kue tersebut.
🔗
Batang dan batu dapat digunakan dalam masalah pencacahan selain anak dan kue. Berikut beberapa contohnya:
🔗

Contoh 3.5.4.

Kedai es krim matematis favorit Anda menawarkan 10 rasa. Ada berapa susu kocok yang dapat Anda buat dengan tepat 6 sendok es krim yang tidak harus berbeda? Urutan penambahan rasa tidak penting (semuanya akan diblender), tetapi pengulangan diperbolehkan. Jadi, salah satu susu kocok yang mungkin terdiri atas tiga sendok cokelat, dua sendok ceri, dan satu sendok cokelat keping mint.
🔗
Penyelesaian.
Kita memperoleh enam sendok, yang masing-masing dapat berupa salah satu dari sepuluh rasa yang mungkin. Representasikan setiap sendok sebagai bintang. Bayangkan Anda menyusuri etalase, satu rasa demi satu: pertama Anda melihat vanila, lalu melewatinya menuju rasa berikutnya, cokelat. Anda mengatakan ya untuk cokelat tiga kali (gunakan tiga batu), kemudian berpindah ke rasa berikutnya. Anda terus melewati rasa hingga tiba pada ceri, dan mengatakan ya dua kali. Berpindah sekali lagi, Anda tiba pada cokelat keping mint. Anda mengatakan ya satu kali. Lalu Anda terus berpindah sampai melewati rasa terakhir tanpa mengatakan ya lagi (karena Anda sudah mengatakan ya enam kali). Terdapat sepuluh rasa yang dapat dipilih, sehingga kita harus berpindah dari satu rasa ke rasa berikutnya sembilan kali. Perpindahan ini direpresentasikan oleh sembilan batang.
🔗
Setelah yakin bahwa kita memiliki jumlah batang dan batu yang tepat, kita dapat menjawab pertanyaan dengan mudah: terdapat 6 batu dan 9 batang, sehingga seluruhnya ada 15 simbol. Kita perlu memilih 9 di antaranya sebagai batang, sehingga banyaknya susu kocok yang mungkin adalah
\begin{equation*} \binom{15}{9}\text{.} \end{equation*}
🔗
🔗
🔗

Contoh 3.5.5.

Ada berapa nomor telepon 7 digit yang digit-digitnya takmenaik? Artinya, setiap digit kurang dari atau sama dengan digit sebelumnya.
🔗
Penyelesaian.
Kita perlu menentukan 7 digit, sehingga kita akan menggunakan 7 batu. Batang akan merepresentasikan perpindahan dari setiap bilangan satu digit yang mungkin ke bilangan lebih kecil berikutnya. Jadi, nomor telepon 866-5221 direpresentasikan oleh diagram batang dan batu
\begin{equation*} |\o||\o\o|\o|||\o\o|\o|\text{.} \end{equation*}
🔗
Terdapat 10 pilihan untuk setiap digit (0–9), sehingga kita harus berpindah di antara pilihan sebanyak 9 kali. Kita memiliki 7 batu dan 9 batang, sehingga jumlah seluruh nomor telepon adalah
\begin{equation*} {16 \choose 9}\text{.} \end{equation*}
🔗
🔗
🔗

Contoh 3.5.6.

Ada berapa solusi bilangan bulat untuk persamaan
\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 = 13\text{.} \end{equation*}
🔗
(Solusi bilangan bulat suatu persamaan adalah solusi yang peubah takdiketahuinya harus bernilai bilangan bulat.)
🔗
  1. dengan \(x_i \ge 0\) untuk setiap \(x_i\text{?}\)
    🔗
    🔗
  2. dengan \(x_i > 0\) untuk setiap \(x_i\text{?}\)
    🔗
    🔗
  3. dengan \(x_i \ge 2\) untuk setiap \(x_i\text{?}\)
    🔗
    🔗
🔗
Penyelesaian.
Masalah ini sama seperti memberikan 13 kue kepada 5 anak. Kita perlu menentukan berapa dari 13 satuan yang diberikan kepada masing-masing dari 5 variabel. Dengan kata lain, kita memiliki 13 batu dan 4 batang (batang berperan seperti tanda “+” dalam persamaan).
🔗
  1. Jika \(x_i\) dapat bernilai 0 atau lebih, kita berada dalam kasus standar tanpa batasan. Jadi, 13 batu dan 4 batang dapat disusun dalam \({17 \choose 4}\) cara.
    🔗
    🔗
  2. Sekarang setiap variabel harus bernilai sedikitnya 1. Jadi, berikan satu satuan kepada setiap variabel untuk memenuhi batasan tersebut. Kini tersisa 8 batu dan masih ada 4 batang, sehingga banyaknya solusi adalah \({12 \choose 4}\text{.}\)
    🔗
    🔗
  3. Sekarang setiap variabel harus bernilai 2 atau lebih. Jadi, sebelum melakukan pencacahan, berikan 2 satuan kepada setiap variabel. Kini kita memiliki 3 batu yang tersisa dan 4 batang, sehingga terdapat \({7 \choose 4}\) solusi.
    🔗
    🔗
🔗
🔗
🔗

Pencacahan dengan Fungsi.

Banyak masalah pencacahan dalam bagian ini mula-mula mungkin tampak sebagai contoh pencacahan fungsi. Lagi pula, ketika mencoba menghitung banyaknya cara membagikan kue kepada anak-anak, kita memasangkan setiap kue dengan seorang anak, seperti memasangkan elemen domain suatu fungsi dengan elemen kodomainnya. Namun, banyaknya cara membagikan 7 kue kepada 4 anak adalah \({10 \choose 7} = 120\text{,}\) sedangkan banyaknya fungsi \(f: \{1,2,3,4,5,6,7\} \to \{a,b,c,d\}\) adalah \(4^7 = 16384\text{.}\) Apa yang terjadi di sini?
🔗
Ketika mencacah fungsi, kita menganggap, misalnya, kedua fungsi berikut berbeda:
\begin{equation*} f = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{a \amp b \amp c \amp c \amp c \amp c \amp c} \qquad g = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{b \amp a \amp c \amp c \amp c \amp c \amp c}\text{.} \end{equation*}
Namun, kedua fungsi ini berkorespondensi dengan pembagian kue yang sama: anak \(a\) dan \(b\) masing-masing memperoleh satu kue, anak \(c\) memperoleh sisanya, dan anak \(d\) tidak memperoleh kue.
🔗
Intinya: elemen-elemen domain dapat dibedakan, sedangkan kue-kue tidak dapat dibedakan. Hal ini analog dengan perbedaan antara permutasi (seperti pencacahan fungsi) dan kombinasi.
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Manakah di antara pertanyaan pencacahan berikut yang BUKAN merupakan contoh pertanyaan yang akan Anda selesaikan dengan batang dan batu?
🔗
  • Ada berapa cara untuk membagikan enam hadiah berbeda kepada tiga teman?
    🔗
  • Benar. Karena hadiah-hadiahnya berbeda, kita memiliki tiga pilihan untuk hadiah pertama, tiga untuk hadiah kedua, dan seterusnya, sehingga jawabannya adalah \(3^6\text{.}\)
  • Ada berapa cara untuk membagikan enam hadiah identik kepada tiga teman?
    🔗
  • Anda dapat menggunakan batang dan batu di sini: gunakan dua batang untuk memisahkan ketiga teman dan enam batu untuk hadiah-hadiahnya.
  • Ada berapa kombinasi bilangan berbeda yang dapat Anda peroleh jika Anda melempar tiga dadu identik bersisi 6?
    🔗
  • Gunakan lima batang untuk memisahkan keenam nilai pada dadu. Setiap batu merepresentasikan salah satu dadu identik tersebut.
  • Ada berapa susu kocok tiga sendok yang berbeda jika setiap sendok es krim dapat berupa salah satu dari enam rasa berbeda?
    🔗
  • Gunakan lima batang dan tiga batu!
🔗

2.

Ketika Anda mencacah hasil dengan batang dan batu, apakah urutan penting? Apakah pengulangan diperbolehkan? Jelaskan maksud jawaban Anda (urutan dari apa, pengulangan dari apa)?
🔗
🔗

3.

Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan sedikitnya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Multihimpunan adalah koleksi objek, sama seperti himpunan, tetapi dapat memuat suatu objek lebih dari sekali (urutan elemennya tetap tidak penting). Sebagai contoh, \(\{1,1, 2, 5, 5, 7\}\) merupakan multihimpunan berukuran 6.
  1. Ada berapa himpunan berukuran 5 yang dapat dibentuk dengan menggunakan 10 digit 0 sampai 9?
    🔗
    🔗
  2. Ada berapa multihimpunan berukuran 5 yang dapat dibentuk dengan menggunakan 10 digit 0 sampai 9?
    🔗
    🔗
🔗
🔗

2.

Dengan menggunakan digit 2 sampai 7, tentukan banyaknya bilangan berbeda yang terdiri atas 5 digit sehingga:
  1. Digit tidak boleh berulang dan harus ditulis dalam urutan menaik. (Menaik berarti menaik secara ketat. Sebagai contoh, digit pada 134 menaik, tetapi digit pada 133 tidak.)
    🔗
    🔗
  2. Digit boleh berulang dan harus ditulis dalam urutan takmenurun. (Sekarang digit tidak harus menaik secara ketat; digit pada 133 takmenurun.)
    🔗
    🔗
🔗
🔗

3.

Setelah pelajaran olahraga, Anda ditugasi menyimpan 21 bola dodgeball identik ke dalam 10 wadah.
  1. Ada berapa cara untuk melakukannya jika tidak ada kendala?
    🔗
    🔗
  2. Ada berapa cara untuk melakukannya jika setiap wadah harus memuat sedikitnya satu bola dodgeball?
    🔗
    🔗
🔗
🔗

4.

Berapakah banyaknya solusi bilangan bulat untuk persamaan \(x + y + z = 11\) yang memenuhi
  1. \(x\text{,}\) \(y\text{,}\) dan \(z\) semuanya positif?
    🔗
    🔗
  2. \(x\text{,}\) \(y\text{,}\) dan \(z\) semuanya taknegatif?
    🔗
    🔗
  3. \(x\text{,}\) \(y\text{,}\) dan \(z\) semuanya lebih besar daripada atau sama dengan \(-3\text{.}\)
    🔗
    🔗
🔗
🔗

5.

Ketika bermain Yahtzee, Anda melempar lima dadu biasa bersisi 6. Ada berapa hasil berbeda yang mungkin diperoleh dari satu lemparan? Urutan dadu tidak penting.
🔗
Ketika bermain Super-Yahtzee, Anda melempar 6 dadu biasa bersisi 5. Sekarang ada berapa hasil berbeda yang mungkin diperoleh dari satu lemparan?
🔗
🔗

6.

Teman Anda mengatakan bahwa ia memegang 11 keping uang logam (hanya koin 1 sen atau penny, 5 sen atau nickel, 10 sen atau dime, dan 25 sen atau quarter). Jika Anda menebak banyaknya uang logam dari setiap jenis yang ia miliki, ia akan memberikan semuanya kepada Anda. Jika Anda menebak secara acak, berapakah peluang bahwa tebakan Anda benar?
🔗
Petunjuk.
Peluangnya adalah 1 dibagi banyaknya kombinasi berbeda dari 11 keping uang logam yang mungkin dimiliki teman Anda.
🔗
🔗
🔗

7.

Berapakah banyaknya solusi bilangan bulat untuk \(x_1 + x_2 + x_3 + x_4 = 38\) yang memenuhi \(x_1 \ge 4\text{,}\) \(x_2 \ge 4\text{,}\) \(x_3 \ge 1\text{,}\) dan \(x_4\ge 1\text{?}\)
🔗
🔗

8.

Perhatikan fungsi-fungsi \(f:{\left\{1,2,3,4,5,6,7\right\}} \to {\left\{0,1,2,3,4,5,6,7,8,9,10\right\}}\text{.}\)
  1. Berapa banyak fungsi yang menaik secara ketat? Jelaskan. (Suatu fungsi menaik secara ketat jika \(\renewcommand{\v}{\vtx{above}{}}a \lt b\text{,}\) maka \(\renewcommand{\v}{\vtx{above}{}}f(a) \lt f(b)\text{.}\))
    🔗
    🔗
  2. Berapa banyak fungsi yang takmenurun? Jelaskan. (Suatu fungsi takmenurun jika \(\renewcommand{\v}{\vtx{above}{}}a \lt b\text{,}\) maka \(f(a) \le f(b)\text{.}\))
    🔗
    🔗
🔗
🔗

9.

Conic, gerai cepat saji bertema matematika favorit Anda yang melayani pesanan dari kendaraan, menawarkan 17 rasa yang dapat ditambahkan ke soda. Anda mempunyai cukup uang untuk membeli soda besar dengan 7 tambahan rasa. Ada berapa racikan soda berbeda yang dapat Anda pesan jika:
  1. Anda tidak mau menggunakan rasa yang sama lebih dari sekali?
    🔗
    🔗
  2. Anda tidak memperbolehkan pengulangan, tetapi memperhatikan urutan penambahan rasa?
    🔗
    🔗
  3. Anda memperbolehkan beberapa takaran rasa yang sama?
    🔗
    🔗
  4. Anda memperbolehkan beberapa takaran rasa yang sama dan memperhatikan urutan penambahan rasa?
    🔗
    🔗
🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Setiap masalah pencacahan di bawah ini dapat diselesaikan dengan batang dan batu. Untuk masing-masing masalah, jelaskan hasil yang direpresentasikan oleh diagram
\begin{equation*} \o\o\o|\o||\o\o| \end{equation*}
jika jumlah batang dan batunya tepat untuk masalah tersebut. Jika tidak, jelaskan mengapa diagram itu tidak merepresentasikan hasil apa pun, dan seperti apa diagram yang benar.
  1. Ada berapa cara untuk mengambil segenggam 6 permen jeli dari stoples yang berisi 5 rasa berbeda?
    🔗
    🔗
  2. Ada berapa cara untuk membagikan 5 lolipop identik kepada 6 anak?
    🔗
    🔗
  3. Ada berapa kata 6 huruf yang dapat Anda bentuk dengan menggunakan 5 huruf vokal dalam urutan alfabetis?
    🔗
    🔗
  4. Ada berapa solusi untuk persamaan \(x_1 + x_2 + x_3 + x_4 = 6\text{.}\)
    🔗
    🔗
🔗
🔗

2.

Selesaikan ketiga masalah pencacahan di bawah ini. Kemudian jelaskan mengapa wajar jika semuanya memiliki jawaban yang sama. Artinya, jelaskan bagaimana masing-masing dapat ditafsirkan sebagai masalah yang lain.
  1. Ada berapa cara untuk membagikan 8 kue kepada 3 anak?
    🔗
    🔗
  2. Ada berapa solusi dalam bilangan bulat taknegatif untuk \(x+y+z = 8\text{?}\)
    🔗
    🔗
  3. Ada berapa kemasan berbeda yang masing-masing berisi 8 krayon yang dapat Anda buat dengan krayon merah, biru, dan kuning?
    🔗
    🔗
🔗
🔗

3.

Kita telah merepresentasikan multihimpunan dengan diagram batang dan batu, lalu menghitung banyaknya diagram batang dan batu untuk memperoleh banyaknya multihimpunan. Proses ini hanya sah jika setiap multihimpunan berkorespondensi dengan tepat satu diagram batang dan batu, dan sebaliknya.
🔗
(a)
Tuliskan dengan jelas aturan untuk mengubah multihimpunan menjadi diagram batang dan batu. Artinya, deskripsikan fungsi \(f\) yang menerima multihimpunan sebagai masukan dan menghasilkan diagram batang dan batu sebagai keluaran.
🔗
🔗
(b)
Buktikan bahwa fungsi \(f\) merupakan bijeksi. Artinya, buktikan bahwa setiap diagram batang dan batu berkorespondensi dengan tepat satu multihimpunan, dan sebaliknya.
🔗
Petunjuk.
Hal ini sebenarnya memerlukan pembuktian empat fakta: setiap multihimpunan berkorespondensi dengan sedikitnya satu diagram, dan setiap diagram berkorespondensi dengan sedikitnya satu multihimpunan; lalu setiap multihimpunan berkorespondensi dengan paling banyak satu diagram, dan setiap diagram berkorespondensi dengan paling banyak satu multihimpunan. Dengan kata lain, kita harus membuktikan bahwa fungsi tersebut terdefinisi dengan baik, injektif, dan surjektif.
🔗
🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik