Dalam permainan catur, benteng hanya dapat bergerak dalam garis lurus (bukan secara diagonal). Ada berapa cara benteng di sudut kiri atas dapat mencapai sudut kanan bawah papan jika hanya bergerak ke bawah dan ke kanan?
Selain itu, apa kaitannya persoalan ini dengan pencacahan banyaknya piza yang dapat Anda pesan jika Anda memilih separuh dari 14 taburan yang tersedia?
Angka 6 pada petak di baris dan kolom ke-3 menyatakan bahwa terdapat 6 lintasan berbeda menuju petak tersebut, meskipun benteng hanya perlu melewati empat petak untuk sampai ke sana. Salah satu lintasannya adalah DDRR (bawah, bawah, kanan, kanan). Tuliskan keenam lintasan tersebut.
Ada berapa lintasan menuju petak pada baris 4, kolom 2 (secara diagonal di bawah dan di sebelah kiri angka 6)? Tuliskan semua lintasan sebagai string D/R.
Lanjutkan mengisi papan catur, baik dengan mencacah string D/R secara langsung maupun dengan menggunakan pengamatan Anda dari tugas sebelumnya. Angka berapa yang terdapat di sudut kanan bawah papan catur?
Pada tahun 1653, Blaise Pascal, yang menelaah persoalan-persoalan yang kelak menjadi dasar teori peluang, menghimpun sejumlah fakta tentang susunan bilangan berbentuk segitiga dalam karyanya Risalah tentang Segitiga Aritmetika. Susunan bilangan ini telah muncul sejak abad ke-10 di Tiongkok, India, dan Persia. Kajian terhadap segitiga ini di Tiongkok dan Persia digunakan untuk apa yang kini kita sebut aljabar: mencari akar pangkat \(n\text{,}\) yang pada dasarnya berarti menyelesaikan persamaan polinomial. Dalam naskah-naskah India, bilangan-bilangan pada segitiga tersebut muncul sebagai jawaban atas persoalan pencacahan: dari enam rasa, berapa banyak kombinasi yang dapat dibuat dengan satu, dua, atau tiga rasa, dan seterusnya? Matematikawan Eropa pada abad ke-14 menyajikan segitiga ini sebagai tabel bilangan figuratif (bilangan yang dapat disusun dalam bentuk geometris), yang sebelumnya telah menjadi pokok utama karya Pythagoras dan para pengikutnya.
Tujuh belas baris pertama segitiga Pascal. Susunan segitiga dari segi enam; setiap baris memuat satu segi enam lebih banyak daripada baris di atasnya. Setiap segi enam memuat sebuah bilangan bulat: angka 1 berada pada tepi segitiga, sedangkan setiap bilangan bulat di bagian dalam segitiga merupakan jumlah dua bilangan bulat di atasnya.
Luangkan waktu sejenak untuk mengamati keindahan segitiga ini. Apa yang Anda perhatikan? Apa yang membuat Anda bertanya-tanya? Perhatikan secara khusus baris ke-5 (angka 1 pada baris teratas kita sebut baris 0, sehingga baris 5 adalah 1, 5, 10, 10, 5, 1). Bagaimana hubungan bilangan-bilangan pada baris ini dengan bilangan-bilangan di atasnya? Perhatikan bahwa \(5 = 1+4\) dan \(10 = 4+6\text{.}\) Apakah hal ini juga terjadi di bagian lain segitiga?
Memang, setiap bilangan pada segitiga merupakan jumlah dua bilangan di atasnya. Kita akan menggunakan sifat ini sebagai definisi segitiga Pascal. Dengan demikian, kita dapat membentuk sebanyak mungkin baris segitiga sesuai kebutuhan. Definisi aditif inilah yang digunakan di Tiongkok dan Persia untuk mencari akar pangkat \(n\text{;}\) penggunaan ini akan kita singgung secara singkat pada akhir bagian. Namun, kita tertarik pada persoalan pencacahan, sehingga tujuan utama kita sekarang adalah mengamati bagaimana bilangan-bilangan pada segitiga Pascal menjadi jawaban bagi berbagai persoalan pencacahan.
Berikut beberapa objek diskret yang tampaknya berbeda dan dapat kita cacah: lintasan kisi, string bit, subhimpunan, dan piza. Kita akan memberikan contoh untuk setiap jenis persoalan pencacahan tersebut (sekaligus menjelaskan apa yang dimaksud dengan objek-objek itu). Seperti yang akan kita lihat, bilangan-bilangan pada segitiga Pascal merupakan jawaban bagi semua persoalan ini.
Sebelum memulai, kita perlu memperkenalkan sedikit notasi. Mari kita beri nama setiap bilangan pada segitiga Pascal berdasarkan posisinya. Anggap setiap bilangan berada pada sebuah baris dan kolom: baris dihitung ke bawah mulai dari 0, sedangkan kolom dihitung dari kiri, juga mulai dari 0. Entri pada baris \(n\) dan kolom \(k\) dinotasikan dengan \(\binom{n}{k}\text{.}\) Sebagai contoh, \(\binom{6}{3} = 20\) karena itulah nilai pada baris 6, kolom 3. Karena alasan yang akan segera menjadi jelas, \(\binom{n}{k}\) dibaca “\(n\) pilih \(k\text{.}\)” Kita dapat menuliskan kembali segitiga tersebut menggunakan nama-nama ini:
Kisi bilangan bulat adalah himpunan semua titik pada bidang Kartesius yang koordinat \(x\) dan \(y\)-nya merupakan bilangan bulat. Jika Anda biasa menggambar grafik pada kertas berpetak, kisi adalah himpunan semua titik potong garis-garis petak tersebut.
Lintasan kisi adalah salah satu lintasan terpendek yang mungkin untuk menghubungkan dua titik pada kisi dengan hanya bergerak secara horizontal dan vertikal. Sebagai contoh, berikut tiga lintasan kisi yang mungkin dari titik \((0,0)\) ke \((3,2)\text{:}\)
Perhatikan bahwa agar lintasan tersebut merupakan lintasan terpendek yang mungkin, setiap langkah harus menuju ke kanan atau ke atas. Selain itu, dalam kasus ini, apa pun lintasan yang kita ambil, kita harus melangkah tiga kali ke kanan dan dua kali ke atas. Apa pun urutan langkahnya, selalu terdapat lima langkah. Jadi, setiap lintasan memiliki panjang lima.
Persoalan pencacahan yang akan kita ajukan adalah: ada berapa lintasan kisi antara \((0,0)\) dan \((3,2)\text{?}\) Dalam kasus ini, menggambar semua lintasan tidak akan memakan waktu lama. Atau, kita dapat menuliskan setiap lintasan sebagai string “arah”, seperti \(xxyyx\text{,}\)\(yyxxx\text{,}\) atau \(xyxxy\text{,}\) yang berturut-turut bersesuaian dengan tiga lintasan yang digambar di atas. Di sini, sebuah \(x\) berarti bergerak satu satuan dalam arah \(x\text{,}\) dan demikian pula untuk \(y\text{.}\) Kita akan memperoleh sepuluh lintasan berikut:
Setiap lintasan kisi dari (0,0) ke (3,2) harus melalui tepat salah satu dari \(A\) dan \(B\text{.}\) Titik \(A\) berjarak 4 langkah dari (0,0), dan dua di antaranya berada dalam arah \(x\text{.}\) Langkah terakhir juga berada dalam arah \(x\text{,}\) sehingga lintasan dari (0,0) ke (3,2) yang melalui \(A\) tepat merupakan enam string di atas yang berakhir dengan \(x\text{.}\) Untuk lintasan yang melalui titik \(B\text{,}\) langkah terakhir berada dalam arah \(y\text{,}\) sehingga lintasan dari (0,0) ke (3,2) yang melalui \(B\) tepat merupakan empat string di atas yang berakhir dengan \(y\text{.}\) Jadi, banyaknya lintasan menuju (3,2) adalah \(6+4\text{.}\)
Pengamatan umumnya adalah sebagai berikut. Untuk menentukan banyaknya lintasan yang berawal di \((0,0)\) dan berakhir di \((m,n)\text{,}\) kita dapat menjumlahkan banyaknya lintasan menuju titik tepat di sebelah kiri titik akhir, yaitu \((m-1,n)\text{,}\) dengan banyaknya lintasan menuju titik tepat di bawah titik akhir, yaitu \((m,n-1)\text{.}\) Cara ini persis sama dengan cara membentuk segitiga Pascal! Jika kita memutar kisi dengan tepat sehingga titik \((0,0)\) berada di puncak segitiga dan kedua sumbu terletak di sepanjang sisi-sisi segitiga, kita melihat bahwa bilangan-bilangan pada segitiga Pascal tepat menyatakan banyaknya lintasan menuju setiap titik kisi.
Agar pengamatan ini berguna untuk benar-benar menentukan banyaknya lintasan dari titik asal ke suatu titik, perhatikan bahwa panjang lintasan menentukan baris segitiga Pascal, sedangkan banyaknya langkah dalam arah \(y\) menentukan seberapa jauh posisi kita ke dalam segitiga, yaitu kolom segitiga Pascal.
“Bit” merupakan singkatan dari “digit biner”, sehingga string bit adalah string yang terdiri atas digit-digit biner. Digit biner tidak lain adalah angka 0 dan 1. Semua objek berikut merupakan string bit:
Banyaknya bit (0 atau 1) dalam string disebut panjang string; string-string di atas berturut-turut memiliki panjang 4, 1, 4, dan 10. Kita juga dapat menanyakan berapa banyak bit yang bernilai 1. Banyaknya angka 1 dalam suatu string bit disebut bobot string; string-string di atas berturut-turut memiliki bobot 2, 0, 4, dan 5.
String \(n\)-bit adalah string bit yang panjangnya \(n\text{.}\) Dengan kata lain, string tersebut memuat \(n\) simbol, dan setiap simbol merupakan sebuah bit, yaitu 0 atau 1.
Sebagai contoh, elemen-elemen himpunan \(\B^3_2\) adalah string bit 011, 101, dan 110. Ketiganya merupakan satu-satunya string yang memuat tiga bit dengan tepat dua di antaranya bernilai 1.
Bagus. Ada sepuluh. Sebenarnya, saya harus mengaku: saya tidak mengetik semuanya dari awal. Saya hanya mengubah daftar 10 lintasan kisi dari (0,0) ke (3,2) yang kita peroleh sebelumnya. Setiap \(x\) diubah menjadi 1 dan setiap \(y\) menjadi 0. Bagaimanapun, setiap lintasan kisi dengan panjang \(n\) yang memerlukan \(k\) langkah dalam arah \(x\) dapat direpresentasikan oleh string yang terdiri atas \(n\) simbol dari dua jenis, dengan \(k\) simbol di antaranya berjenis sama. Menamai kedua simbol itu \(x\) dan \(y\text{,}\) atau menamainya \(1\) dan \(0\text{,}\) tidak mengubah banyaknya string yang diperoleh.
Karena itu, tidak mengherankan jika hubungan yang sama antara segitiga Pascal dan lintasan kisi juga berlaku untuk string bit. Perhatikan 10 string di atas. Baris pertama memuat semua string bit dalam \(\B^5_3\) yang berakhir dengan 0. Sebelum angka 0 terakhir itu terdapat sebuah string dalam \(\B^4_3\text{,}\) sebab string tersebut harus memiliki panjang 4 dan bobot 3 (angka 0 terakhir menambah panjang, tetapi tidak menambah bobot). Baris kedua memuat semua string bit dalam \(\B^5_3\) yang berakhir dengan 1. Sebelum angka 1 terakhir itu terdapat sebuah string dalam \(\B^4_2\text{,}\) sebab string tersebut harus memiliki panjang 4 dan bobot 2 (angka 1 terakhir menambah panjang sekaligus bobot). Jadi, banyaknya string 5-bit berbobot 3 adalah jumlah banyaknya string 4-bit berbobot 3 dan banyaknya string 4-bit berbobot 2. Dalam simbol:
Sekarang kita memiliki dua alasan kuat untuk meyakini bahwa segitiga Pascal memberikan banyaknya string bit dengan bobot tertentu: terdapat korespondensi satu-satu antara lintasan kisi dan string bit, serta relasi rekurensi yang sama berlaku bagi string bit dan bagi pembentukan segitiga Pascal. Jadi, sekarang kita dapat menggunakan segitiga tersebut untuk mencacah string bit.
Subhimpunan dari suatu himpunan \(A\) adalah himpunan yang seluruh elemennya juga merupakan elemen \(A\text{.}\) Bayangkan kita memulai dengan himpunan \(A\) lalu menghapus beberapa elemennya (atau tidak menghapus satu pun, atau menghapus semuanya): himpunan yang dihasilkan merupakan subhimpunan dari \(A\text{.}\) (Informasi lebih lanjut tentang himpunan dapat ditemukan dalam Subbab 0.2 dan Subbab 5.1.)
Misalkan kita memperhatikan himpunan \(A = \{1,2,3,4,5\}\text{.}\) Ada berapa subhimpunan dari \(A\) yang memuat tepat 3 elemen? Mari kita tuliskan semuanya:
Sekali lagi, kita memperoleh sepuluh objek. Bahkan, kita telah menuliskannya dalam urutan yang sama dengan sepuluh string 5-bit berbobot 3 dan sepuluh lintasan kisi dari (0,0) ke (3,2). Namun, apakah hal ini masuk akal? Dalam hal apa subhimpunan dapat dianggap sama dengan string bit?
Bayangkan setiap bit dalam suatu string bit merepresentasikan salah satu elemen dalam suatu himpunan. Himpunan \(A\) memiliki lima elemen, sehingga kita memerlukan lima bit untuk merepresentasikan subhimpunan dari \(A\text{.}\) Jika bit pada posisi \(n\) bernilai 0, berarti kita tidak memasukkan \(n\) ke dalam subhimpunan; sedangkan nilai 1 pada posisi tersebut menunjukkan bahwa \(n\) berada dalam subhimpunan. Tiga angka 1 berarti kita mengatakan “ya” kepada tiga elemen.
Subhimpunan terakhir adalah himpunan kosong, yaitu himpunan yang tidak memuat elemen apa pun (kita juga dapat menuliskannya sebagai \(\{\}\)). Himpunan ini merupakan subhimpunan dari setiap himpunan!
Yang telah kita lakukan di sini adalah memberikan sebuah bijeksi antara himpunan string 5-bit berbobot 3 dan himpunan subhimpunan 3-elemen dari \(A\text{.}\) Bijeksi adalah fungsi \(f: X \to Y\) sedemikian sehingga setiap elemen \(Y\) merupakan citra dari tepat satu elemen \(X\text{.}\) Anda dapat membuktikan bahwa jika terdapat bijeksi antara dua himpunan, maka keduanya memiliki banyak elemen yang sama. Ini merupakan teknik pencacahan umum yang akan kita gunakan pada bagian-bagian berikutnya.
Contoh ini sekali lagi memperlihatkan bahwa segitiga Pascal dapat memberikan jawaban bagi suatu persoalan pencacahan. Banyaknya subhimpunan \(k\)-elemen dari himpunan dengan \(n\) elemen sama dengan banyaknya string \(n\)-bit berbobot \(k\text{,}\) yaitu bilangan pada baris \(n\text{,}\) kolom \(k\) segitiga: \(\binom{n}{k}\text{.}\)
Himpunan tersebut memuat 7 elemen, sehingga banyaknya subhimpunan 4-elemen sama dengan banyaknya string 7-bit berbobot 4, yaitu \(\binom{7}{4} = 35\text{.}\)
Pada tahap ini, saya yakin kita semua mulai lapar, jadi mari memesan piza. Namun, piza apa yang akan kita pesan? Agar tidak berlebihan, kita cukup memilih tiga dari sepuluh taburan yang tersedia. Ada berapa piza berbeda yang dapat kita pesan?
Aha! Inilah alasan kita perlu mencacah subhimpunan! Setiap pilihan piza tidak lain adalah subhimpunan 3-elemen dari himpunan 10 taburan. Sekarang kita tahu cara mencacahnya: terdapat \(\binom{10}{3} = 120\) piza berbeda.
Bagaimana jika kita menginginkan soda Italia saat makan malam? Misalkan kita ingin menambahkan dua sirop dengan rasa berbeda dari 13 rasa yang tersedia. Ada berapa soda berbeda yang mungkin dibuat? Ini tidak lain adalah banyaknya subhimpunan 2-elemen dari himpunan dengan 13 elemen: \(\binom{13}{2} = 78\text{.}\)
Inilah alasan \(\binom{n}{k}\) dibaca “\(n\) pilih \(k\)”. Bilangan ini menyatakan banyaknya cara memilih \(k\) objek dari kumpulan \(n\) objek karena memilih \(k\) elemen tepat merupakan cara membentuk subhimpunan \(k\)-elemen.
Kita dapat memandang pencacahan lintasan kisi sebagai memilih \(k\) dari \(n\) objek: dari \(n\) langkah pada lintasan, kita memilih \(k\) langkah untuk bergerak dalam arah \(x\text{.}\) String bit juga dapat dipandang dengan cara ini: dari \(n\) bit dalam string, kita memilih \(k\) bit untuk bernilai 1.
Sekarang kita dapat menjawab berbagai persoalan pencacahan di dunia nyata, selama persoalan itu pada dasarnya hanya menanyakan banyaknya subhimpunan dari suatu himpunan. Segitiga Pascal memuat semua jawaban tersebut.
Banyaknya subhimpunan \(k\)-elemen dari suatu himpunan dengan \(n\) elemen adalah bilangan pada baris \(n\text{,}\) kolom \(k\) segitiga Pascal, yaitu \(\binom{n}{k}\text{,}\) yang dibaca “\(n\) pilih \(k\text{.}\)” Bilangan ini menyatakan banyaknya cara memilih \(k\) objek dari kumpulan \(n\) objek.
Sebelumnya kita mengatakan bahwa salah satu penggunaan awal segitiga Pascal adalah untuk menyelesaikan persoalan dalam aljabar. Apa kaitan pencacahan subhimpunan (atau string bit atau lintasan kisi) dengan aljabar?
Misalkan Anda mengembangkan ekspresi binomial \((x+1)^6\) (yaitu mengalikan binomial \(x+1\) dengan dirinya sendiri sebanyak enam kali). Pengerjaan secara manual dapat melelahkan, tetapi sistem aljabar komputer seperti SageMath dapat melakukannya dengan mudah.
Untuk melihat mengapa hal ini bukan sekadar kebetulan, mari kita perhatikan pengembangan \((x+y)^3\) dengan sangat cermat. Sebenarnya kita sedang mengalikan
Artinya, kita harus menerapkan sifat distributif pada binomial-binomial tersebut, seperti berikut. (Kita akan menggunakan bentuk huruf berbeda untuk setiap versi \(x\) dan \(y\) agar asal setiap faktor dapat dilacak.)
Penerapan sifat distributif secara berulang menghasilkan jumlah suku-suku yang masing-masing merupakan hasil kali tiga variabel. Kita melihat bahwa setiap suku diperoleh dengan memilih\(x\) atau \(y\) dari setiap binomial. Sebagai contoh, suku \(x\y\X\) diperoleh dengan memilih \(x\) dari binomial pertama, \(\y\) dari binomial kedua, dan \(\X\) dari binomial ketiga.
Misalkan kita ingin menentukan koefisien suku \(x^2y\text{.}\) Kita menggabungkan suku-suku sejenis, yaitu semua suku yang diperoleh dengan memilih \(x\) dua kali (dan \(y\) satu kali). Dari sudut pandang lain, suku \(x^2y\) berasal dari semua string yang memuat dua \(x\) dan satu \(y\text{,}\) seperti string bit atau lintasan kisi. Bagaimanapun cara kita memandangnya, hasilnya adalah terdapat \(\binom{3}{2} = 3\) suku berbentuk \(x^2y\text{.}\)
Semoga jelas bahwa hasil ini dapat diperumum ke pengembangan \((x+y)^n\) untuk setiap bilangan bulat positif \(n\text{.}\) Hasil ini dikenal sebagai teorema binomial.
Baris ke-\(n\) segitiga Pascal memberikan koefisien-koefisien pengembangan \((x+y)^n\text{.}\) Artinya, untuk setiap bilangan bulat positif \(n\text{,}\)
Hati-hati, lintasan dari \((0,0)\) ke \((11,5)\) memiliki panjang \(11+5 = 16\text{,}\) sehingga jawaban persoalan ini adalah \(\binom{16}{5}\text{.}\)
Ada berapa subhimpunan dari \(\{1,2,\ldots, 11\}\) yang memuat tepat 5 elemen?
Banyaknya subhimpunan berukuran 3 dari \(\{1,2,\ldots, 8\}\) sama dengan banyaknya subhimpunan dari \(\{1,2,\ldots, 7\}\) yang berukuran \(2\) atau \(3\text{.}\) Jelaskan mengapa hal ini masuk akal.
Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan setidaknya satu pertanyaan tentang isi bagian ini yang ingin Anda ketahui lebih lanjut.
Ada berapa lintasan kisi dari \((a,b)\) ke \((c,d)\text{?}\) Berikan jawaban Anda sebagai koefisien binomial berbentuk \(\binom{n}{k}\text{,}\) dan nyatakan nilai \(n\) serta \(k\text{.}\)
Ada berapa lintasan kisi dari \((0,0)\) ke \((8,3)\text{?}\) Ada berapa lintasan kisi dari \((0,0)\) ke \((3,8)\text{?}\) Mengapa wajar jika kedua bilangan ini sama? Jelaskan penalaran Anda.
Misalkan Anda sedang mencacah lintasan kisi dari \((0,0)\) ke \((4,3)\text{.}\) Kita mengetahui bahwa banyaknya lintasan tersebut adalah \(\binom{4+3}{4} = \binom{7}{4} = 35\text{.}\) Berikut cara lain untuk mencacahnya: perhatikan kasus-kasus berdasarkan letak langkah pertama dalam arah \(y\text{.}\) Terdapat lima kemungkinan berbeda; hitung banyaknya lintasan untuk setiap kasus.
Ada berapa lintasan dari \((0,0)\) ke \((4,3)\) yang mula-mula bergerak satu langkah dalam arah \(x\text{,}\) lalu satu langkah dalam arah \(y\) (sehingga melalui titik \((1,0)\) lalu \((1,1)\))?
Verifikasi bahwa jumlah banyaknya lintasan dari semua kasus adalah 35. Kemudian, jelaskan letak semua bilangan ini pada segitiga Pascal. Temukan contoh lain dari pola tersebut dan verifikasi bahwa pola itu berlaku.
Dengan menggunakan bentuk pengembangan \((x+y)^5\text{,}\) kalikan \((x+y)^5\cdot (x+y)\) menggunakan sifat distributif. Sederhanakan jawaban Anda, tetapi tunjukkan semua langkahnya.
