Masalah Kombinatorika: Mencari Banyak Rute

      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 banyak 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 banyak rute? Beberapa orang mungkin melambaikan bendera putih. Sekarang, apakah ada cara yang lebih efisien untuk menentukan banyak rute seperti masalah di atas? Jawabannya, ada.

Quote by Imam Ali

Tetap diam sampai kamu diminta untuk bicara adalah lebih baik daripada bicara sampai kamu diminta untuk diam.

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 banyak 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 banyak 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 banyak 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 banyak rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ jika hanya boleh bergerak ke arah kanan atau atas?

Pembahasan

Dengan prinsip yang sama, beri setiap titik sudut dengan bilangan yang menunjukkan banyak cara untuk bergerak ke titik yang bersangkutan.

Jadi, ada $\boxed{18}$ rute berbeda untuk bergerak dari $A$ ke $B$.

[collapse]

Soal Nomor 2

Perhatikan sketsa rute berikut.
Berapa banyak rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ dengan melalui $P$ jika hanya boleh bergerak ke arah kanan atau atas?

Pembahasan

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$.

[collapse]

Soal Nomor 3

Perhatikan sketsa rute berikut.
Berapa banyak rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ tanpa melalui $P$ jika hanya boleh bergerak ke arah kanan atau atas?

Pembahasan

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$.

[collapse]

Soal Nomor 4

Perhatikan sketsa rute berikut.
Berapa banyak rute berbeda yang dapat ditempuh untuk bergerak dari $A$ ke $B$ jika hanya boleh bergerak ke arah kanan atau atas?

Pembahasan

Gunakan prinsip yang sama. Perhatikan gambar di bawah.
Jadi, ada $\boxed{77}$ rute berbeda untuk bergerak dari $A$ ke $B$.

[collapse]

Soal Nomor 5

Perhatikan sketsa rute berikut.
Berapa banyak rute berbeda yang dapat ditempuh untuk bergerak dari $X$ ke $Y$ jika hanya boleh bergerak ke arah kiri atau bawah?

Pembahasan

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$.

[collapse]

Soal Nomor 6

Perhatikan sketsa rute berikut.
Berapa banyak rute berbeda yang dapat ditempuh untuk bergerak dari $X$ ke $Y$ dengan melalui $P$ jika hanya boleh bergerak ke arah kiri atau bawah?

Pembahasan

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$.

[collapse]

Soal Nomor 7

Seseorang mula-mula di titik $A$. Berapa banyak rute berbeda yang dapat ia tempuh untuk menuju ke titik $B$ mengikuti panah yang ada pada setiap jalur?

Pembahasan

Perhatikan baik-baik panah yang ada pada setiap jalur karena akan menentukan bilangan yang ada pada setiap titik sudut. Perhatikan gambar di bawah.
Jadi, banyak rute berbeda yang dapat ia tempuh untuk menuju ke titik $B$ adalah $\boxed{14}$

[collapse]

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 banyak rute berbeda yang dapat mereka tempuh?

Pembahasan

Tandai setiap titik sudutnya, kemudian beri penomoran seperti berikut.
Jadi, ada $\boxed{12}$ rute berbeda yang dapat mereka tempuh untuk menuju daerah $B$.

[collapse]

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 banyak cara semut menuju titik D dari titik A jika harus melalui titik C, tetapi tidak melalui titik B?
A. 210                       D. 282
B. 260                       E. 294
C. 278

Pembahasan

Perhatikan gambar.
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.
(Jawaban A)

[collapse]

Baca Juga: Materi, Soal, dan Pembahasan – Teorema Bintang dan Garis