Subbab 7.1 Pengantar

Kita memulai bab ini dengan sebuah contoh sederhana.

Contoh 7.1.

Misalkan \(X\) adalah himpunan \(63\) mahasiswa yang mengikuti mata kuliah kombinatorika terapan di sebuah universitas teknologi besar. Misalkan terdapat \(47\) mahasiswa program studi ilmu komputer dan \(51\) mahasiswa laki-laki. Kita juga mengetahui bahwa \(45\) mahasiswa laki-laki mengambil program studi ilmu komputer. Berapa banyak mahasiswi di kelas tersebut yang tidak mengambil program studi ilmu komputer?

Penyelesaian.

Meskipun diagram Venn yang mungkin sudah sering Anda lihat tidak selalu merupakan ilustrasi terbaik (terutama jika Anda mencoba menafsirkannya seolah-olah berskala), mari kita gunakan diagram semacam itu sebagai langkah awal. Dalam Gambar 7.2, kita dapat melihat bagaimana kelompok-kelompok dalam situasi tersebut saling bertumpang tindih.

dijelaskan secara terperinci setelah gambar — Gambar 7.2. Diagram Venn untuk kelas kombinatorika terapan

Sekarang dapat kita lihat bahwa yang dicari ialah banyaknya mahasiswa di dalam persegi panjang putih tetapi di luar kedua oval berwarna, yaitu mahasiswi yang tidak mengambil program studi ilmu komputer. Untuk menghitungnya, kita dapat mulai dengan mengurangkan banyaknya mahasiswa laki-laki (wilayah biru) dari jumlah seluruh mahasiswa di kelas, lalu mengurangkan banyaknya mahasiswa program studi ilmu komputer (wilayah kuning). Namun, dengan cara itu kita telah mengurangkan wilayah yang bertumpang tindih (mahasiswa laki-laki program studi ilmu komputer) dua kali, sehingga jumlah tersebut harus ditambahkan kembali. Jadi, banyaknya mahasiswi di kelas yang tidak mengambil program studi ilmu komputer adalah

\begin{equation*} 63 - 51 - 47 + 45 = 10. \end{equation*}

Contoh 7.3.

Jenis masalah lain yang dengan mudah memperlihatkan penerapan teknik semacam ini adalah generalisasi masalah enumerasi solusi bilangan bulat suatu persamaan. Dalam Bab 2, kita telah membahas cara menghitung banyaknya solusi persamaan seperti

\begin{equation*} x_1 + x_2 + x_3 + x_4 = 100, \end{equation*}

dengan \(x_1>0\text{,}\) \(x_2, x_3 \geq 0\text{,}\) dan \(2\leq x_4\leq 10\text{.}\) Namun, kita belum membahas situasi ketika ditambahkan batasan \(x_3\leq 7\text{.}\) Contoh sebelumnya memberi petunjuk mengenai cara menangani masalah yang telah dimodifikasi ini.

Pertama, mari kita susun ulang masalah tersebut agar batas bawah setiap variabel berbentuk \(x_i\geq 0\text{.}\) Dengan demikian, masalahnya berubah menjadi enumerasi solusi bilangan bulat dari

\begin{equation*} x_1' + x_2 + x_3 + x_4' = 97 \end{equation*}

dengan \(x_1',x_2,x_3,x_4'\geq 0\text{,}\) \(x_3\leq 7\text{,}\) dan \(x_4'\leq 8\text{.}\) (Selanjutnya, \(x_1 = x_1'+1\) dan \(x_4 = x_4' + 2\) menghasilkan solusi yang kita inginkan.) Untuk menghitung banyaknya solusi bilangan bulat persamaan ini dengan \(x_3\leq 7\) dan \(x_4'\leq 8\text{,}\) kita harus mengecualikan setiap solusi dengan \(x_3 \gt 7\) atau \(x_4' \gt 8\text{.}\) Terdapat \(C(92,3)\) solusi dengan \(x_3 \gt 7\text{,}\) sedangkan banyaknya solusi dengan \(x_4'\gt 8\) adalah \(C(91,3)\text{.}\) Pada tahap ini, kita mungkin tergoda untuk langsung mengurangkan \(C(92,3)\) dan \(C(91,3)\) dari \(C(100,3)\text{,}\) yaitu jumlah seluruh solusi dengan semua variabel tak negatif. Namun, kita harus berhati-hati. Jika dilakukan, solusi yang sekaligus memenuhi \(x_3\gt 7\) dan \(x_4'\gt 8\) akan terhapus dua kali. Untuk memperhitungkannya, perhatikan bahwa terdapat \(C(83,3)\) solusi yang sekaligus memenuhi \(x_3\gt 7\) dan \(x_4'\gt 8\text{.}\) Dengan menambahkan kembali bilangan ini setelah pengurangan, kita memastikan bahwa solusi yang memenuhi \(x_3\gt 7\) dan \(x_4'\gt 8\) tidak masuk ke dalam hitungan akhir dan juga tidak dikecualikan lebih dari sekali. Jadi, jumlah seluruh solusi adalah

\begin{equation*} \binom{100}{3} - \binom{92}{3} - \binom{91}{3} + \binom{83}{3} = 6516. \end{equation*}

Dari contoh-contoh ini, mulai terlihat sebuah pola yang membawa kita menuju kerangka yang lebih umum. Secara umum, kita akan meninjau sebuah himpunan \(X\) dan keluarga \(\mathcal{P}=\{P_1,P_2,\dots,P_m\}\) yang terdiri atas sifat-sifat. Untuk setiap \(x\in X\) dan setiap \(i=1,2,\dots,m\text{,}\) \(x\) memenuhi \(P_i\) atau tidak memenuhinya; tidak ada ambiguitas. Tujuan akhirnya ialah menentukan banyaknya elemen \(X\) yang tidak memenuhi satu pun sifat dalam \(\mathcal{P}\text{.}\) Dalam Contoh 7.1, kita dapat menetapkan sifat \(P_1\) sebagai “mengambil program studi ilmu komputer” dan sifat \(P_2\) sebagai “laki-laki”. Dengan demikian, banyaknya mahasiswa yang tidak memenuhi \(P_1\) maupun \(P_2\) adalah banyaknya mahasiswi yang mengambil program studi selain ilmu komputer, tepat seperti jumlah yang diminta. Apa sifat \(P_1\) dan \(P_2\) untuk Contoh 7.3?

Mari kita tinjau tiga contoh yang melibatkan himpunan sifat yang lebih besar. Sifat-sifat ini akan muncul kembali pada bagian-bagian selanjutnya dalam bab ini ketika inklusi–eksklusi diterapkan pada situasi yang lebih rumit. Ingat bahwa di seluruh buku ini kita menggunakan notasi \([n]\) untuk himpunan \(\{1,2,\dots,n\}\) apabila \(n\) adalah bilangan bulat positif.

Contoh 7.4.

Misalkan \(m\) dan \(n\) adalah bilangan bulat positif tetap, dan misalkan \(X\) terdiri atas semua fungsi dari \([n]\) ke \([m]\text{.}\) Untuk setiap \(i=1,2,\dots,m\) dan setiap fungsi \(f\in X\text{,}\) kita katakan bahwa \(f\) memenuhi \(P_i\) jika tidak ada \(j\) sedemikian sehingga \(f(j)=i\text{.}\) Dengan kata lain, \(i\) tidak berada dalam citra atau keluaran fungsi \(f\text{.}\)

Sebagai contoh khusus, misalkan \(n=5\) dan \(m=3\text{.}\) Fungsi yang diberikan oleh tabel berikut memenuhi \(P_1\text{,}\) tetapi tidak memenuhi \(P_2\) ataupun \(P_3\text{.}\)

\(i\)	1	2	3	4	5
\(f(i)\)	2	3	2	2	3

Contoh 7.5.

Misalkan \(m\) adalah bilangan bulat positif tetap, dan misalkan \(X\) terdiri atas semua bijeksi dari \([m]\) ke \([m]\text{.}\) Elemen-elemen \(X\) disebut permutasi. Untuk setiap \(i=1,2,\dots,m\) dan setiap permutasi \(\sigma\in X\text{,}\) kita katakan bahwa \(\sigma\) memenuhi \(P_i\) jika \(\sigma(i)=i\text{.}\)

Sebagai contoh, permutasi \(\sigma\) pada \([5]\) yang diberikan oleh tabel berikut memenuhi \(P_3\) dan \(P_5\text{,}\) tetapi tidak memenuhi \(P_i\) yang lain.

\(i\)	1	2	3	4	5
\(\sigma(i)\)	2	4	3	1	5

Perhatikan bahwa pada contoh sebelumnya kita dapat saja mengatakan bahwa \(\sigma\) memenuhi sifat \(P_i\) jika \(\sigma(i)\neq i\text{.}\) Namun, karena tujuan kita adalah menghitung banyaknya elemen yang tidak memenuhi satu pun sifat, dengan pilihan itu kita justru akan menghitung banyaknya permutasi yang memenuhi \(\sigma(i)=i\) untuk setiap \(i=1,2,\dots,m\text{.}\) Untuk menyelesaikan tugas ini tampaknya tidak diperlukan banyak teori—tentu saja jumlahnya satu.

Contoh 7.6.

Misalkan \(m\) dan \(n\) adalah bilangan bulat positif tetap, dan misalkan \(X=[n]\text{.}\) Untuk setiap \(i=1,2,\dots,m\) dan setiap \(j\in X\text{,}\) kita katakan bahwa \(j\) memenuhi \(P_i\) jika \(i\) merupakan pembagi dari \(j\text{.}\) Dengan kata lain, bilangan bulat positif yang memenuhi sifat \(P_i\) tidak lain adalah kelipatan \(i\text{.}\)

Sekilas, himpunan sifat ini mungkin tampak paling rumit di antara yang telah kita bahas. Namun, contoh konkret akan membantu menghilangkan kebingungan. Misalkan \(n=m=15\text{.}\) Sifat mana saja yang dipenuhi oleh \(12\text{?}\) Pembagi-pembagi \(12\) adalah \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(4\text{,}\) \(6\text{,}\) dan \(12\text{,}\) sehingga \(12\) memenuhi \(P_1\text{,}\) \(P_2\text{,}\) \(P_3\text{,}\) \(P_4\text{,}\) \(P_6\text{,}\) dan \(P_{12}\text{.}\) Sebagai perbandingan, perhatikan bahwa \(7\) hanya memenuhi sifat \(P_1\) dan \(P_7\) karena hanya kedua bilangan itulah pembaginya.

Sblm Ke Atas Lnjt