Subbab2.5Koefisien Binomial yang Muncul di Mana-Mana
Dalam bagian ini, kita menyajikan beberapa soal kombinatorial yang dapat diselesaikan dengan menggunakan koefisien binomial, meskipun pada pandangan pertama soal-soal tersebut tampaknya tidak berkaitan dengan himpunan.
Asisten kantor sedang membagikan perlengkapan. Ada berapa cara untuk membagikan 18 map yang identik kepada empat pegawai kantor—Audrey, Bart, Cecilia, dan Darren—dengan syarat tambahan bahwa masing-masing menerima setidaknya satu map?
Bayangkan map-map tersebut ditempatkan dalam satu baris. Terdapat 17 celah di antaranya. Dari celah-celah itu, pilih tiga dan letakkan sebuah pemisah pada masing-masing celah terpilih. Pilihan ini membagi map-map tersebut menjadi empat kelompok yang tidak kosong. Kelompok pertama diberikan kepada Audrey, kelompok kedua kepada Bart, etc. Jadi, jawabannya adalah \(C(17,3)\text{.}\) Dalam Gambar 2.22, skema ini digambarkan dengan Audrey menerima \(6\) map, Bart menerima \(1\text{,}\) Cecilia \(4\text{,}\) dan Darren 7.
Delapan belas ikon map tersusun dalam satu baris. Tiga garis pemisah vertikal membaginya, dari kiri ke kanan, menjadi kelompok berisi 6, 1, 4, dan 7 map untuk Audrey, Bart, Cecilia, dan Darren.
Andaikan kita mengerjakan kembali soal sebelumnya, tetapi menghapus syarat bahwa masing-masing dari keempat pegawai harus menerima setidaknya satu map. Sekarang, ada berapa cara untuk melakukan pembagian tersebut?
Penyelesaiannya melibatkan semacam “trik”. Pertama, kita mengubah soal ini menjadi soal yang sudah kita ketahui cara menyelesaikannya. Caranya adalah dengan menambah jatah setiap orang secara semu sebanyak satu. Dengan kata lain, jika Bart sebenarnya akan menerima \(7\) map, kita mengatakan bahwa ia akan menerima \(8\text{.}\) Kita juga menambah banyaknya map secara semu sebanyak \(4\text{,}\) satu untuk masing-masing dari empat orang. Jadi, sekarang bayangkan satu baris yang terdiri atas \(22=18+4\) map. Sekali lagi, pilih \(3\) celah. Pilihan ini menentukan jatah tak nol untuk setiap orang. Jatah yang sebenarnya satu lebih sedikit—dan mungkin saja nol. Jadi, jawabannya adalah \(C(21,3)\text{.}\)
Sekali lagi kita mempunyai soal yang sama seperti sebelumnya, tetapi sekarang kita ingin menghitung banyaknya pembagian ketika hanya Audrey dan Cecilia yang dipastikan menerima sebuah map. Bart dan Darren boleh tidak menerima map. Triknya sekarang ialah menambah jatah Bart dan Darren secara semu, tetapi membiarkan jatah Audrey dan Cecilia apa adanya. Jadi, jawabannya adalah \(C(19,3)\) .
dengan berbagai kumpulan syarat pada nilai \(x_1,x_2,\dots,x_6\text{.}\) Beberapa syarat tersebut mengharuskan pertidaksamaan itu sebenarnya berupa persamaan.
\(C(537,6)\text{,}\) jika semua \(x_i > 0\) dan pertidaksamaannya ketat (Bayangkan sebuah variabel baru \(x_7\) yang menyatakan sisa. Perhatikan bahwa \(x_7\) harus positif.);
\(C(543,6)\text{,}\) jika semua \(x_i \ge 0\) dan pertidaksamaannya ketat (Tambahkan sebuah variabel baru \(x_7\) seperti di atas. Sekarang, hanya variabel inilah yang harus positif.); dan
Salah satu soal enumerasi klasik, yang berkaitan dengan beberapa soal lain, adalah menghitung lintasan kisi. Sebuah lintasan kisi pada bidang merupakan barisan pasangan terurut bilangan bulat:
Kisi yang terdiri atas 14 kolom dan 9 baris titik, sesuai dengan koordinat 0 sampai 13 dan 0 sampai 8. Titik di sudut kiri bawah berlabel \((0,0)\text{,}\) sedangkan titik di sudut kanan atas berlabel \((13,8)\text{.}\) Sebuah lintasan menghubungkan kedua titik itu dengan hanya bergerak ke kanan dan ke atas: tiga langkah ke kanan, dua ke atas, satu ke kanan, satu ke atas, satu ke kanan, tiga ke atas, lima ke kanan, satu ke atas, satu ke kanan, satu ke atas, lalu dua ke kanan.
Untuk memahami mengapa rumus ini berlaku, perhatikan bahwa lintasan kisi tidak lain adalah string atas \(X\) dengan \(X=\{H,V\}\text{,}\) dengan \(H\) menyatakan langkah horizontal dan \(V\) menyatakan langkah vertikal. Dalam kasus ini, terdapat tepat \((p-m)+(q-n)\) langkah, dan \(p-m\) di antaranya merupakan langkah horizontal.
Misalkan \(n\) sebuah bilangan bulat tak negatif. Banyaknya lintasan kisi dari \((0,0)\) ke \((n,n)\) yang tidak pernah berada di atas garis diagonal \(y=x\) adalah bilangan Catalan
Untuk melihat bahwa rumus ini berlaku, pertimbangkan keluarga \(\cgP\) yang terdiri atas semua lintasan kisi dari \((0,0)\) ke \((n,n)\text{.}\) Lintasan kisi dari \((0,0)\) ke \((n,n)\) tidak lain adalah string atas \(\{H,V\}\) dengan panjang \(2n\) yang memuat tepat \(n\) karakter \(H\text{.}\) Jadi, \(|\cgP|=\binom{2n}{n}\text{.}\) Kita menggolongkan lintasan dalam \(\cgP\) sebagai baik jika lintasan itu tidak pernah berada di atas diagonal; jika tidak, lintasan tersebut buruk. Sebuah string \(s\in\cgP\) bersifat baik jika banyaknya karakter \(V\) dalam setiap segmen awal \(s\) tidak pernah melebihi banyaknya karakter \(H\text{.}\) Sebagai contoh, string “\(HHVHVVHHHVHVVV\)” merupakan lintasan kisi yang baik dari \((0,0)\) ke \((7,7)\text{,}\) sedangkan lintasan “\(HVHVHHVVVHVHHV\)” bersifat buruk. Dalam kasus kedua, perhatikan bahwa setelah \(9\) langkah, terdapat \(5\) karakter \(V\) dan \(4\) karakter \(H\text{.}\)
Misalkan \(\cgG\) dan \(\cgB\) masing-masing menyatakan keluarga semua lintasan baik dan semua lintasan buruk. Tentu saja, tujuan kita adalah menentukan \(|\cgG|\text{.}\)
Pertimbangkan sebuah lintasan \(s\in\cgB\text{.}\) Terdapat bilangan bulat terkecil \(i\) sedemikian sehingga \(s\) memuat lebih banyak karakter \(V\) daripada karakter \(H\) dalam \(i\) posisi pertamanya. Dari sifat minimal \(i\text{,}\) mudah dilihat bahwa \(i\) harus ganjil (jika tidak, kita dapat mundur satu langkah). Jika kita menetapkan \(i=2j+1\text{,}\) maka dalam \(2j+1\) posisi pertama \(s\) terdapat tepat \(j\) karakter \(H\) dan \(j+1\) karakter \(V\text{.}\) Sisa \(2n-2j-1\) posisi (“ekor \(s\)”) memuat \(n-j\) karakter \(H\) dan \(n-j-1\) karakter \(V\text{.}\) Sekarang kita mengubah \(s\) menjadi string baru \(s'\) dengan mengganti setiap \(H\) pada ekor \(s\) dengan \(V\) dan setiap \(V\) pada ekor \(s\) dengan \(H\text{,}\) serta membiarkan \(2j+1\) posisi awal tetap. Sebagai contoh, lihat Gambar 2.29. Di sana, lintasan \(s\) digambar dengan garis penuh, sedangkan \(s'\) berimpit dengan \(s\) hingga lintasan melintasi garis \(y=x\text{,}\) kemudian dilanjutkan sebagai lintasan bergaris putus-putus. String \(s'\) memiliki panjang \(2n\) dengan \((n-j)+(j+1) = n+1\) karakter \(V\) dan \((n-j-1)+j=n-1\) karakter \(H\text{,}\) sehingga \(s'\) merupakan lintasan kisi dari \((0,0)\) ke \((n-1,n+1)\text{.}\) Perhatikan bahwa terdapat \(\binom{2n}{n-1}\) lintasan kisi semacam itu.
Kisi titik menampilkan dua lintasan yang berawal di (0,0). Lintasan bergaris penuh s berakhir di (n,n). Lintasan bergaris putus-putus s’ berimpit dengan s hingga lintasan pertama kali melintasi y=x; setelah itu, setiap langkah horizontal dan vertikal ditukar, sehingga s’ berakhir di (n-1,n+1).
Kita juga dapat mengamati bahwa transformasi yang telah diuraikan sebenarnya merupakan bijeksi antara \(\cgB\) dan \(\cgP'\text{,}\) yaitu himpunan lintasan kisi dari \((0,0)\) ke \((n-1,n+1)\text{.}\) Untuk melihat kebenarannya, perhatikan bahwa setiap lintasan \(s'\) dalam \(\cgP'\) harus melintasi garis \(y=x\text{.}\) Jadi, terdapat saat pertama lintasan itu melintasinya, misalkan pada posisi \(i\text{.}\) Sekali lagi, \(i\) harus ganjil, sehingga \(i=2j+1\text{,}\) dan terdapat \(j\) karakter \(H\) serta \(j+1\) karakter \(V\) dalam \(i\) posisi pertama \(s'\text{.}\) Oleh karena itu, ekor \(s'\) memuat \(n+1-(j+1)=n-j\) karakter \(V\) dan \((n-1)-j\) karakter \(H\text{.}\) Dengan menukar karakter \(H\) dan \(V\) dalam ekor \(s'\text{,}\) kita memperoleh string baru \(s\) yang memuat \(n\) karakter \(H\) dan \(n\) karakter \(V\text{,}\) sehingga string itu menyatakan lintasan kisi dari \((0,0)\) ke \((n,n)\text{.}\) Namun, lintasan tersebut tetap buruk karena kita tidak mengubah bagian awal lintasan, yang mengakibatkan lintasan melintasi garis \(y=x\) pada posisi \(i\text{.}\) Oleh karena itu, \(|\cgB|=|\cgP'|\text{,}\) sehingga
Perlu diperhatikan bahwa dalam Contoh 2.28, kita menggunakan dua teknik enumerasi yang umum: memberikan bijeksi antara dua kelas objek, dengan salah satu kelas “lebih mudah” dihitung daripada yang lain, serta menghitung objek yang tidak ingin kita enumerasi lalu mengurangkan banyaknya dari jumlah keseluruhan.
