Subbab 1.2 Enumerasi
Banyak masalah dasar dalam kombinatorika melibatkan pencacahan banyaknya cara mendistribusikan objek ke dalam wadah—objek-objek tersebut mungkin dapat atau tidak dapat dibedakan, demikian pula wadahnya. Selain itu, wadah-wadah tersebut dapat disusun mengikuti suatu pola. Berikut beberapa contoh konkret.
Amanda memiliki tiga anak: Dawn, Keesha, dan Seth.
-
Amanda memiliki sepuluh lembar uang satu dolar dan memutuskan untuk memberikan seluruhnya kepada anak-anaknya. Ada berapa cara ia dapat melakukannya? Sebagai contoh, salah satu cara membagikan uang tersebut adalah memberikan empat dolar masing-masing kepada Dawn dan Keesha, sedangkan Seth menerima sisanya—dua dolar. Cara lain adalah memberikan seluruh uang kepada Keesha, pilihan yang mungkin tidak akan membuat Dawn dan Seth sangat senang. Perhatikan bahwa pertanyaan ini secara tersirat mengasumsikan Amanda tidak membedakan lembar-lembar uang satu dolar tersebut, misalnya dengan memeriksa nomor serinya secara cermat. Dengan kata lain, ia hanya perlu menentukan jumlah uang yang akan diterima masing-masing dari ketiga anaknya.
-
Jumlah uang yang dibagikan kepada ketiga anak membentuk suatu barisan yang, jika ditulis dalam urutan tak menaik, berbentuk \(a_1, a_2, a_3\) dengan \(a_1\ge a_2\ge a_3\) dan \(a_1+a_2+a_3=10\text{.}\) Ada berapa barisan seperti itu?
-
Misalkan Amanda memutuskan untuk memberikan sekurang-kurangnya satu dolar kepada setiap anak. Bagaimana hal ini mengubah jawaban untuk dua pertanyaan pertama?
-
Sekarang misalkan Amanda memiliki sepuluh buku, tepatnya 10 buku teratas dalam daftar buku terlaris New York Times, dan memutuskan untuk memberikannya kepada anak-anaknya. Ada berapa cara ia dapat melakukannya? Sekali lagi, terdapat asumsi tersirat—kesepuluh buku itu semuanya berbeda.
-
Misalkan kesepuluh buku diberi label \(B_1, B_2,\dots, B_{10}\text{.}\) Himpunan buku yang diberikan kepada ketiga anak saling lepas sepasang-sepasang dan gabungannya adalah \(\{B_1,B_2,\dots,B_{10}\}\text{.}\) Ada berapa himpunan berbeda berbentuk \(\{S_1, S_2, S_3\}\text{,}\) dengan \(S_1\text{,}\) \(S_2\text{,}\) dan \(S_3\) saling lepas sepasang-sepasang dan \(S_1\cup S_2\cup S_3=\{B_1,B_2,\dots,B_{10}\}\text{?}\)
-
Misalkan Amanda memutuskan untuk memberikan sekurang-kurangnya satu buku kepada setiap anak. Bagaimana hal ini mengubah jawaban untuk dua pertanyaan sebelumnya?
-
Bagaimana mungkin kita menjawab pertanyaan semacam ini jika sepuluh sebenarnya adalah sepuluh ribu (baiklah, sekarang kita tidak lagi berbicara tentang anak-anak!) dan tiga adalah tiga ribu? Dapatkah Anda menuliskan jawabannya pada satu halaman buku?
Sebuah kalung melingkar dengan jumlah enam manik-manik akan dirangkai menggunakan manik-manik dari tiga warna berbeda. Dalam Gambar 1.1, kami menampilkan empat kalung seperti itu—namun, perhatikan bahwa tiga kalung pertama sebenarnya merupakan kalung yang sama. Masing-masing memiliki tiga manik-manik merah, dua biru, dan satu hijau. Sebaliknya, kalung keempat memiliki jumlah manik-manik setiap warna yang sama, tetapi merupakan kalung yang berbeda.
Empat kalung melingkar dengan enam manik-manik berwarna merah, biru, dan hijau; tiga kalung pertama setara melalui rotasi, sedangkan kalung keempat berbeda.
-
Ada berapa kalung berbeda dengan enam manik-manik yang dapat dibentuk menggunakan tiga manik-manik merah, dua biru, dan satu hijau?
-
Ada berapa kalung berbeda dengan enam manik-manik yang dapat dibentuk menggunakan manik-manik merah, biru, dan hijau (tidak semua warna harus digunakan)?
-
Ada berapa kalung berbeda dengan enam manik-manik yang dapat dibentuk menggunakan manik-manik merah, biru, dan hijau jika ketiga warna harus digunakan?
-
Bagaimana mungkin kita menjawab pertanyaan-pertanyaan ini untuk kalung yang terdiri atas enam ribu manik-manik dengan tiga ribu warna berbeda? Perangkat lunak khusus apa yang diperlukan untuk memperoleh jawaban tepat, dan berapa lama perhitungannya akan berlangsung?
