Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 3.3 Hasil yang Tidak Saling Lepas

Subbagian Pratinjau Bagian

Selidiki!
Sebuah kampanye pemasaran dari mulut ke mulut yang baru-baru ini dilakukan oleh The Pie Hole menyurvei para pelanggan mengenai pai yang mereka sukai. Mereka ditanya apakah menyukai pai (A) apel, (B) blueberry, atau (C) ceri (responden menjawab ya atau tidak untuk setiap jenis pai, dan boleh menjawab ya untuk lebih dari satu jenis). Tabel berikut menunjukkan hasil survei tersebut.
🔗
Pai yang disukai: A B C AB AC BC ABC
Banyak orang: 20 13 26 9 15 7 5
Berapa banyak responden yang menyukai sedikitnya satu jenis pai? Jelaskan juga mengapa jawabannya bukan 95.
🔗
🔗
Dalam Subbab 3.2 kita telah mempelajari prinsip penjumlahan sebagai cara menggabungkan dua (atau lebih) himpunan hasil yang saling lepas. Apa yang terjadi jika hasil-hasilnya tidak saling lepas?
🔗
Kita perlu melakukan sesuatu yang berbeda. Misalnya, ketika menghitung banyaknya kartu permainan yang merupakan kartu bergambar atau kartu merah, kita tidak dapat menerapkan prinsip penjumlahan lalu menyatakan bahwa terdapat \(12 + 26 = 38\) kartu. Masalahnya adalah tepat enam kartu sekaligus merupakan kartu bergambar dan kartu merah. Ada beberapa cara untuk menangani hal ini yang akan kita pelajari dalam bagian ini.
🔗

Lembar Kerja Kegiatan Pratinjau

1.
Perhatikan delapan string bit berpanjang 3. Mari kita tentukan banyaknya string yang diawali dengan 1 atau berbobot 2 (yakni, memuat tepat dua angka 1).
🔗
(a)
Daftarkan semua string bit berpanjang 3 yang diawali dengan 1.
🔗
🔗
(b)
Daftarkan semua string bit berpanjang 3 yang berbobot 2.
🔗
🔗
(c)
Sekarang daftarkan semua string bit berpanjang 3 yang diawali dengan 1 atau berbobot 2. Namun, bekerjalah dengan hemat: jangan menyusunnya dari awal. Gunakan daftar Anda dari kedua tugas di atas.
🔗
🔗
(d)
Berapa banyak string dalam daftar-daftar tersebut?
  • String yang diawali dengan 1:
    🔗
    🔗
  • String berbobot 2:
    🔗
    🔗
  • String yang diawali dengan 1 atau berbobot 2:
    🔗
    🔗
  • String yang diawali dengan 1 dan berbobot 2:
    🔗
    🔗
🔗
🔗
🔗
2.
Bagaimana Anda menggabungkan kedua daftar di atas? Jelaskan cara Anda melakukannya. Kemudian pikirkan metode lain yang dapat digunakan, dan jelaskan bagaimana metode itu berbeda.
🔗
🔗
3.
Xiang dan Omari sedang membahas matematikawan favorit mereka sepanjang sejarah. Xiang memiliki daftar 7 matematikawan favorit, sedangkan Omari memiliki daftar 5 matematikawan. Mereka mendapati bahwa 3 matematikawan terdapat dalam kedua daftar. Berapa banyak matematikawan dalam daftar gabungan mereka?
🔗
🔗
🔗
🔗

Subbagian Menghitung dengan Diagram Venn

Untuk memahami cara menangani penggabungan himpunan hasil yang tidak saling lepas, akan berguna jika kita memakai beberapa notasi dari teori himpunan, yang akan kita tinjau secara singkat di sini.
🔗
Misalkan \(A\) adalah himpunan hasil untuk kejadian pertama dan \(B\) adalah himpunan hasil untuk kejadian kedua. Ketika kita menanyakan banyaknya cara salah satu kejadian dapat terjadi, himpunan hasil yang baru terdiri atas semua hasil yang berada dalam \(A\text{,}\) atau \(B\text{,}\) atau keduanya. Himpunan ini tidak lain adalah gabungan dari himpunan \(A\) dan \(B\text{,}\) yang ditulis \(A \cup B\text{.}\)
🔗
Prinsip penjumlahan hanya berlaku ketika tidak ada hasil yang termasuk dalam kedua kejadian. Elemen-elemen yang terdapat dalam himpunan \(A\) maupun \(B\) merupakan elemen-elemen dalam irisan keduanya, yang ditulis \(A \cap B\text{.}\) Irisan dua himpunan itu sendiri merupakan suatu himpunan. Jika himpunan \(A\) dan \(B\) saling lepas, maka tidak ada elemen dalam irisannya, sehingga irisan tersebut merupakan himpunan kosong, yang ditulis \(\emptyset\text{.}\)
🔗
Kita menghitung banyaknya hasil, sehingga yang benar-benar kita perhatikan adalah ukuran (atau kardinalitas) himpunan-himpunan tersebut. Ukuran suatu himpunan \(X\) kita tulis sebagai \(\card{X}\text{.}\)
🔗
Dengan notasi ini, kita dapat menyatakan kembali prinsip penjumlahan sebagai berikut.
🔗
Sekarang perhatikan apa yang terjadi pada prinsip penjumlahan ketika himpunan-himpunannya TIDAK saling lepas. Misalkan kita ingin menentukan \(\card{A \cup B}\) dan mengetahui bahwa \(\card{A} = 10\) serta \(\card{B} = 8\text{.}\) Jika kita mengetahui bahwa kedua himpunan itu saling lepas, maka \(\card{A \cup B}\) akan bernilai 18. Namun, jika kedua himpunan itu tidak diketahui saling lepas, kita memerlukan informasi tambahan. Kita harus mengetahui berapa banyak dari 8 elemen dalam \(B\) yang juga merupakan elemen \(A\text{.}\) Misalkan kita juga mengetahui bahwa \(\card{A \cap B} = 6\text{.}\) Sekarang kita dapat mengatakan secara tepat berapa banyak elemen yang berada dalam \(A\text{,}\) dan, di antara elemen-elemen tersebut, berapa banyak yang berada dalam \(B\) dan berapa banyak yang tidak (6 dari 10 elemen berada dalam \(B\text{,}\) sehingga 4 berada dalam \(A\) tetapi tidak dalam \(B\)). Kita dapat mengisi diagram Venn sebagai berikut:
🔗
Dua lingkaran beririsan yang berlabel A dan B. Di dalam daerah yang dibatasi oleh kedua lingkaran terdapat angka 6. Angka 4 berada di daerah di dalam A tetapi di luar B. Angka 2 berada di daerah di dalam B tetapi di luar A.
Ini menyatakan bahwa terdapat 6 elemen dalam \(A \cap B\text{,}\) 4 elemen dalam \(A\) tetapi tidak dalam \(B\) (yang dapat kita tulis sebagai \(\card{A \setminus B} = 4\)), dan 2 elemen dalam \(B\) tetapi tidak dalam \(A\) (ditulis \(\card{B \setminus A} = 2\)). Sekarang ketiga himpunan ini memang saling lepas, sehingga kita dapat menggunakan prinsip penjumlahan untuk menentukan banyaknya elemen dalam \(A \cup B\text{.}\) Banyaknya adalah \(6 + 4 + 2 = 12\text{.}\)
🔗

Contoh 3.3.2.

Berapa banyak string bit berpanjang \(7\) dan berbobot \(4\) yang diawali dengan \(11\) atau diakhiri dengan \(00\text{,}\) atau keduanya?
🔗
Penyelesaian.
Misalkan \(A\) adalah himpunan string bit berpanjang \(7\) dan berbobot \(4\) yang diawali dengan \(11\text{.}\) Kita memiliki \(\card{A} = \binom{5}{2} = 10\text{.}\) Misalkan \(B\) adalah himpunan string bit berpanjang \(7\) dan berbobot \(4\) yang diakhiri dengan \(00\text{.}\) Kita memiliki \(\card{B} = \binom{5}{4} = 5\text{.}\)
🔗
Namun, tidak benar bahwa \(\card{A \cup B} = 10 + 5 = 15\text{,}\) sebab string seperti 1101100 diawali dengan \(11\) sekaligus diakhiri dengan \(00\text{.}\) String itu termasuk dalam 10 string yang diawali dengan \(11\) dan lima string yang diakhiri dengan \(00\text{.}\) Kita harus menentukan banyaknya string yang termasuk dalam \(A\) sekaligus \(B\text{.}\) Kita memiliki
\begin{equation*} \card{A \cap B} = \binom{3}{2} = 3 \end{equation*}
(dan memang terdapat tiga string dalam irisan: 1111000, 1110100, dan 1101100).
🔗
Sekarang kita dapat mengisi diagram Venn:
🔗
Dua lingkaran beririsan yang berlabel A dan B. Di dalam daerah yang dibatasi oleh kedua lingkaran terdapat angka 3. Angka 7 berada di daerah di dalam A tetapi di luar B. Angka 2 berada di daerah di dalam B tetapi di luar A.
Lingkaran untuk \(A\) memuat total 10 elemen, yaitu 3 elemen yang juga termasuk dalam \(B\) dan 7 elemen lain yang hanya termasuk dalam \(A\text{.}\) Lingkaran untuk \(B\) memuat total 5 elemen, yaitu 3 elemen yang juga termasuk dalam \(A\) dan 2 elemen lain yang hanya termasuk dalam \(B\text{.}\) Banyaknya elemen dalam \(A \cup B\) adalah jumlah elemen di setiap daerah
\begin{equation*} \card{A \cup B} = 7+3+2 = 12\text{.} \end{equation*}
🔗
🔗
🔗
Kita dapat melakukan hal serupa untuk tiga himpunan.
🔗

Contoh 3.3.3.

Sebanyak 41 mahasiswa mengikuti ujian dalam tiga mata kuliah, yaitu Aljabar, Biologi, dan Kimia. Tabel berikut menunjukkan banyaknya mahasiswa yang tidak lulus dalam setiap mata kuliah dan dalam berbagai kombinasinya:
🔗
Mata kuliah: A B C AB AC BC ABC
Tidak lulus: 12 5 8 2 6 3 1
Berapa banyak mahasiswa yang tidak lulus sedikitnya satu mata kuliah?
🔗
Penyelesaian.
Jawabannya bukan 37, meskipun jumlah bilangan-bilangan di atas adalah 37. Sebagai contoh, meskipun 12 mahasiswa tidak lulus Aljabar, 2 di antaranya juga tidak lulus Biologi, 6 juga tidak lulus Kimia, dan 1 di antaranya tidak lulus ketiga mata kuliah tersebut. Bahkan, 1 mahasiswa yang tidak lulus ketiga mata kuliah itu dihitung sebanyak 7 kali dalam total 37. Untuk memperjelas, mari kita anggap mahasiswa yang tidak lulus Aljabar sebagai elemen himpunan \(A\text{,}\) dan demikian pula untuk himpunan \(B\) dan \(C\text{.}\) Satu mahasiswa yang tidak lulus ketiga mata kuliah merupakan satu-satunya elemen himpunan \(A \cap B \cap C\text{.}\) Jadi, dalam diagram Venn:
🔗
Tiga lingkaran beririsan yang berlabel A, B, dan C. Daerah pusat di dalam ketiga lingkaran memuat angka 1.
Sekarang mari kita isi irisan-irisan lainnya. Kita mengetahui bahwa \(A\cap B\) memuat 2 elemen, tetapi 1 elemen sudah dihitung. Jadi, kita harus menempatkan angka 1 di daerah tempat \(A\) dan \(B\) beririsan (tetapi tidak dengan \(C\)). Dengan cara serupa, kita menghitung kardinalitas \((A\cap C) \setminus B\text{,}\) dan \((B \cap C) \setminus A\text{:}\)
🔗
Tiga lingkaran beririsan yang berlabel A, B, dan C. Daerah pusat di dalam ketiga lingkaran memuat angka 1. Daerah di atasnya, di dalam A dan B tetapi di luar C, memuat angka 1. Daerah di dalam A dan C tetapi di luar B memuat angka 5. Daerah di dalam B dan C tetapi di luar A memuat angka 2.
Selanjutnya, kita menentukan bilangan-bilangan yang harus ditempatkan di daerah-daerah yang tersisa, termasuk di luar ketiga lingkaran. Bilangan terakhir ini adalah banyaknya mahasiswa yang lulus semua mata kuliah:
🔗
Tiga lingkaran beririsan yang berlabel A, B, dan C. Daerah pusat di dalam ketiga lingkaran memuat angka 1. Daerah di atasnya, di dalam A dan B tetapi di luar C, memuat angka 1. Daerah di dalam A dan C tetapi di luar B memuat angka 5. Daerah di dalam B dan C tetapi di luar A memuat angka 2. Daerah yang hanya di dalam A memuat angka 5; daerah yang hanya di dalam B memuat angka 1; daerah yang hanya di dalam C memuat angka 0. Angka 26 berada di luar ketiga lingkaran.
Kita memperoleh angka 5 untuk daerah “hanya \(A\)” karena seluruh lingkaran untuk \(A\) harus memuat total 12, sedangkan 7 sudah diperhitungkan. Dengan cara serupa, kita menghitung bahwa daerah “hanya \(B\)” memuat hanya 1 mahasiswa dan daerah “hanya \(C\)” tidak memuat mahasiswa.
🔗
Jadi, banyaknya mahasiswa yang tidak lulus sedikitnya satu mata kuliah adalah 15 (jumlah bilangan dalam ketujuh daerah saling lepas yang berada di dalam gabungan ketiga himpunan). Banyaknya mahasiswa yang lulus ketiga mata kuliah adalah 26: jumlah seluruh mahasiswa, 41, dikurangi 15 mahasiswa yang tidak lulus sedikitnya satu mata kuliah.
🔗
Perhatikan bahwa kita juga dapat menjawab pertanyaan-pertanyaan lain. Misalnya, berapa banyak mahasiswa yang hanya tidak lulus Kimia? Tidak ada. Berapa banyak yang lulus Aljabar tetapi tidak lulus Biologi maupun Kimia? Ini bersesuaian dengan daerah di dalam \(B\) dan \(C\) tetapi di luar \(A\text{,}\) yang memuat 2 mahasiswa.
🔗
🔗
🔗
Berikut suatu fakta matematika yang menarik.
\begin{equation*} 12 + 5 + 8 - 2 - 6 - 3 + 1 = 15\text{.} \end{equation*}
Apakah sekadar kebetulan bahwa cara menggabungkan banyaknya mahasiswa yang tidak lulus setiap mata kuliah dalam contoh di atas menghasilkan banyaknya mahasiswa yang tidak lulus sedikitnya satu mata kuliah? Hal ini menunjukkan bahwa mungkin ada cara yang lebih sederhana untuk menentukan ukuran gabungan himpunan-himpunan yang tidak saling lepas.
🔗
🔗

Subbagian Prinsip Inklusi–Eksklusi

Akan berguna jika kita dapat menuliskan sebuah rumus aljabar yang merangkum apa yang telah kita lakukan dalam contoh-contoh sebelumnya. Lebih baik lagi jika rumus aljabar ini merupakan perumuman dari kasus ketika himpunan-himpunannya memang saling lepas.
🔗
Perhatikan kembali contoh dengan \(\card{A} = 10\text{,}\) \(\card{B} = 8\text{,}\) dan \(\card{A \cap B} = 6\text{.}\) Kita menyatakan bahwa \(\card{A \cup B} = 12\text{,}\) yang diperoleh dengan menjumlahkan \(4 + 6 + 2\text{.}\)
🔗
Jika \(A\) dan \(B\) saling lepas, maka \(\card{A \cup B}\) akan bernilai \(\card{A} + \card{B} = 10 + 8 = 18\text{.}\) Kita melihat bahwa hasil itu lebih besar tepat sebesar 6, yang kebetulan sama dengan \(\card{A \cap B}\text{.}\) Jadi, kita dapat menduga,
\begin{equation*} \card{A \cup B} = \card{A} + \card{B} - \card{A \cap B}\text{.} \end{equation*}
Ini masuk akal! Ketika kita menambahkan banyaknya elemen dalam \(A\) dengan banyaknya elemen dalam \(B\text{,}\) kita telah menghitung enam elemen yang termasuk dalam kedua himpunan tepat dua kali. Jadi, jika kita mengurangkannya sekali, setiap elemen tersebut terhitung tepat satu kali.
🔗
Dengan kata lain, kita memperoleh:
🔗

Contoh 3.3.5.

Berapa banyak string bit berpanjang \(7\) dan berbobot \(4\) yang diawali dengan \(11\) atau diakhiri dengan \(00\text{,}\) atau keduanya? Gunakan Teorema 3.3.4 dan bandingkan dengan Contoh 3.3.2.
🔗
Penyelesaian.
Kita memiliki \(\card{A} = \binom{5}{2} = 10\text{,}\) \(\card{B} = \binom{5}{4} = 5\text{,}\) dan \(\card{A \cap B} = \binom{3}{2} = 3\text{.}\) Oleh karena itu:
\begin{equation*} \card{A \cup B} = 10 + 5 - 3 = 12\text{.} \end{equation*}
Ini masuk akal karena tiga string bit yang diawali dengan \(11\) dan diakhiri dengan \(00\) terhitung dalam 10 string yang diawali dengan \(11\) dan sekali lagi dalam 5 string yang diakhiri dengan \(00\text{.}\) Jadi, sebelum mengurangkannya, kita telah menghitung string-string tersebut satu kali terlalu banyak.
🔗
🔗
🔗
Untuk tiga himpunan, kita juga dapat menghitung elemen-elemen dalam gabungannya dengan secara cermat mengurangi elemen-elemen yang telah kita hitung beberapa kali. Karena ada lebih banyak cara himpunan-himpunan tersebut dapat bertumpang tindih, rumusnya lebih rumit.
🔗
Untuk menentukan berapa banyak elemen yang berada dalam sedikitnya salah satu dari \(A\text{,}\) \(B\text{,}\) atau \(C\text{,}\) kita menjumlahkan semua elemen dalam masing-masing himpunan tersebut. Namun, ketika melakukan itu, setiap elemen yang berada dalam \(A\) dan \(B\) dihitung dua kali. Demikian pula, setiap elemen yang berada dalam \(A\) dan \(C\) dihitung dua kali, begitu juga elemen dalam \(B\) dan \(C\text{,}\) sehingga kita mengurangi setiap kelompok tersebut satu kali dari jumlah kita. Namun, bagaimana dengan elemen-elemen yang berada dalam \(A \cap B \cap C\) (dalam ketiga himpunan)? Kita telah menambahkannya tiga kali, tetapi juga mengurangkannya tiga kali. Elemen-elemen tersebut belum terhitung. Jadi, pada akhir perhitungan kita menambahkannya kembali.
🔗

Contoh 3.3.7.

Berapa banyak bilangan dalam \(\{1, 2, \ldots, 50\}\) yang merupakan kelipatan 2, 3, atau 5?
🔗
Penyelesaian.
Di antara bilangan dalam \(\{1, 2, \ldots, 50\}\text{,}\) misalkan \(A\) adalah himpunan kelipatan 2, \(B\) adalah himpunan kelipatan 3, dan \(C\) adalah himpunan kelipatan 5. Kita memiliki \(\card{A} = 25\text{,}\) \(\card{B} = 16\text{,}\) dan \(\card{C} = 10\text{.}\) (Bilangan-bilangan ini dapat diperoleh melalui pembagian; misalnya, karena sepertiga bilangan merupakan kelipatan tiga, kita dapat menghitung \(50/3 = 16.66\text{,}\) sehingga terdapat 16 kelipatan 3 dalam himpunan tersebut.) Beberapa bilangan dalam himpunan tersebut merupakan kelipatan 2 sekaligus 3, seperti \(6, 12, 18,\ldots\text{,}\) yakni semua kelipatan 6. Terdapat \(\card{A \cap B} = 8\) bilangan semacam itu. Dengan cara serupa, terdapat \(\card{A \cap C} = 5\) kelipatan 2 sekaligus 5 (kelipatan 10), dan \(\card{B \cap C} = 3\) kelipatan 3 sekaligus 5 (kelipatan 15). Terdapat \(\card{A \cap B \cap C} = 1\) kelipatan ketiganya (hanya bilangan 30).
🔗
Dengan menggunakan Teorema 3.3.6, kita memperoleh:
\begin{equation*} \card{A \cup B \cup C} = 25 + 16 + 10 - 8 - 5 - 3 + 1 = 36\text{.} \end{equation*}
🔗
Mari kita gunakan contoh ini untuk memahami teorema tersebut dengan lebih baik. Perhatikan bilangan \(21\text{.}\) Dalam himpunan mana bilangan ini dihitung? Bilangan tersebut berada dalam \(B\text{,}\) tetapi tidak dalam \(A\) ataupun \(C\text{,}\) sehingga dihitung di antara 16 kelipatan \(3\) dan tidak dihitung dalam himpunan lain. Dengan demikian, bilangan itu terhitung tepat sekali dalam hitungan lengkap kita. Hal yang sama berlaku bagi semua bilangan lain yang merupakan kelipatan hanya salah satu dari \(2\text{,}\) \(3\text{,}\) atau \(5\text{.}\)
🔗
Bilangan \(18\) berada dalam himpunan \(A\) dan \(B\text{,}\) sehingga juga berada dalam \(A \cap B\text{.}\) Bilangan ini dihitung di antara 25 kelipatan \(2\text{,}\) 16 kelipatan \(3\text{,}\) dan 8 kelipatan \(6\text{.}\) Jadi, bilangan ini ditambahkan dua kali ke dalam total kita dan dikurangkan sekali, yang berarti bilangan tersebut terhitung tepat satu kali. Hal yang sama berlaku bagi semua bilangan yang termasuk dalam tepat dua dari masing-masing himpunan.
🔗
Bagaimana dengan \(30\text{?}\) Bilangan ini termasuk dalam semua himpunan. Oleh karena itu, bilangan ini ditambahkan ke dalam total kita tiga kali, ketika kita menambahkan kelipatan \(2\text{,}\) \(3\text{,}\) dan \(5\text{.}\) Namun, bilangan ini juga dikurangkan tiga kali, satu kali untuk setiap pasangan dari ketiga himpunan. Jadi, bilangan ini sama sekali tidak terhitung dalam total kita... sampai kita menambahkannya kembali pada langkah terakhir, sehingga akhirnya terhitung tepat sekali.
🔗
🔗
🔗
Proses menambahkan, kemudian mengurangkan, lalu menambahkan kembali, dan seterusnya disebut Prinsip Inklusi–Eksklusi, atau cukup disebut PIE. Prinsip ini dapat diterapkan pada berapa pun banyaknya himpunan, tetapi rumusnya menjadi semakin rumit seiring bertambahnya himpunan. Sebagai contoh, berikut bentuk PIE untuk empat himpunan.
\begin{align*} \card{A \cup B \cup C \cup D} = \amp \card{A} + \card{B} + \card{C} + \card{D} \\ - \amp \card{A \cap B} - \card{A \cap C} - \card {A \cap D} - \card{B \cap C} - \card{B \cap D} - \card{C \cap D}\\ + \amp \card{A \cap B \cap C} + \card{A \cap B \cap D} + \card{A \cap C \cap D} + \card{B \cap C \cap D}\\ - \amp \card{A \cap B \cap C \cap D} \text{.} \end{align*}
Fiuh! Untuk lima himpunan, rumusnya adalah... hanya bercanda. Meskipun tidak menuliskannya, semoga kita semua dapat membayangkan apa yang harus ditulis. Dalam praktiknya, PIE untuk lebih dari tiga himpunan hanya digunakan ketika kita dapat menyederhanakan perhitungan dengan mengenali bahwa, misalnya, semua irisan dua himpunan akan berukuran sama. Beberapa contoh mengenai hal ini dipelajari dalam Subbab 3.8.
🔗
🔗

Subbagian Tumpang Tindih dan Prinsip Perkalian

Semua yang telah kita bahas sejauh ini dalam bagian ini berkaitan dengan cara prinsip penjumlahan diterapkan ketika himpunan-himpunan hasil tidak saling lepas. Apakah kita perlu mencemaskan tumpang tindih dengan cara serupa ketika menerapkan prinsip perkalian?
🔗
Tidak juga.
🔗
Salah satu kegunaan prinsip perkalian adalah menghitung peluang, dan dalam konteks tersebut kita memang membedakan kejadian yang saling bebas dan yang saling bergantung. Kita akan mempelajari hal ini lebih lanjut dalam Subbab 3.7. Pada dasarnya, untuk menentukan peluang terjadinya dua kejadian, kita dapat mengalikan peluang masing-masing jika dan hanya jika kedua kejadian tersebut saling bebas: hasil salah satu kejadian tidak memengaruhi hasil kejadian lainnya.
🔗
Meskipun menentukan peluang berkaitan erat dengan menghitung hasil, prinsip perkalian itu sendiri tidak mensyaratkan bahwa himpunan-himpunan hasil harus saling lepas atau membedakan kejadian yang saling bergantung dan yang saling bebas. Yang penting adalah banyaknya hasil untuk kejadian kedua tidak berubah berdasarkan hasil mana yang terjadi pada kejadian pertama.
🔗
Salah satu pembedaan yang memang sering kita buat ketika menerapkan prinsip perkalian adalah apakah hasil suatu kejadian dapat “diulang.” Perhatikan contoh berikut.
🔗

Contoh 3.3.8.

Berapa banyak kata 3 huruf (barisan tiga huruf) yang ada jika,
  1. pengulangan diperbolehkan?
    🔗
  2. pengulangan tidak diperbolehkan?
    🔗
🔗
Penyelesaian.
Dengan menerapkan prinsip perkalian secara cermat, kita menggabungkan tiga kejadian: \(A\) adalah kejadian memilih huruf pertama, \(B\) adalah kejadian memilih huruf kedua, dan \(C\) adalah kejadian memilih huruf ketiga. Jika kita ingin menghitung banyaknya kata ketika huruf dalam kata boleh diulang, maka setiap kejadian memuat 26 hasil. Jadi, banyaknya kata 3 huruf adalah \(26^3 = 17,576\) ketika pengulangan diperbolehkan.
🔗
Ketika pengulangan tidak diperbolehkan, banyaknya hasil untuk kejadian \(A\) tetap 26, tetapi banyaknya hasil untuk \(B\) hanya 25. Apa pun hasil kejadian \(A\text{,}\) huruf tersebut tidak dapat dipilih untuk posisi kedua dalam kata. Demikian pula, apa pun hasil kejadian \(A\) dan \(B\text{,}\) banyaknya hasil untuk kejadian \(C\) selalu 24, yaitu sembarang huruf yang tidak dipilih dalam dua kejadian pertama. Jadi, banyaknya kata 3 huruf tanpa huruf berulang adalah \(26\cdot 25\cdot 24 = 15,600\text{.}\)
🔗
Agak aneh bahwa himpunan hasil yang sebenarnya untuk kejadian \(B\) berbeda bagi setiap kemungkinan hasil kejadian \(A\text{.}\) Namun, hal ini tidak menjadi masalah selama ukuran himpunan hasilnya tidak berubah.
🔗
🔗
🔗
Selanjutnya, kita akan mempelajari masalah seperti contoh sebelumnya secara jauh lebih mendalam dalam Subbab 3.4. Namun sebelumnya, berikut contoh terakhir ketika prinsip perkalian TIDAK dapat digunakan dengan mudah.
🔗

Contoh 3.3.9.

Jelaskan mengapa prinsip perkalian TIDAK berlaku untuk pertanyaan pencacahan berikut: Berapa banyak kata 3 huruf yang huruf-hurufnya tersusun menurut urutan alfabet?
🔗
Penyelesaian.
Hal pertama yang mungkin kita coba adalah menjadikan kejadian \(A\) sebagai pemilihan huruf pertama, \(B\) sebagai pemilihan huruf kedua, dan \(C\) sebagai pemilihan huruf ketiga. Terdapat 26 hasil untuk kejadian \(A\text{.}\) Berapa banyak hasil untuk kejadian \(B\text{?}\) Jika kita memilih \(w\) sebagai huruf pertama, kita dapat memilih satu huruf dari himpunan \(\{w, x, y, z\}\) sebagai huruf kedua, sehingga tampaknya terdapat \(4\) hasil untuk kejadian \(B\text{.}\) Namun, jika kita memilih \(a\) sebagai huruf pertama, sembarang huruf dapat digunakan sebagai huruf kedua, sehingga kejadian \(B\) memiliki \(26\) hasil. Celaka!
🔗
Masalahnya adalah banyaknya hasil untuk huruf kedua (dan ketiga) dalam kata berubah bergantung pada hasil kejadian sebelumnya. Kejadian-kejadian tersebut tidak saling bebas, dan lebih dari itu, banyaknya hasil pada setiap tahap juga bergantung pada hasil sebelumnya, sehingga prinsip perkalian tidak berlaku.
🔗
🔗
🔗
Kita akan melihat cara menjawab masalah pencacahan di atas ketika huruf boleh diulang dalam Subbab 3.5. Jika kita membatasi pertanyaannya lebih lanjut dan mensyaratkan bahwa huruf-hurufnya berbeda (serta tersusun menurut urutan alfabet), kita sudah mengetahui cara menjawabnya. Karena untuk sembarang himpunan tiga huruf terdapat tepat satu kata 3 huruf yang menyusun huruf-huruf tersebut menurut urutan alfabet, kita cukup menghitung banyaknya himpunan tiga huruf. Banyaknya adalah \(\binom{26}{3}\text{.}\) Lalu kita tinggal melihat segitiga Pascal untuk mendapatkan nilainya... aduh. Segitiga kita tidak sampai sejauh itu. Sepertinya kita perlu memikirkan cara menghitung nilainya tanpa segitiga tersebut. Mari lanjutkan!
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Manakah di antara pilihan berikut yang paling tepat menggambarkan kegunaan Prinsip Inklusi–Eksklusi?
🔗
  • Untuk menghitung ukuran gabungan dua atau lebih himpunan yang tidak harus saling lepas.
    🔗
  • Benar. Perhatikan bahwa Prinsip Inklusi–Eksklusi tetap berlaku dengan baik meskipun himpunan-himpunannya saling lepas; semua irisannya hanya berukuran 0.
  • Untuk menghitung ukuran gabungan dua atau lebih himpunan, asalkan semuanya saling lepas.
    🔗
  • Jika himpunan-himpunannya saling lepas, Anda tidak perlu menggunakan Prinsip Inklusi–Eksklusi. Anda cukup menjumlahkan ukuran himpunan-himpunan tersebut.
  • Untuk menghitung ukuran irisan himpunan hasil dari dua atau lebih kejadian yang saling bebas.
    🔗
  • Prinsip Inklusi–Eksklusi melibatkan irisan himpunan, tetapi tidak digunakan untuk menentukan ukuran irisan tersebut.
  • Untuk menentukan ukuran irisan himpunan hasil dari kejadian-kejadian yang saling bergantung.
    🔗
  • Prinsip Inklusi–Eksklusi melibatkan irisan himpunan, tetapi tidak digunakan untuk menentukan ukuran irisan tersebut.
🔗

2.

Mengapa Prinsip Inklusi–Eksklusi menambahkan ukuran irisan tiga himpunan, bukan mengurangkannya? Jelaskan dengan kata-kata Anda sendiri.
🔗
🔗

3.

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

Latihan Soal Latihan

1.

Misalkan Anda memiliki himpunan \(A\) dan \(B\) dengan \(\card{A} = 11\) dan \(\card{B} = 19\text{.}\)
🔗
(a)
Berapakah nilai terbesar yang mungkin untuk \(\card{A \cap B}\text{?}\)
🔗
🔗
(b)
Berapakah nilai terkecil yang mungkin untuk \(\card{A \cap B}\text{?}\)
🔗
🔗
(c)
Apa saja nilai yang mungkin untuk \(\card{A \cup B}\text{?}\)
🔗
\(\le \card{A \cup B} \le\)
🔗
🔗
🔗

2.

Jika \(\card{A} = 7\) dan \(\card{B} = 11\text{,}\) berapakah \(\card{A \cup B} + \card{A \cap B}\text{?}\)
🔗
🔗

3.

Sekelompok mahasiswa ditanya tentang kebiasaan mereka menonton televisi. Di antara mahasiswa yang disurvei, 29 mahasiswa menonton The Walking Dead, 24 menonton The Blacklist, dan 27 menonton Game of Thrones. Selain itu, 10 menonton The Walking Dead dan The Blacklist, 13 menonton The Walking Dead dan Game of Thrones, serta 17 menonton The Blacklist dan Game of Thrones. Ada 8 mahasiswa yang menonton ketiga acara tersebut. Berapa banyak mahasiswa yang disurvei menonton sedikitnya satu dari ketiga acara itu?
🔗
🔗

4.

Dalam sebuah survei baru-baru ini, 115 mahasiswa menyatakan apakah mereka menyukai kentang tumbuk, kentang goreng, atau kentang panggang dua kali. Sebanyak 53 mahasiswa menyukai kentang tumbuk, 51 menyukai kentang goreng, dan 70 menyukai kentang panggang dua kali. Selain itu, 22 mahasiswa menyukai kentang tumbuk dan kentang goreng, 33 menyukai kentang goreng dan kentang panggang dua kali, 36 menyukai kentang tumbuk dan kentang panggang dua kali, serta 16 menyukai ketiga olahan tersebut. Berapa banyak mahasiswa yang sama sekali tidak menyukai kentang? Jelaskan mengapa jawaban Anda benar.
🔗
🔗

5.

Berapa banyak string bit sepanjang \(14\) yang memenuhi syarat berikut?
  1. Diawali substring 011.
    🔗
    🔗
  2. Berbobot 8 (yaitu, memuat tepat 8 angka 1) dan diawali substring 011.
    🔗
    🔗
  3. Diawali \(011\) atau diakhiri \(01\) (atau keduanya).
    🔗
    🔗
  4. Berbobot 8 dan diawali \(011\) atau diakhiri \(01\) (atau keduanya).
    🔗
    🔗
🔗
🔗

6.

Ada berapa banyak \(n \in \{1,2, \ldots, 790\}\) yang merupakan kelipatan dari sedikitnya salah satu di antara 8, 5, dan 9?
🔗
Petunjuk.
Untuk menentukan banyak bilangan yang habis dibagi 8 dan 9, misalnya, hitung \(790/(8\cdot9)\) lalu bulatkan ke bawah.
🔗
🔗
🔗

7.

Berapa banyak bilangan bulat positif yang kurang dari 850 dan merupakan kelipatan dari 9, 5, atau 2? Gunakan prinsip inklusi–eksklusi.
🔗
🔗

8.

Kita ingin membentuk “kata” sepanjang 12 huruf dengan hanya menggunakan \(n =7\) huruf pertama dalam alfabet. Sebagai contoh, jika \(n = 5\text{,}\) kita dapat menggunakan 5 huruf pertama, \(\{a, b, c, d, e \}\text{.}\) (Ingat, kata di sini hanyalah untaian huruf dan tidak harus berupa kata yang benar-benar ada dalam bahasa Inggris.)
  1. Ada berapa kata seluruhnya?
    🔗
    🔗
  2. Ada berapa kata yang tidak memuat huruf berulang?
    🔗
    🔗
  3. Ada berapa kata yang diawali subkata “ade”?
    🔗
    🔗
  4. Ada berapa kata yang diawali “ade”, diakhiri “be”, atau memenuhi keduanya?
    🔗
    🔗
  5. Di antara kata-kata tanpa huruf berulang, ada berapa yang juga tidak memuat subkata “bed”?
    🔗
    🔗
🔗
🔗

9.

Gridtown, AS, selain memiliki toko donat yang sangat baik, terkenal karena kisi jalan dan jalan rayanya yang tertata tepat. Jalan membentang dari timur ke barat, sedangkan jalan raya dari utara ke selatan, di seluruh kota tanpa berbelok dan tanpa terputus oleh taman, sekolah, atau semacamnya.
🔗
Misalkan Anda tinggal di persimpangan Jalan ke-5 dan Jalan Raya ke-5, serta bekerja di persimpangan Jalan ke-18 dan Jalan Raya ke-18. Jadi, agar sampai di tempat kerja secepat mungkin, Anda harus menempuh 26 blok.
  1. Ada berapa rute berbeda yang dapat Anda tempuh ke tempat kerja jika ingin sampai secepat mungkin?
    🔗
    🔗
🔗
  1. Sekarang misalkan Anda ingin singgah membeli donat dalam perjalanan ke tempat kerja, di toko donat favorit Anda di persimpangan Jalan Raya ke-15 dan Jalan ke-14. Ada berapa rute ke tempat kerja yang melewati toko donat itu dan tetap merupakan rute terpendek?
    🔗
    🔗
🔗
  1. Bencana melanda Gridtown: ada lubang di Jalan Raya ke-6, di antara Jalan ke-7 dan Jalan ke-8. Ada berapa rute ke tempat kerja yang dapat Anda tempuh sambil menghindari ruas jalan yang buruk (dan berbahaya) itu?
    🔗
    🔗
🔗
  1. Lubang itu telah diperbaiki (syukurlah!) dan sebuah toko donat baru dibuka di persimpangan Jalan Raya ke-6 dan Jalan ke-7. Ada berapa rute ke tempat kerja yang melewati salah satu atau kedua toko donat? Petunjuk: gunakan prinsip inklusi-eksklusi (PIE).
    🔗
    🔗
🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Misalkan \(A\text{,}\) \(B\text{,}\) dan \(C\) adalah himpunan.
  1. Tentukan \(\card{(A \cup C)\setminus B}\) jika diketahui \(\card{A} = 50\text{,}\) \(\card{B} = 45\text{,}\) \(\card{C} = 40\text{,}\) \(\card{A\cap B} = 20\text{,}\) \(\card{A \cap C} = 15\text{,}\) \(\card{B \cap C} = 23\text{,}\) dan \(\card{A \cap B \cap C} = 12\text{.}\)
    🔗
  2. Nyatakan suatu himpunan menggunakan \(A\text{,}\) \(B\text{,}\) dan \(C\) yang berkardinalitas 26.
    🔗
🔗
Petunjuk.
Untuk bagian (a), Anda dapat menggunakan rumus PIE, tetapi untuk bagian (b), menggambar diagram Venn mungkin lebih membantu.
🔗
🔗
🔗

2.

Ada berapa banyak bilangan tiga digit (100 hingga 999) yang jumlah digit-digitnya genap? (Sebagai contoh, \(343\) memiliki jumlah digit yang genap: \(3+4+3 = 10\text{,}\) yang merupakan bilangan genap.) Tentukan jawabannya dan jelaskan mengapa jawaban itu benar dengan sedikitnya dua cara yang berbeda.
🔗
Petunjuk.
Anda dapat mempertimbangkan beberapa kasus. Sebagai contoh, sembarang bilangan berbentuk GANJIL-GANJIL-GENAP akan memiliki jumlah digit yang genap. Sebagai alternatif, ada berapa banyak bilangan tiga digit dengan jumlah digit genap jika dua digit pertamanya adalah 54? Bagaimana jika dua digit pertamanya adalah 19?
🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik