Subbagian Apa yang Dimaksud dengan Hasil?
Sebelum mulai mencacah, mari kita perhatikan sejenak cara persoalan pencacahan diajukan. Persoalan pencacahan sering kali menanyakan berapa banyak cara sesuatu dapat terjadi. Artinya, terdapat suatu
kejadian yang dapat memberikan berbagai
hasil, dan hasil-hasil yang berbeda itulah yang dicacah. Sebagai alternatif, kita dapat mengambil sudut pandang yang kurang “aktif” dengan menanyakan banyaknya elemen dalam suatu himpunan, misalnya himpunan string bit dengan panjang dan bobot tertentu. Namun, pertanyaan ini pun dapat dirumuskan kembali sebagai pertanyaan tentang suatu kejadian: jika Anda memilih secara acak salah satu string bit (dari himpunan string bit), ada berapa hal yang dapat terjadi?
Jadi, mencacah elemen dalam suatu himpunan sebenarnya tidak berbeda dengan mencacah banyaknya hasil suatu kejadian. Mari kita pandang setiap persoalan pencacahan sebagai pertanyaan tentang banyaknya elemen dalam suatu
himpunan hasil.
Pada tingkat paling dasar, pencacahan sama sekali tidak sulit: tuliskan semua hasil dalam daftar bernomor dan lihat berapa banyak nomor yang digunakan. Mari saya ceritakan koleksi dasi kupu-kupu saya. Saya memiliki
-
Sebuah dasi kupu-kupu ungu.
-
Sebuah dasi kupu-kupu hijau.
-
Sebuah dasi kupu-kupu bergaris.
-
Sebuah dasi kupu-kupu bermotif paisley.
Berapa banyak dasi kupu-kupu yang saya miliki (ada berapa cara saya dapat memilih sebuah dasi kupu-kupu)? Bilangan terbesar dalam daftar bernomor saya adalah 4, jadi saya memiliki empat dasi kupu-kupu. Tentu saja, seperti yang kita lihat pada bagian sebelumnya, kita dapat menggunakan jalan pintas agar tidak perlu menuliskan semua hasil, misalnya menggunakan segitiga Pascal untuk menentukan banyaknya objek dalam daftar.
Pencacahan mulai menarik ketika kita ingin membuat daftar baru yang menggabungkan dua atau lebih daftar yang telah kita cacah. Sebagai contoh, misalkan selain daftar empat dasi kupu-kupu, saya memiliki daftar tujuh pasang kaus kaki unik. Saya dapat menanyakan banyaknya pilihan jika saya ingin mengenakan sebuah dasi kupu-kupu keren atau sepasang kaus kaki unik. Gabungkan kedua daftar tersebut untuk membuat daftar baru dengan 11 objek: mungkin kita menuliskan empat dasi kupu-kupu terlebih dahulu, lalu melanjutkan pencacahan (dimulai dengan nomor 5 untuk pasangan kaus kaki pertama) hingga tujuh objek tambahan selesai dituliskan dan daftar berakhir pada nomor 11.
Dalam contoh ini, kita telah menggabungkan dua himpunan hasil (memilih dasi kupu-kupu dan memilih sepasang kaus kaki) untuk memperoleh himpunan hasil baru (memilih dasi kupu-kupu atau sepasang kaus kaki). Himpunan hasil yang terbentuk memuat 11 elemen.
Sekarang perhatikan pertanyaan berikut: ada berapa pilihan jika saya ingin mengenakan dasi kupu-kupu sekaligus sepasang kaus kaki unik? Sekali lagi, saya perlu menggabungkan dua himpunan hasil untuk memperoleh himpunan hasil baru. Namun, himpunan hasil baru ini akan memuat 28 elemen. Bagaimana saya mengetahui bahwa banyaknya elemen dalam kedua himpunan asal harus dikalikan, bukan dijumlahkan? Sekali lagi kita menggabungkan hasil: himpunan hasil yang terbentuk memuat 28 elemen yang masing-masing terdiri atas sebuah dasi kupu-kupu dan sepasang kaus kaki. Sekarang bacalah kembali paragraf sebelumnya! Keduanya terdengar sangat mirip!
Perbedaan antara kedua skenario tersebut cukup halus. Terdapat dua cara untuk memandang penggabungan hasil:
-
Kita dapat menggabungkan
himpunan-himpunan hasil.
-
Kita dapat menggabungkan
hasil-hasil di dalam himpunan.
Kemampuan membedakan kedua operasi ini merupakan keterampilan penting dalam kombinatorika.
Contoh 3.2.1.
Misalkan pada pintu lemari es Anda terdapat beberapa magnet berbentuk huruf dan angka: ada lima huruf (A, B, C, D, dan E) serta tiga angka (1, 2, dan 3). Saudara laki-laki Anda mengatakan bahwa jika kedua himpunan magnet ini digabungkan, akan diperoleh koleksi 8 magnet. Saudara perempuan Anda mengatakan bahwa magnet-magnet ini dapat digabungkan dengan 15 cara.
Himpunan hasil apa yang dipikirkan oleh kedua saudara Anda?
Penyelesaian.
Saudara laki-laki Anda memikirkan penggabungan himpunan-himpunan hasil. Himpunan hasil untuk huruf adalah
\(\{A, B, C, D, E\}\text{,}\) sedangkan himpunan hasil untuk angka adalah
\(\{1, 2, 3\}\text{.}\) Himpunan hasil untuk gabungan kedua himpunan magnet adalah
\(\{A, B, C, D, E, 1, 2, 3\}\text{,}\) yang memuat 8 elemen.
Saudara perempuan Anda memikirkan penggabungan hasil-hasil itu sendiri. Himpunan hasilnya adalah
\begin{gather*}
\{A1, A2, A3, B1, B2, B3, C1, C2,\\
\qquad C3, D1, D2, D3, E1, E2, E3\},
\end{gather*}
yang memuat 15 elemen.
Subbagian Prinsip Penjumlahan dan Prinsip Perkalian
Mari kita tuliskan dengan cermat aturan-aturan yang dapat digunakan untuk menggabungkan himpunan-himpunan hasil dan hasil-hasil di dalam himpunan.
Prinsip 3.2.2. Prinsip Penjumlahan.
Jika kejadian
\(A\) memberikan
\(m\) hasil dan kejadian
\(B\) memberikan
\(n\) hasil yang
saling lepas dari hasil kejadian pertama, maka kejadian “
\(A\) atau
\(B\)” memberikan
\(m + n\) hasil.
Penting bahwa kedua kejadian tersebut
saling lepas, yaitu tidak mungkin
\(A\) dan
\(B\) terjadi secara bersamaan. Sebagai contoh, satu set kartu remi standar yang terdiri atas 52 kartu memuat
\(26\) kartu merah dan
\(12\) kartu bergambar. Namun, banyaknya cara memilih kartu yang berwarna merah atau merupakan kartu bergambar bukanlah
\(26 + 12 = 38\text{.}\) Hal ini karena terdapat 6 kartu yang sekaligus berwarna merah dan merupakan kartu bergambar.
Contoh 3.2.3.
Ada berapa “kata” dua huruf yang diawali dengan A atau B? (Sebuah
kata di sini hanya merupakan barisan huruf; kata itu tidak harus merupakan kata bahasa Inggris, bahkan tidak harus dapat dilafalkan.)
Penyelesaian.
Pertama, ada berapa kata dua huruf yang diawali dengan A? Kita hanya perlu memilih huruf kedua, yang dapat dilakukan dengan 26 cara. Jadi, terdapat 26 kata yang diawali dengan A. Terdapat pula 26 kata yang diawali dengan B. Untuk memilih kata yang diawali dengan A atau B, kita dapat memilihnya dari 26 kata pertama atau 26 kata kedua, sehingga seluruhnya terdapat 52 kata.
Kita memiliki dua himpunan hasil: kata-kata yang diawali dengan A dan kata-kata yang diawali dengan B. Kita membuat himpunan hasil baru dengan menggabungkan kedua himpunan itu untuk memperoleh himpunan kata yang diawali dengan A atau B. Menurut prinsip penjumlahan, himpunan baru ini memuat 52 hasil.
Kita sering menggunakan prinsip ini ketika himpunan-himpunan hasil perlu dicacah dengan teknik pencacahan lain.
Contoh 3.2.4.
Ada berapa string
\(10\)-bit berbobot
\(6\) yang diawali dengan
\(11\) atau
\(00\text{?}\)
Penyelesaian.
Kita telah mempelajari cara mencacah string bit dengan panjang dan bobot tetap dalam
Subbab 3.1. Jumlah seluruh string
\(10\)-bit berbobot
\(6\) adalah
\(\binom{10}{6} = 210\) (nilai ini diperoleh menggunakan
segitiga Pascal). Namun, kita hanya ingin mencacah string yang diawali dengan
\(11\) atau
\(00\) (bukan yang diawali dengan
\(10\) atau
\(01\)).
Karena tidak ada string bit yang sekaligus diawali dengan
\(11\) dan
\(00\text{,}\) kita dapat menerapkan prinsip penjumlahan. Kita akan menghitung ukuran setiap himpunan hasil, lalu menjumlahkan hasilnya.
Ada berapa string
\(10\)-bit berbobot
\(6\) yang diawali dengan
\(11\text{?}\) Jika string diawali dengan
\(11\text{,}\) maka di antara delapan bit yang tersisa harus terdapat empat angka 1 agar bobot totalnya
\(6\text{.}\) Ini sama dengan menanyakan banyaknya string
\(8\)-bit berbobot 4, sehingga terdapat
\(\binom{8}{4} = 70\) string semacam itu. Demikian pula, terdapat
\(\binom{8}{6} = 28\) string yang diawali dengan
\(00\) (keenam angka 1 harus berada di antara 8 bit yang tersisa). Menurut prinsip penjumlahan, jumlah seluruh string yang ingin kita cacah adalah
\(70 + 28 = 98\text{.}\)
Kita juga dapat menggunakan prinsip penjumlahan
secara tidak langsung dengan cara yang mungkin saja disebut
prinsip pengurangan (tetapi sebenarnya tidak demikian).
Contoh 3.2.5.
Ada berapa string
\(10\)-bit berbobot
\(6\) yang memiliki setidaknya satu angka 1 di antara tiga bit pertamanya?
Penyelesaian.
Ada banyak cara berbeda bagi sebuah string untuk memiliki setidaknya satu angka 1 di antara tiga bit pertamanya: string itu dapat diawali dengan 100, 010, 001, 101, 110, 011, atau 111. Kita dapat mencacah banyaknya string untuk setiap awalan tersebut, lalu menerapkan prinsip penjumlahan berkali-kali. Namun, kita tidak akan melakukannya.
Misalkan banyaknya string yang ingin kita cacah adalah
\(x\text{.}\) Misalkan
\(y\) adalah banyaknya string
\(10\)-bit berbobot 6 yang
tidak memiliki angka 1 pada ketiga bit pertamanya. Berapakah
\(x + y\text{?}\) Nilai ini adalah jumlah seluruh string
\(10\)-bit berbobot 6, yaitu
\(\binom{10}{6} = 210\text{.}\) Menentukan
\(y\) juga mudah: string bit dengan panjang 10 dan bobot 6 yang diawali dengan 000 harus berakhir dengan string bit yang panjangnya 7 dan bobotnya 6. Terdapat
\(\binom{7}{6} = 7\) string semacam itu.
Dengan demikian, kita memperoleh
\begin{equation*}
x + 7 = 210\text{,}
\end{equation*}
sehingga \(x = 210 - 7 = 203\text{.}\)
Meskipun kita tidak ingin menggunakan prinsip penjumlahan berulang kali dalam contoh sebelumnya, sebenarnya kita dapat melakukannya. Prinsip penjumlahan berlaku untuk lebih dari dua kejadian. Misalkan, selain empat dasi kupu-kupu dan tujuh pasang kaus kaki, Anda juga dapat memilih satu dari lima kepala ikat pinggang. Sekarang ada berapa pilihan? Anda memiliki
\(4+7+5 = 16\) pilihan.
Contoh 3.2.6.
Ada berapa kata dua huruf yang diawali dengan salah satu dari 5 huruf vokal?
Penyelesaian.
Terdapat 26 kata dua huruf yang diawali dengan A, 26 lainnya yang diawali dengan E, dan seterusnya. Menurut prinsip penjumlahan, jumlah seluruh kata adalah
\(26+26+26+26+26 = 130\text{.}\) Tentu saja, akan lebih mudah jika kita langsung menghitung
\(5\cdot 26\text{.}\)
Perhatikan bahwa dalam contoh sebelumnya, ketika prinsip penjumlahan digunakan pada sejumlah himpunan hasil berukuran sama, perkalian memberikan cara yang lebih cepat. Mari kita manfaatkan pengamatan ini dan menyatakannya sebagai prinsip baru.
Prinsip 3.2.7. Prinsip Perkalian.
Jika kejadian
\(A\) dapat terjadi dengan
\(m\) cara, dan setiap kemungkinan bagi
\(A\) memungkinkan tepat
\(n\) cara bagi kejadian
\(B\text{,}\) maka kejadian “
\(A\) dan
\(B\)” dapat terjadi dengan
\(m \cdot n\) cara.
Salah satu cara yang baik untuk menggambarkan prinsip perkalian adalah memandang hasil sebagai “tingkat” dalam suatu pohon. Sebagai ilustrasi, perhatikan persoalan pencacahan dalam
Contoh 3.2.1: ada berapa cara memilih sebuah huruf dari
\(\{A, B, C, D, E\}\text{,}\) kemudian sebuah angka dari
\(\{1, 2, 3\}\text{?}\) Diagram pohon berikut menunjukkan prosesnya.
Setiap daun pada pohon bersesuaian dengan satu hasil. Pohon tersebut menunjukkan bahwa ketiga hasil pada tingkat kedua diulang lima kali, masing-masing sekali untuk setiap hasil pada tingkat pertama.
Contoh 3.2.8.
Ada berapa kata dua huruf yang diawali dengan salah satu dari 5 huruf vokal? Kali ini gunakan prinsip perkalian untuk menjawab pertanyaan tersebut.
Penyelesaian.
Bagaimana kita dapat memandang pemilihan kata dua huruf sebagai urutan dua kejadian yang keduanya terjadi? Kejadian
\(A\) adalah “memilih huruf vokal yang mengawali kata.” Kejadian
\(B\) adalah “memilih huruf kedua kata.” Menurut prinsip perkalian, terdapat
\(5 \cdot 26 = 130\) cara bagi kejadian “
\(A\) dan
\(B\)” untuk terjadi.
Tentu saja, penyelesaian
Contoh 3.2.6 dan
Contoh 3.2.8 memberikan hasil yang sama, tetapi hasil yang kita gabungkan dan cara menggabungkannya berbeda.
Ketika menerapkan prinsip penjumlahan, kita menggabungkan lima himpunan hasil yang saling lepas. Salah satu himpunan hasil tersebut adalah
\begin{equation*}
\{AA, AB, AC, AD,\ldots, AZ\}
\end{equation*}
dan himpunan lainnya adalah
\begin{equation*}
\{EA, EB, EC, ED, \ldots, EZ\}\text{.}
\end{equation*}
Dengan kata lain, setiap himpunan hasil merupakan himpunan kata dua huruf yang diawali dengan huruf vokal berbeda. Prinsip penjumlahan menggabungkan kelima himpunan ini untuk membentuk himpunan baru yang memuat tepat elemen-elemen yang sama dengan himpunan-himpunan asal, tetapi semuanya terkumpul dalam satu himpunan.
Sebaliknya, ketika menerapkan prinsip perkalian, kita menggabungkan hasil-hasil dalam dua himpunan. Himpunan pertama adalah
\begin{equation*}
\{A, E, I, O, U\}
\end{equation*}
dan himpunan kedua adalah
\begin{equation*}
\{A, B, C, D, \ldots, Z\}\text{.}
\end{equation*}
Prinsip perkalian menggabungkan elemen-elemen dalam kedua himpunan tersebut untuk membentuk himpunan hasil baru (hasil-hasil yang tidak terdapat dalam himpunan mana pun yang digabungkan).
Seperti halnya prinsip penjumlahan, kita sering menggunakan prinsip perkalian untuk mendefinisikan himpunan-himpunan hasil yang terlebih dahulu perlu dicacah dengan cermat.
Contoh 3.2.9.
Ada berapa lintasan kisi dari
\((0,0)\) ke
\((10,10)\) yang melalui titik
\((4,7)\text{?}\)
Penyelesaian.
Kita dapat mencacah lintasan kisi dengan
segitiga Pascal, tetapi bagaimana kita memastikan bahwa lintasan melalui suatu titik tertentu? Setiap lintasan yang melalui
\((4,7)\) harus terlebih dahulu bergerak dari
\((0,0)\) ke
\((4,7)\text{,}\) lalu menyelesaikan perjalanannya dengan lintasan dari
\((4,7)\) ke
\((10,10)\text{.}\)
Banyaknya lintasan dari
\((0,0)\) ke
\((4,7)\) adalah
\(\binom{11}{4} = 330\text{.}\)
Banyaknya lintasan dari
\((4,7)\) ke
\((10,10)\) adalah
\(\binom{9}{3} = 84\text{.}\) (Lintasan-lintasan tersebut memiliki panjang 9 dengan 6 langkah dalam arah
\(x\text{.}\))
Sekarang gabungkan keduanya dengan... tunggu, prinsip yang mana? Untuk memperoleh lintasan dari
\((0,0)\) ke
\((10,10)\) yang melalui
\((4,7)\text{,}\) kita perlu terlebih dahulu memilih lintasan dari
\((0,0)\) ke
\((4,7)\text{,}\) kemudian
menyambungkan lintasan dari
\((4,7)\) ke
\((10,10)\text{.}\) Jadi, apakah kita menggunakan prinsip penjumlahan?
Bukan! Ingat bahwa prinsip penjumlahan menggabungkan dua himpunan hasil. Jika menerapkan prinsip penjumlahan, kita akan memperoleh himpunan lebih besar yang memuat
\(330 + 84\) lintasan dari kedua himpunan secara terpisah. Tidak satu pun merupakan lintasan lengkap yang ingin kita cacah. Kita ingin menggabungkan berbagai elemen dalam himpunan-himpunan hasil menurut setiap kombinasi yang mungkin. Karena itulah prinsip perkalian tepat digunakan di sini.
Dengan demikian, jumlah seluruh lintasan yang ingin kita cacah adalah
\(330 \cdot 84 = 27720\text{.}\)
Prinsip perkalian juga dapat diperumum untuk lebih dari dua kejadian.
Contoh 3.2.10.
Ada berapa pelat nomor yang dapat dibuat dari tiga huruf yang diikuti tiga digit angka?
Penyelesaian.
Di sini terdapat enam kejadian: huruf pertama, huruf kedua, huruf ketiga, digit pertama, digit kedua, dan digit ketiga. Masing-masing dari tiga kejadian pertama dapat terjadi dengan 26 cara; masing-masing dari tiga kejadian terakhir dapat terjadi dengan 10 cara. Jadi, menurut prinsip perkalian, jumlah seluruh pelat nomor adalah
\(26\cdot 26\cdot 26 \cdot 10 \cdot 10 \cdot 10\text{.}\)
Apakah hal ini masuk akal? Pikirkan cara kita memilih sebuah pelat nomor. Ada berapa pilihan? Pertama, kita harus memilih huruf pertama. Terdapat 26 pilihan. Untuk setiap pilihan tersebut, terdapat 26 pilihan bagi huruf kedua: 26 huruf kedua jika huruf pertama A, 26 huruf kedua jika huruf pertama B, dan seterusnya. Kita menjumlahkan 26 dengan dirinya sendiri sebanyak 26 kali. Atau, dengan lebih cepat: terdapat
\(26 \cdot 26\) pilihan untuk dua huruf pertama.
Selanjutnya, untuk setiap pilihan dua huruf pertama, kita memiliki 26 pilihan bagi huruf ketiga. Artinya, terdapat 26 pilihan huruf ketiga setelah dua huruf pertama AA, 26 pilihan huruf ketiga setelah awalan AB, dan seterusnya. Terdapat
\(26 \cdot 26\) kelompok pilihan yang masing-masing berisi
\(26\) pilihan huruf ketiga, sehingga seluruhnya ada
\((26\cdot26)\cdot 26\) pilihan bagi tiga huruf pertama. Untuk setiap dari
\(26\cdot26\cdot26\) pilihan huruf ini, kita memiliki sejumlah pilihan bagi digit-digit yang tersisa.
Bahkan, terdapat tepat 1000 pilihan angka. Kita dapat melihatnya karena terdapat 1000 bilangan tiga digit (000 hingga 999). Terdapat 10 pilihan untuk digit pertama, 10 untuk digit kedua, dan 10 untuk digit ketiga. Menurut prinsip perkalian, kita mengalikannya:
\(10\cdot 10 \cdot 10 = 1000\text{.}\)
Secara keseluruhan, terdapat
\(26^3\) pilihan bagi ketiga huruf dan
\(10^3\) pilihan bagi ketiga angka, sehingga kita memiliki total
\(26^3 \cdot 10^3\) pilihan pelat nomor.
Jawaban contoh sebelumnya menggunakan eksponen. Jadi, adakah
prinsip eksponensial yang perlu kita pelajari? Kita tidak memisahkannya sebagai prinsip tersendiri karena tidak ada perbedaan dalam cara kita memikirkan pembentukan himpunan hasil. Namun, kita akan sering melihat prinsip perkalian diterapkan pada kejadian yang sama yang diulang beberapa kali. Berikut dua contohnya.
Contoh 3.2.11.
Misalkan Anda melempar dadu bersisi 12 sebanyak tujuh kali dan mencatat angka yang muncul setelah setiap lemparan. Ada berapa barisan tujuh hasil lemparan yang mungkin?
Penyelesaian.
Setiap lemparan dapat memberikan 12 hasil berbeda, sehingga menurut prinsip perkalian, jumlah seluruh barisan adalah
\(12^7\text{.}\)
Contoh 3.2.12.
Ada berapa piza berbeda yang dapat dibuat jika tersedia 10 pilihan taburan dan Anda boleh menggunakan berapa pun banyaknya taburan pada piza?
Penyelesaian.
Jika ingin menerapkan prinsip perkalian, kita harus memandang kejadian majemuk berupa pemilihan piza sebagai hasil penggabungan sejumlah kejadian individual menurut setiap kombinasi yang mungkin. Apa saja kejadian tersebut? Pertanyaan ini memiliki beberapa jawaban, tetapi jawaban berikut paling berguna.
Pertama, putuskan apakah Anda ingin menambahkan ikan teri pada piza. Kejadian ini dapat memberikan dua hasil (ya atau tidak untuk ikan teri). Kedua, putuskan apakah Anda ingin menambahkan zaitun hitam. Kemudian bacon Kanada, tomat potong dadu, dan seterusnya. Setiap kejadian memiliki dua hasil, dan kita harus menggabungkan hasil dari kesepuluh kejadian ini untuk membentuk satu hasil yang bersesuaian dengan satu piza. Jadi, menurut prinsip perkalian, terdapat
\(2^{10}\) piza yang mungkin.
Sebagai catatan, pendekatan lain terhadap persoalan ini adalah “mengodekan” setiap piza sebagai string bit, dengan 1 berarti taburan disertakan dan 0 berarti tidak. Dengan demikian, banyaknya piza sama dengan banyaknya string bit yang panjangnya 10. Setiap bit dalam string memiliki dua nilai yang mungkin, sehingga terdapat
\(2^{10}\) string 10-bit.
Hati-hati: “dan” tidak berarti “dikali”. Sebagai contoh, ada berapa kartu remi yang sekaligus berwarna merah dan merupakan kartu bergambar? Bukan
\(26 \cdot 12\text{.}\) Jawabannya adalah 6, dan kita perlu mengetahui sifat kartu remi untuk menjawab pertanyaan tersebut.
Contoh 3.2.13. Mencacah Fungsi.
Ada berapa fungsi
\(f:\{1,2,3,4,5\} \to \{a,b,c,d\}\text{?}\)
Penyelesaian.
Ingat bahwa fungsi memetakan setiap elemen domain ke tepat satu elemen kodomain. Untuk menentukan sebuah fungsi, kita hanya perlu menentukan citra setiap elemen domain. Ke mana 1 dapat dipetakan? Terdapat 4 pilihan. Ke mana 2 dapat dipetakan? Sekali lagi, terdapat 4 pilihan. Di sini kita memiliki 5 “kejadian” (memilih citra suatu elemen domain), yang masing-masing dapat terjadi dengan 4 cara (pilihan bagi citra tersebut). Dengan demikian, terdapat
\(4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 4^5\) fungsi.
Ini bukan sekadar contoh penggunaan prinsip perkalian dalam suatu persoalan pencacahan tertentu. Di sini kita memperoleh interpretasi umum bagi penerapan tertentu prinsip perkalian dengan menggunakan objek matematika yang didefinisikan secara ketat, yaitu fungsi. Setiap kali suatu persoalan pencacahan menanyakan banyaknya hasil dari kejadian yang diulang, kita dapat menafsirkannya sebagai pertanyaan tentang banyaknya fungsi dari
\(\{1,2,\ldots, n\}\) (dengan
\(n\) adalah banyaknya pengulangan kejadian) ke
\(\{1,2,\ldots,k\}\) (dengan
\(k\) adalah banyaknya cara kejadian tersebut dapat terjadi).
Subbagian Menggabungkan Prinsip
Mari kita kembali ke pertanyaan
Selidiki! pada bagian ini: ada berapa cara memilih dua kartu dari satu set standar berisi 52 kartu sehingga kartu pertama berwarna merah dan kartu kedua merupakan kartu bergambar?
Persoalan ini agak menyerupai prinsip perkalian karena hasil-hasilnya terdiri atas pasangan kartu. Terdapat 26 kartu merah yang menjadi hasil bagi kejadian pertama dan 12 kartu bergambar yang menjadi hasil bagi kejadian kedua. Namun, jawabannya bukan
\(26 \cdot 12\text{.}\) Masalahnya, meskipun kartu pertama dapat dipilih dengan 26 cara, tidak benar bahwa
untuk setiap pilihan tersebut terdapat 12 cara memilih kartu kedua. Jika kartu pertama sekaligus berwarna merah dan merupakan kartu bergambar, hanya akan tersisa 11 pilihan bagi kartu kedua.
Dalam
Subbab 3.3 kita akan mempelajari beberapa cara menyesuaikan pencacahan ketika kejadian-kejadian tidak saling lepas. Namun, dengan berhati-hati, kita dapat menyelesaikan persoalan kartu ini sekarang. Perhatikan seluruh himpunan hasil dua kartu. Dapatkah kita membagi hasil-hasil tersebut menjadi dua himpunan yang saling lepas (agar prinsip penjumlahan dapat diterapkan), sedemikian sehingga setiap himpunan dapat dibentuk menggunakan prinsip perkalian?
Dari semua hasil, pertama-tama kita cacah hasil yang diawali dengan kartu merah yang bukan kartu bergambar. Di antara 26 kartu merah, terdapat 6 kartu bergambar, sehingga terdapat 20 kartu merah yang bukan kartu bergambar. Untuk setiap kartu ini, terdapat 12 kartu bergambar yang dapat dipilih sebagai kartu kedua. Menurut prinsip perkalian, banyaknya hasil dua kartu yang diawali dengan kartu merah bukan bergambar adalah
\(20 \cdot 12 = 240\text{.}\)
Sekarang, hasil mana yang belum kita cacah? Tepat hasil dua kartu yang diawali dengan kartu merah bergambar. Terdapat 6 pilihan kartu pertama, dan untuk setiap pilihan terdapat 11 pilihan kartu kedua. Jadi, banyaknya hasil dua kartu yang diawali dengan kartu merah bergambar adalah
\(6 \cdot 11 = 66\text{.}\)
Terakhir, terapkan prinsip penjumlahan pada dua himpunan hasil yang saling lepas ini untuk memperoleh jumlah seluruh hasil dua kartu, yaitu
\(240 + 66 = 306\text{.}\)
Kita menutup bagian ini dengan dua contoh tambahan tentang penggunaan prinsip penjumlahan dan prinsip perkalian secara bersama-sama dalam satu persoalan pencacahan.
Contoh 3.2.14.
Ada berapa lintasan kisi dari
\((0,0)\) ke
\((9,9)\) yang melalui
\((2,6)\) atau
\((6,2)\text{?}\)
Penyelesaian.
Kita beruntung karena tidak ada lintasan dari
\((0,0)\) ke
\((9,9)\) yang melalui
\((2,6)\) sekaligus
\((6,2)\text{.}\) Artinya, kita dapat menerapkan prinsip penjumlahan pada dua himpunan hasil: lintasan yang melalui
\((2,6)\) dan lintasan yang melalui
\((6,2)\text{.}\) Kita akan menerapkan prinsip perkalian untuk menentukan banyaknya lintasan dalam masing-masing himpunan hasil yang saling lepas ini.
Setiap lintasan dari
\((0,0)\) ke
\((9,9)\) yang melalui
\((2,6)\) merupakan konkatenasi lintasan dari
\((0,0)\) ke
\((2,6)\) dan lintasan dari
\((2,6)\) ke
\((9,9)\text{.}\) Terdapat
\(\binom{8}{2} = 28\) lintasan untuk bagian pertama dan
\(\binom{10}{7} = 120\) lintasan untuk bagian kedua. Jadi, penerapan prinsip perkalian memberikan
\(28 \cdot 120 = 3360\) lintasan yang melalui
\((2,6)\text{.}\)
Banyaknya lintasan dari \((0,0)\) ke \((9,9)\) yang melalui \((6,2)\) dapat dihitung dengan cara serupa sebagai
\begin{equation*}
\binom{8}{6} \cdot \binom{10}{3} = 28 \cdot 120 = 3360
\end{equation*}
(dan setelah dipikirkan, tidak mengherankan bahwa kedua bilangan ini sama karena setiap lintasan yang melalui \((2,6)\) dapat dicerminkan untuk membentuk lintasan yang melalui \((6,2)\)).
Dengan demikian, jumlah seluruh lintasan yang melalui
\((2,6)\) atau
\((6,2)\) adalah
\(3360 + 3360 = 6720\text{.}\)
Contoh 3.2.15.
Ada berapa bilangan dua digit yang hanya menggunakan digit dari
\(\{1,2,3,4,5\}\) dan memiliki
jumlah digit genap?
Penyelesaian.
Pertama, pikirkan himpunan hasilnya. Beberapa bilangan dua digit dengan jumlah digit genap adalah
\(11, 13, 15, 22, 24, 31, \ldots\text{.}\) Mungkin tidak terlalu sulit untuk menuliskan semuanya (dan itu merupakan cara yang baik untuk memeriksa pekerjaan kita). Meskipun demikian, mari kita mencoba menggunakan prinsip penjumlahan dan prinsip perkalian.
Apa yang kita perhatikan dari semua bilangan ini? Agar jumlahnya genap, tampaknya kedua digit harus genap atau keduanya harus ganjil. Kita dapat meninjau kedua kasus tersebut dan mencacah setiap kasus menggunakan prinsip perkalian.
Mencacah bilangan “ganjil-ganjil”: terdapat tiga pilihan untuk digit pertama dan tiga pilihan untuk digit kedua. Jadi, terdapat
\(3 \cdot 3 = 9\) bilangan ganjil-ganjil.
Mencacah bilangan “genap-genap”: terdapat dua pilihan untuk digit pertama dan dua pilihan untuk digit kedua. Jadi, terdapat
\(2 \cdot 2 = 4\) bilangan genap-genap.
Jika digabungkan, terdapat
\(9 + 4 = 13\) bilangan dua digit dengan jumlah digit genap.
