Beberapa orang “beruntung” terkadang menjumpai masalah yang melibatkan pencarian banyak rute yang dapat ditempuh untuk bergerak dari suatu tempat ke tempat yang lain. Apabila kita berbicara konteks efisiensi, maka orang-orang pasti menginginkan rute paling pendek yang dapat dipilih, tetapi sering kali tidak mudah untuk menemukannya. Terkadang logika mencoba mengambil perannya dengan cara mengira-ngira agar pengambilan keputusan lebih cepat, tetapi sekali lagi perlu ditegaskan bahwa ada unsur kepastian yang diutamakan dalam hal ini.
Dalam matematika, mencari banyaknya rute yang dapat dilalui dari suatu tempat (titik) ke tempat yang lain merupakan salah satu masalah dalam kajian bidang kombinatorika. Kombinatorika (combinatorics) sendiri adalah cabang ilmu matematika yang membahas tentang penyusunan objek-objek dan proses mencacahnya. Sekarang, coba perhatikan sketsa rute di bawah. 
Ada dua titik, namanya $A$ dan $B$. Berapa banyak rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ jika hanya boleh bergerak ke arah kanan atau atas? Orang-orang biasanya menggunakan alternatif pertama: manual, yaitu dengan cara mencoba rutenya satu per satu seperti berikut.
Akan ada 6 rute terpendek yang dapat ditempuh berdasarkan percobaan manual tersebut, dan itu memang jawaban yang benar untuk soal itu. Lantas, apakah kita masih nekad menggunakan cara manual untuk menghadapi masalah yang lebih kompleks terkait penentuan banyaknya rute? Beberapa orang mungkin melambaikan bendera putih. Sekarang, apakah ada cara yang lebih efisien untuk menentukan banyaknya rute seperti masalah di atas? Jawabannya, ada.
Quote by Imam Ali
Sekarang, perhatikan kembali sketsa rute di atas. Tandai tiap titik sudut dari rute tersebut seperti berikut.
Angka $1$ pada empat titik sudut menunjukkan bahwa ada satu cara untuk menuju titik tersebut dari titik $A$. Karena hanya boleh bergerak ke kanan atau atas, maka untuk menuju titik sudut tengah, akan ada 2 cara yang mungkin. Caranya adalah dengan menjumlahkan banyaknya cara yang dapat ditempuh dari titik di sebelah kiri dan bawahnya.
Prinsipnya sama untuk titik sudut yang lain.
Langkah terakhir adalah di titik $B$. Di titik sebelah kiri ada $3$ cara, di bawahnya juga ada $3$ cara. Jumlahkan, $3 + 3 = 6$. Jadi, kita simpulkan bahwa ada $6$ cara untuk menuju titik $B$ dari titik $A$.
Kita coba lagi untuk sketsa rute lain yang lebih rumit.
Pertanyaannya sama, berapa banyaknya rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ jika hanya boleh bergerak ke arah kanan atau atas?
Dengan prinsip yang sama, beri setiap titik sudut dengan bilangan yang menunjukkan banyaknya cara untuk bergerak ke titik yang bersangkutan.
Perhatikan bahwa angka $3$ yang diberi panah pada gambar di atas didapat dari angka di bawah titik itu. Ini dikarenakan hanya ada satu jalan untuk menuju titik tersebut, yaitu dari bawah sehingga kita tetap tuliskan $3$. Dari gambar, terdapat $11$ rute berbeda untuk menuju titik $B$ dari titik $A$.
Silakan coba kerjakan soal-soal latihan berikut terkait submateri kombinatorika ini. Tidak perlu khawatir, pembahasan setiap soal juga telah disediakan.
Soal Nomor 1
Perhatikan sketsa rute berikut.
Berapa banyaknya rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ jika hanya boleh bergerak ke arah kanan atau atas?
Dengan prinsip yang sama, beri setiap titik sudut dengan bilangan yang menunjukkan banyaknya cara untuk bergerak ke titik yang bersangkutan.
Jadi, ada $\boxed{18}$ rute berbeda untuk bergerak dari $A$ ke $B$.
Soal Nomor 2
Perhatikan sketsa rute berikut.
Berapa banyaknya rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ dengan melalui $P$ jika hanya boleh bergerak ke arah kanan atau atas?
Pertama, kita bergerak dari titik $A$ ke $P$ terlebih dahulu.
Dari gambar di atas, ada $3$ rute berbeda untuk bergerak dari $A$ ke $P$. Berikutnya, dari $P$ ke $B$.
Jadi, ada $\boxed{12}$ rute berbeda untuk bergerak dari $A$ ke $B$ dengan melalui $P$.
Soal Nomor 3
Perhatikan sketsa rute berikut.
Berapa banyaknya rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ tanpa melalui $P$ jika hanya boleh bergerak ke arah kanan atau atas?
Berbeda dengan soal sebelumnya, sekarang kita diberi syarat untuk tidak melalui titik $P$. Perhatikan gambar di bawah.
Jadi, ada $\boxed{6}$ rute berbeda untuk bergerak dari $A$ ke $B$ tanpa melalui $P$.
Soal Nomor 4
Perhatikan sketsa rute berikut.
Berapa banyaknya rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ jika hanya boleh bergerak ke arah kanan atau atas?
Gunakan prinsip yang sama. Perhatikan gambar di bawah.
Jadi, ada $\boxed{77}$ rute berbeda untuk bergerak dari $A$ ke $B$.
Soal Nomor 5
Perhatikan sketsa rute berikut.
Berapa banyaknya rute berbeda yang dapat ditempuh untuk bergerak dari $X$ ke $Y$ jika hanya boleh bergerak ke arah kiri atau bawah?
Gunakan prinsip yang sama seperti pergerakan ke arah kanan atau atas. Titik $X$ adalah titik mula-mula. Perhatikan gambar di bawah.
Jadi, ada $\boxed{8}$ rute berbeda untuk bergerak dari $X$ ke $Y$.
Soal Nomor 6
Perhatikan sketsa rute berikut.
Berapa banyaknya rute berbeda yang dapat ditempuh untuk bergerak dari $X$ ke $Y$ dengan melalui $P$ jika hanya boleh bergerak ke arah kiri atau bawah?
Pertama, kita bergerak dari titik $A$ ke $P$ terlebih dahulu.
Dari gambar di atas, ada $4$ rute berbeda untuk bergerak dari $X$ ke $P$. Berikutnya, dari $P$ ke $Y$.
Jadi, ada $\boxed{4}$ rute berbeda untuk bergerak dari $X$ ke $Y$ dengan melalui $P$.
Soal Nomor 7
Seseorang mula-mula di titik $A$. Berapa banyaknya rute berbeda yang dapat ia tempuh untuk menuju ke titik $B$ mengikuti panah yang ada pada setiap jalur?
Perhatikan baik-baik panah yang ada pada setiap jalur karena akan menentukan bilangan yang ada pada setiap titik sudut. Perhatikan gambar di bawah.
Jadi, banyaknya rute berbeda yang dapat ia tempuh untuk menuju ke titik $B$ adalah $\boxed{14}$
Soal Nomor 8
Anggota OSIS suatu sekolah dari daerah $A$ mengadakan kunjungan sosial ke panti asuhan di daerah $B$. Jalur perjalanan yang akan mereka lalui disketsakan melalui gambar di bawah.
Ada berapa banyaknya rute berbeda yang dapat mereka tempuh?
Tandai setiap titik sudutnya, kemudian beri penomoran seperti berikut.
Jadi, ada $\boxed{12}$ rute berbeda yang dapat mereka tempuh untuk menuju daerah $B$.
Baca Juga: Materi, Soal, dan Pembahasan – Prinsip Inklusi-Eksklusi
Soal Nomor 9
Perhatikan gambar berikut.
Seekor semut mulai berjalan dari titik A menuju titik D. Semut hanya boleh berjalan di sepanjang garis dengan arah ke kanan atau ke atas. Berapa banyaknya cara semut menuju titik D dari titik A jika harus melalui titik C, tetapi tidak melalui titik B?
Perhatikan gambar berikut.
Pertama, kita menuju titik A ke C tanpa melalui titik B. Akan ada 26 cara berbeda yang dapat ditempuh. Selanjutnya, dari titik C menuju ke titik D ada sebanyak 260 cara. Jadi, secara keseluruhan ada 260 cara yang dapat ditempuh semut sesuai dengan persyaratan yang diberikan tersebut.
Soal Nomor 10
Berapa banyaknya rute berbeda yang dapat ditempuh dari titik $A$ ke titik $H$ jika setiap titik hanya boleh dilalui sekali?
Perhatikan gambar berikut.
Urutan pengisian untuk setiap bilangan yang merepresentasikan banyaknya rute berbeda dari titik $A$ ke tujuh titik lainnya dengan catatan bahwa setiap titik hanya boleh dilalui sekali adalah $A, B, C,$ $E, F, D, G,$ dan $H.$ Berdasarkan gambar, dapat disimpulkan bahwa banyaknya rute berbeda yang dapat ditempuh dari titik $A$ ke titik $H$ jika setiap titik hanya boleh dilalui sekali adalah $\boxed{10}$ rute.
Baca Juga: Materi, Soal, dan Pembahasan – Teorema Bintang dan Garis