Faktorial, Filling Slot, Permutasi, dan Kombinasi Lengkap

Kombinatorika adalah bagian matematika yang mempelajari cara menghitung banyak kemungkinan secara sistematis. Ketika kita menghitung banyak kata sandi yang dapat dibuat, banyak susunan siswa pada kursi, banyak cara memilih anggota tim, banyak pola warna, atau banyak rute yang mungkin dilalui, kita sedang melakukan pencacahan kombinatorik.

Bagi siswa yang baru mempelajari matematika dari nol, kombinatorika sering tampak seperti kumpulan rumus. Ada faktorial, aturan penjumlahan, aturan perkalian, permutasi, kombinasi, dan berbagai bentuk khususnya. Padahal semua konsep tersebut sebenarnya lahir dari satu pertanyaan yang sangat sederhana:

Ada berapa banyak kemungkinan yang dapat terjadi?

Kita akan membangun jawabannya secara bertahap. Kita mulai dari mengenali objek diskret, memahami faktorial, kemudian mempelajari aturan penjumlahan dan aturan perkalian melalui metode filling slot. Setelah fondasinya kuat, barulah kita memahami permutasi dan kombinasi beserta berbagai kasus khususnya.

Tujuan akhirnya bukan sekadar mampu memasukkan angka ke rumus. Kamu diharapkan mampu melihat struktur masalah, memilih strategi yang paling efisien, menjelaskan alasan di balik perhitungan, serta mengenali kesalahan yang sering terjadi.

Tujuan Pembelajaran

Setelah mempelajari materi ini, kamu diharapkan mampu:

1. menjelaskan pengertian kombinatorika dan objek diskret;
2. membedakan besaran diskret dan kontinu;
3. memahami definisi faktorial dan alasan \(\displaystyle 0!=1\);
4. menyederhanakan operasi faktorial secara efisien;
5. menyelesaikan persamaan sederhana yang melibatkan faktorial;
6. memahami aturan penjumlahan;
7. memahami aturan perkalian;
8. menggunakan metode filling slot untuk melakukan pencacahan;
9. membedakan kasus dengan dan tanpa pengulangan;
10. memahami permutasi sebagai penyusunan yang memperhatikan urutan;
11. menyelesaikan permutasi biasa, permutasi bersyarat, permutasi dengan unsur sama, dan permutasi siklis;
12. memahami kombinasi sebagai pemilihan yang tidak memperhatikan urutan;
13. menyelesaikan kombinasi biasa dan kombinasi bersyarat;
14. memahami kombinasi dengan pengulangan;
15. menggunakan kombinasi untuk menghitung rute terpendek;
16. memilih antara aturan penjumlahan, aturan perkalian, filling slot, permutasi, dan kombinasi berdasarkan struktur masalah.

Mari Berpikir

Bayangkan tersedia empat angka, yaitu \(\displaystyle 1\), \(\displaystyle 2\), \(\displaystyle 3\), dan \(\displaystyle 4\). Kita hendak membuat kata sandi empat angka tanpa pengulangan.

Beberapa kemungkinan adalah \(\displaystyle 1234\), \(\displaystyle 1243\), \(\displaystyle 1324\), dan seterusnya.

Jika hanya ada empat angka, kita mungkin masih dapat menuliskan seluruh susunannya satu per satu.

Sekarang bayangkan tersedia sepuluh angka, dua puluh enam huruf, dan beberapa simbol. Kata sandi harus terdiri atas delapan karakter.

Apakah kita masih ingin menuliskan semua kemungkinan satu per satu?

Tentu tidak efisien.

Kita membutuhkan metode pencacahan yang dapat memberikan jumlah kemungkinan tanpa harus membuat daftar lengkap.

Hal serupa terjadi dalam persoalan pemilihan.

Misalkan dari sepuluh siswa akan dipilih tiga siswa sebagai delegasi. Apakah memilih A, B, dan C berbeda dari memilih C, B, dan A?

Jika ketiganya hanya menjadi anggota delegasi tanpa jabatan berbeda, kelompok tersebut tetap sama.

Namun jika tiga siswa itu akan menjadi ketua, sekretaris, dan bendahara, posisi A, B, dan C menjadi penting.

Perbedaan kecil inilah yang nantinya membedakan kombinasi dan permutasi.

Pengertian Kombinatorika

Kombinatorika adalah cabang matematika yang mempelajari pencacahan, pemilihan, penyusunan, dan pengelompokan objek-objek yang bersifat diskret.

Kata diskret sangat penting.

Objek diskret dapat dihitung satu per satu dan banyaknya mengambil nilai yang terpisah.

Contohnya:

• jumlah siswa dalam kelas;
• banyak halaman sebuah buku;
• jumlah kendaraan;
• banyak kartu;
• banyak kursi;
• jumlah kata sandi;
• banyak pilihan menu;
• banyak rute.

Sebaliknya, besaran seperti tinggi badan, massa, suhu, dan waktu pada dasarnya bersifat kontinu karena nilainya dapat berada di antara dua bilangan.

Misalnya jumlah siswa dalam kelas dapat \(\displaystyle 30\) atau \(\displaystyle 31\). Kita tidak mengatakan bahwa sebuah kelas mempunyai \(\displaystyle 30{,}7\) siswa.

Namun tinggi badan dapat saja \(\displaystyle 165{,}4\) cm.

Jadi, kombinatorika terutama berurusan dengan sesuatu yang dapat dicacah.

Apa yang Dimaksud Pencacahan?

Pencacahan berarti menentukan banyak anggota suatu kumpulan kemungkinan.

Misalnya tersedia tiga pilihan minuman:

• teh;
• kopi;
• susu.

Jika kita memilih tepat satu minuman, terdapat tiga kemungkinan.

Untuk kasus sederhana kita dapat langsung menghitungnya.

Namun ketika pilihan dan syaratnya semakin banyak, kita membutuhkan prinsip umum agar tidak kehilangan kemungkinan atau justru menghitung kemungkinan yang sama berulang kali.

Mengapa Kombinatorika Penting?

Kombinatorika menjadi dasar dalam banyak bidang.

Dalam peluang, kita sering menggunakan perbandingan

\(\displaystyle \frac{\text{banyak hasil yang diinginkan}}{\text{banyak seluruh hasil yang mungkin}}\)

Sebelum dapat menghitung peluang, kita harus mengetahui banyaknya hasil yang mungkin.

Dalam teknologi, kombinatorika digunakan ketika menganalisis kata sandi, kode, struktur data, jaringan, dan algoritma.

Dalam kehidupan sehari-hari, kombinatorika muncul dalam penyusunan jadwal, pemilihan tim, pembentukan pasangan, rute perjalanan, pengaturan tempat duduk, dan berbagai proses pengambilan keputusan.

Soal 1

Tentukan mana yang merupakan besaran diskret dari daftar berikut: jumlah siswa sebuah kelas, suhu ruangan, banyak mata pelajaran, berat badan, jumlah kendaraan di tempat parkir, dan tinggi badan.

Faktorial: Notasi Penting dalam Kombinatorika

Sebelum membahas prinsip pencacahan lebih jauh, kita membutuhkan sebuah notasi untuk menyingkat perkalian panjang.

Misalnya,

\(\displaystyle 1\cdot2\cdot3\cdot4\cdot5\cdot6\)

atau

\(\displaystyle 10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1\)

Perkalian bilangan bulat positif berurutan seperti ini akan sangat sering muncul.

Agar penulisannya lebih ringkas, digunakan notasi faktorial.

Definisi Faktorial

Untuk bilangan bulat positif \(\displaystyle n\), faktorial dari \(\displaystyle n\) ditulis \(\displaystyle n!\) dan dibaca n faktorial.

Definisinya adalah

\(\displaystyle n!=n(n-1)(n-2)\cdots3\cdot2\cdot1\)

Dengan demikian,

\(\displaystyle 5!=5\cdot4\cdot3\cdot2\cdot1\)

\(\displaystyle 5!=120\)

Begitu pula,

\(\displaystyle 6!=6\cdot5\cdot4\cdot3\cdot2\cdot1\)

\(\displaystyle 6!=720\)

Nilai Faktorial Dasar

Beberapa nilai faktorial yang baik untuk dikenali adalah:

\(\displaystyle 1!=1\)

\(\displaystyle 2!=2\)

\(\displaystyle 3!=6\)

\(\displaystyle 4!=24\)

\(\displaystyle 5!=120\)

\(\displaystyle 6!=720\)

\(\displaystyle 7!=5040\)

\(\displaystyle 8!=40320\)

Faktorial bertumbuh sangat cepat.

Perhatikan perbandingan

\(\displaystyle 5!=120\)

dan

\(\displaystyle 10!=3628800\)

Meskipun nilai \(\displaystyle n\) hanya bertambah dari \(\displaystyle 5\) menjadi \(\displaystyle 10\), nilai faktorial bertambah sangat besar.

Hubungan Rekursif Faktorial

Perhatikan

\(\displaystyle 6!=6\cdot5\cdot4\cdot3\cdot2\cdot1\)

Bagian

\(\displaystyle 5\cdot4\cdot3\cdot2\cdot1\)

adalah \(\displaystyle 5!\).

Karena itu,

\(\displaystyle 6!=6\cdot5!\)

Secara umum,

\(\displaystyle n!=n(n-1)!\)

Hubungan ini disebut hubungan rekursif faktorial.

Kita juga dapat membuka lebih jauh.

\(\displaystyle n!=n(n-1)(n-2)!\)

atau

\(\displaystyle n!=n(n-1)(n-2)(n-3)!\)

Kita tidak perlu selalu membuka faktorial sampai \(\displaystyle 1\).

Hal ini sangat membantu ketika menyederhanakan pecahan faktorial.

Mengapa \(\displaystyle 0!=1\)?

Nilai \(\displaystyle 0!\) sering membingungkan siswa yang baru belajar.

Mengapa bukan \(\displaystyle 0\)?

Gunakan hubungan

\(\displaystyle n!=n(n-1)!\)

Untuk \(\displaystyle n=1\), kita memperoleh

\(\displaystyle 1!=1\cdot0!\)

Karena

\(\displaystyle 1!=1\)

maka

\(\displaystyle 1=1\cdot0!\)

sehingga

\(\displaystyle 0!=1\)

Ada pula penjelasan kombinatorik.

Faktorial \(\displaystyle n!\) nantinya dapat dimaknai sebagai banyak cara menyusun \(\displaystyle n\) objek berbeda.

Jika tidak ada objek yang harus disusun, ada tepat satu susunan, yaitu susunan kosong.

Karena itulah konsisten jika

\(\displaystyle 0!=1\)

Nilai ini juga membuat rumus permutasi dan kombinasi bekerja dengan benar ketika \(\displaystyle r=0\) atau \(\displaystyle r=n\).

Domain Faktorial

Dalam kombinatorika dasar, faktorial didefinisikan untuk bilangan bulat tidak negatif:

\(\displaystyle 0,1,2,3,\ldots\)

Faktorial bilangan bulat negatif seperti

\(\displaystyle (-1)!\)

atau

\(\displaystyle (-5)!\)

tidak didefinisikan dalam pengertian faktorial elementer.

Karena itu, setiap kali kita memperoleh persamaan yang mengandung faktorial, kita harus memperhatikan syarat agar argumen faktorial merupakan bilangan bulat tidak negatif.

Faktorial dalam Notasi Hasil Kali

Faktorial juga dapat ditulis menggunakan notasi hasil kali.

\(\displaystyle n!=\prod_{k=1}^{n}k\)

Notasi ini berarti kita mengalikan semua nilai \(\displaystyle k\) dari \(\displaystyle 1\) sampai \(\displaystyle n\).

Untuk siswa yang baru belajar, bentuk

\(\displaystyle n!=n(n-1)\cdots2\cdot1\)

biasanya lebih mudah digunakan.

Operasi Sederhana Faktorial

Soal 2

Hitung nilai \(\displaystyle 5!\), \(\displaystyle 3!+2!\), dan \(\displaystyle (4!-2!)\cdot5!\).

Menyederhanakan Pembagian Faktorial

Perhatikan

\(\displaystyle \frac{8!}{5!}\)

Kesalahan yang sering dilakukan adalah menghitung \(\displaystyle 8!\) dan \(\displaystyle 5!\) terlebih dahulu.

Padahal terdapat cara jauh lebih singkat.

Buka \(\displaystyle 8!\) sampai muncul \(\displaystyle 5!\).

\(\displaystyle 8!=8\cdot7\cdot6\cdot5!\)

Maka,

\(\displaystyle \frac{8!}{5!}=\frac{8\cdot7\cdot6\cdot5!}{5!}\)

Faktor \(\displaystyle 5!\) dapat disederhanakan.

\(\displaystyle \frac{8!}{5!}=8\cdot7\cdot6\)

\(\displaystyle \frac{8!}{5!}=336\)

Secara umum, untuk \(\displaystyle n>m\),

\(\displaystyle \frac{n!}{m!}=n(n-1)(n-2)\cdots(m+1)\)

Soal 3

Sederhanakan \(\displaystyle \frac{10!}{8!\cdot2!}\).

Memfaktorkan Bentuk Faktorial

Faktorial dapat diperlakukan seperti faktor dalam aljabar.

Perhatikan

\(\displaystyle 9!+8!\)

Karena

\(\displaystyle 9!=9\cdot8!\)

maka

\(\displaystyle 9!+8!=9\cdot8!+8!\)

Keluarkan faktor \(\displaystyle 8!\).

\(\displaystyle 9!+8!=(9+1)8!\)

\(\displaystyle 9!+8!=10\cdot8!\)

Cara berpikir yang sama berlaku pada pengurangan.

\(\displaystyle 11!-10!=11\cdot10!-10!\)

\(\displaystyle 11!-10!=(11-1)10!\)

\(\displaystyle 11!-10!=10\cdot10!\)

Teknik memfaktorkan seperti ini sering membuat soal faktorial yang terlihat rumit menjadi jauh lebih sederhana.

Persamaan Faktorial

Soal 4

Tentukan bilangan bulat positif \(\displaystyle n\) yang memenuhi \(\displaystyle \frac{n!}{(n-3)!}=210\).

Pendalaman Faktorial: Keterbagian

Karena faktorial merupakan perkalian bilangan-bilangan berurutan, faktorial mempunyai banyak faktor.

Sebagai contoh,

\(\displaystyle 8!=8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1\)

Jelas bahwa \(\displaystyle 8!\) habis dibagi \(\displaystyle 1,2,3,\ldots,8\).

Lebih dari itu, kita dapat menganalisis banyaknya faktor prima tertentu yang muncul.

Misalnya untuk mengetahui berapa banyak faktor \(\displaystyle 5\) dalam \(\displaystyle 100!\), kita tidak perlu menuliskan seluruh faktor dari \(\displaystyle 1\) sampai \(\displaystyle 100\).

Kita cukup menghitung kelipatan \(\displaystyle 5\), lalu memperhitungkan kelipatan \(\displaystyle 25\), \(\displaystyle 125\), dan seterusnya.

Konsep ini sangat berguna dalam menentukan banyak angka nol di bagian akhir suatu faktorial.

Banyak Angka Nol di Belakang \(\displaystyle n!\)

Satu angka nol di akhir suatu bilangan muncul karena terdapat faktor

\(\displaystyle 10=2\cdot5\)

Di dalam faktorial, faktor \(\displaystyle 2\) biasanya jauh lebih banyak daripada faktor \(\displaystyle 5\).

Karena itu, banyak pasangan \(\displaystyle 2\cdot5\) ditentukan oleh banyaknya faktor \(\displaystyle 5\).

Banyak angka nol di akhir \(\displaystyle n!\) dapat dihitung dari

\(\displaystyle \left\lfloor\frac{n}{5}\right\rfloor+\left\lfloor\frac{n}{25}\right\rfloor+\left\lfloor\frac{n}{125}\right\rfloor+\cdots\)

Penjumlahan dihentikan ketika pangkat \(\displaystyle 5\) sudah lebih besar daripada \(\displaystyle n\).

Soal 5

Tentukan banyak angka nol di bagian akhir dari \(\displaystyle 100!\).

Pendalaman Faktorial: Prinsip Teleskopik

Faktorial juga dapat menghasilkan pola teleskopik.

Perhatikan hubungan

\(\displaystyle k\cdot k!=(k+1)!-k!\)

Mengapa hubungan tersebut benar?

Karena

\(\displaystyle (k+1)!=(k+1)k!\)

Maka,

\(\displaystyle (k+1)!-k!=(k+1)k!-k!\)

\(\displaystyle (k+1)!-k!=k\cdot k!\)

Hubungan ini sangat berguna pada penjumlahan panjang.

Misalnya,

\(\displaystyle 1\cdot1!+2\cdot2!+3\cdot3!+\cdots+n\cdot n!\)

Setiap suku dapat diubah menjadi selisih dua faktorial.

\(\displaystyle 1\cdot1!=2!-1!\)

\(\displaystyle 2\cdot2!=3!-2!\)

\(\displaystyle 3\cdot3!=4!-3!\)

Jika semuanya dijumlahkan, suku-suku tengah saling menghilangkan.

Hasil akhirnya adalah

\(\displaystyle (n+1)!-1\)

Ini disebut pola teleskopik karena bagian tengah seolah-olah “menutup” dan menghilang.

Soal 6

Sederhanakan \(\displaystyle 1\cdot1!+2\cdot2!+3\cdot3!+4\cdot4!\).

Prinsip Dasar Pencacahan

Setelah memahami faktorial, kita masuk ke inti kombinatorika.

Banyak masalah pencacahan dapat dibangun dari dua prinsip:

1. aturan penjumlahan;
2. aturan perkalian.

Keduanya tampak sederhana, tetapi hampir seluruh teknik pencacahan dasar dapat ditelusuri kembali kepada dua gagasan tersebut.

Aturan Penjumlahan

Misalkan suatu tindakan dapat dilakukan melalui alternatif pertama atau alternatif kedua.

Alternatif pertama mempunyai \(\displaystyle p\) kemungkinan.

Alternatif kedua mempunyai \(\displaystyle q\) kemungkinan.

Jika kedua kelompok kemungkinan tidak tumpang tindih dan kita hanya melakukan salah satunya, banyak kemungkinan seluruhnya adalah

\(\displaystyle p+q\)

Ini disebut aturan penjumlahan.

Mengapa Dijumlahkan?

Misalnya ada \(\displaystyle 5\) pilihan jus dan \(\displaystyle 4\) pilihan susu. Kita ingin membeli tepat satu minuman.

Kita membeli jus atau susu.

Banyak pilihannya adalah

\(\displaystyle 5+4=9\)

Kita tidak mengalikan karena tidak membeli satu jus dan satu susu sekaligus.

Makna Kata “Atau”

Kata atau sering menjadi petunjuk aturan penjumlahan, tetapi jangan menghafalnya secara mekanis.

Kita tetap harus memahami situasinya.

Pertanyaan pentingnya adalah:

Apakah kita memilih satu alternatif dari beberapa kelompok?

Jika ya, aturan penjumlahan biasanya digunakan.

Soal 7

Di suatu sekolah terdapat \(\displaystyle 180\) siswa kelas X dan \(\displaystyle 160\) siswa kelas XI. Akan dipilih tepat satu siswa dari kelas X atau kelas XI untuk menjadi wakil sekolah. Berapa banyak pilihan yang tersedia?

Aturan Penjumlahan pada Kelompok yang Tumpang Tindih

Aturan penjumlahan sederhana harus digunakan dengan hati-hati jika dua kelompok mempunyai anggota yang sama.

Misalkan terdapat:

• \(\displaystyle 20\) siswa menyukai matematika;
• \(\displaystyle 15\) siswa menyukai fisika;
• \(\displaystyle 6\) siswa menyukai keduanya.

Jika kita menghitung

\(\displaystyle 20+15\)

enam siswa yang menyukai keduanya akan terhitung dua kali.

Karena itu,

\(\displaystyle 20+15-6=29\)

Prinsip ini dapat ditulis sebagai

\(\displaystyle n(A\cup B)=n(A)+n(B)-n(A\cap B)\)

Gagasan tersebut menjadi dasar prinsip inklusi dan eksklusi.

Aturan Perkalian

Sekarang misalkan suatu hasil harus melalui beberapa tahap.

Tahap pertama mempunyai \(\displaystyle p\) pilihan.

Untuk setiap pilihan tahap pertama, tahap kedua mempunyai \(\displaystyle q\) pilihan.

Karena kedua tahap harus dilakukan, banyak hasil lengkap adalah

\(\displaystyle p\cdot q\)

Secara umum, jika terdapat beberapa tahap dengan banyak pilihan

\(\displaystyle n_1,n_2,n_3,\ldots,n_k\)

maka banyak kemungkinan adalah

\(\displaystyle n_1n_2n_3\cdots n_k\)

Mengapa Dikalikan?

Misalkan seseorang mempunyai:

• \(\displaystyle 3\) kemeja;
• \(\displaystyle 2\) celana.

Untuk setiap kemeja terdapat dua pilihan celana.

Kemeja pertama menghasilkan dua outfit.

Kemeja kedua menghasilkan dua outfit.

Kemeja ketiga menghasilkan dua outfit.

Totalnya

\(\displaystyle 3\cdot2=6\)

Soal 8

Seseorang memiliki \(\displaystyle 4\) kemeja, \(\displaystyle 5\) dasi, dan \(\displaystyle 3\) celana berbeda. Satu outfit terdiri atas satu kemeja, satu dasi, dan satu celana. Berapa banyak outfit yang dapat dibuat?

Aturan Perkalian dan Rute

Misalkan terdapat \(\displaystyle 4\) jalan dari kota A ke kota B dan \(\displaystyle 3\) jalan dari kota B ke kota C.

Untuk pergi dari A ke C melalui B, seseorang harus:

1. memilih jalan A ke B;
2. memilih jalan B ke C.

Jumlah rute adalah

\(\displaystyle 4\cdot3=12\)

Jika kemudian harus kembali dari C ke A melalui B, tahapnya semakin banyak dan setiap syarat harus diperhatikan.

Filling Slot

Salah satu cara paling intuitif menggunakan aturan perkalian adalah filling slot.

Filling slot berarti kita membayangkan setiap posisi yang harus diisi sebagai sebuah slot.

Untuk setiap slot kita bertanya:

Berapa banyak pilihan yang tersedia untuk mengisi posisi ini?

Setelah mengetahui banyak pilihan pada setiap slot, kita mengalikannya.

Contoh Dasar Filling Slot

Misalkan sebuah kode terdiri atas tiga karakter dan setiap karakter dipilih dari lima simbol berbeda. Pengulangan diperbolehkan.

Slot pertama mempunyai \(\displaystyle 5\) pilihan.

Slot kedua juga mempunyai \(\displaystyle 5\) pilihan.

Slot ketiga juga mempunyai \(\displaystyle 5\) pilihan.

Jumlah kode adalah

\(\displaystyle 5\cdot5\cdot5\)

\(\displaystyle 5^3=125\)

Filling Slot Tanpa Pengulangan

Sekarang pengulangan tidak diperbolehkan.

Slot pertama mempunyai \(\displaystyle 5\) pilihan.

Setelah satu simbol digunakan, slot kedua tinggal \(\displaystyle 4\) pilihan.

Slot ketiga tinggal \(\displaystyle 3\) pilihan.

Jumlah kode adalah

\(\displaystyle 5\cdot4\cdot3=60\)

Inilah perbedaan mendasar antara kasus boleh berulang dan tidak boleh berulang.

Filling Slot dengan Pengulangan

Jika ada \(\displaystyle n\) pilihan untuk setiap slot, terdapat \(\displaystyle r\) slot, dan objek boleh digunakan kembali, banyak susunan adalah

\(\displaystyle n^r\)

Misalnya sebuah bendera mempunyai empat bidang dan setiap bidang dapat diberi salah satu dari lima warna. Warna yang sama boleh digunakan kembali.

Setiap bidang mempunyai \(\displaystyle 5\) pilihan.

Maka,

\(\displaystyle 5^4=625\)

Terdapat \(\displaystyle 625\) pola warna.

Filling Slot dengan Syarat

Filling slot menjadi sangat kuat ketika terdapat syarat khusus.

Misalnya hendak membuat bilangan tiga angka yang harus ganjil.

Posisi satuan memiliki syarat paling kuat karena hanya boleh diisi digit ganjil.

Tidak ada aturan yang mengatakan kita harus menganalisis slot dari kiri ke kanan.

Kita boleh memulai dari slot yang paling terbatas.

Ini sering membuat soal jauh lebih mudah.

Soal 9

Dari digit \(\displaystyle 1,2,3,4,5,6\) akan dibuat bilangan tiga angka tanpa pengulangan. Berapa banyak bilangan genap yang dapat dibuat?

Filling Slot pada Bilangan yang Memuat Nol

Digit \(\displaystyle 0\) membutuhkan perhatian khusus.

Misalnya kita menyusun bilangan tiga angka dari digit \(\displaystyle 0,1,2,3,4\).

Digit ratusan tidak boleh \(\displaystyle 0\) karena bilangan seperti \(\displaystyle 042\) sebenarnya hanya bilangan dua angka.

Karena itu, slot pertama sering mempunyai jumlah pilihan yang berbeda dengan slot lainnya.

Soal 10

Dari digit \(\displaystyle 0,1,2,3,4,5\) akan dibuat bilangan tiga angka tanpa pengulangan. Berapa banyak bilangan tiga angka yang dapat dibuat?

Hubungan Filling Slot dengan Faktorial

Sekarang perhatikan penyusunan enam objek berbeda pada enam posisi.

Slot pertama mempunyai \(\displaystyle 6\) pilihan.

Slot kedua mempunyai \(\displaystyle 5\) pilihan.

Slot ketiga mempunyai \(\displaystyle 4\) pilihan.

Kemudian \(\displaystyle 3\), \(\displaystyle 2\), dan \(\displaystyle 1\) pilihan.

Jumlah susunan adalah

\(\displaystyle 6\cdot5\cdot4\cdot3\cdot2\cdot1\)

Ini sama dengan

\(\displaystyle 6!\)

Jadi, faktorial sebenarnya muncul secara alami dari aturan perkalian.

Pemahaman ini menjadi jembatan menuju permutasi.

Permutasi

Permutasi adalah penyusunan objek dengan memperhatikan urutan.

Perhatikan tiga digit \(\displaystyle 1,2,3\).

Beberapa susunannya adalah

\(\displaystyle 123\)

\(\displaystyle 132\)

\(\displaystyle 213\)

Ketiganya dianggap berbeda karena posisi setiap digit berbeda.

Pertanyaan kunci untuk mengenali permutasi adalah:

Jika dua objek ditukar, apakah hasilnya dianggap berbeda?

Jika jawabannya ya, urutan penting dan kita mengarah ke permutasi.

Permutasi Seluruh Objek

Jika terdapat \(\displaystyle n\) objek berbeda dan seluruhnya disusun, posisi pertama mempunyai \(\displaystyle n\) pilihan.

Posisi kedua mempunyai \(\displaystyle n-1\) pilihan.

Posisi ketiga mempunyai \(\displaystyle n-2\) pilihan.

Proses berlanjut hingga tersisa satu pilihan.

Karena itu,

\(\displaystyle P(n)=n!\)

Sebagai contoh, enam siswa disusun dalam satu baris.

Jumlah susunannya adalah

\(\displaystyle 6!=720\)

Permutasi \(\displaystyle r\) Objek dari \(\displaystyle n\) Objek

Sekarang misalkan tersedia \(\displaystyle n\) objek, tetapi hanya \(\displaystyle r\) yang akan dipilih dan disusun.

Posisi pertama mempunyai \(\displaystyle n\) pilihan.

Posisi kedua mempunyai \(\displaystyle n-1\) pilihan.

Proses berlanjut sampai terdapat \(\displaystyle r\) posisi.

Jumlahnya adalah

\(\displaystyle {}^nP_r=n(n-1)(n-2)\cdots(n-r+1)\)

Dengan menggunakan faktorial,

\(\displaystyle {}^nP_r=\frac{n!}{(n-r)!}\)

dengan syarat

\(\displaystyle 0\le r\le n\)

Mengapa Rumus Permutasi Bekerja?

Perhatikan

\(\displaystyle n!=n(n-1)\cdots(n-r+1)(n-r)!\)

Jika kedua ruas dibagi dengan \(\displaystyle (n-r)!\), diperoleh

\(\displaystyle \frac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)\)

Itulah perkalian filling slot untuk \(\displaystyle r\) posisi.

Jadi, rumus permutasi bukan rumus yang muncul secara tiba-tiba. Rumus tersebut merupakan bentuk singkat filling slot.

Soal 11

Dari tujuh siswa akan dipilih seorang ketua, seorang sekretaris, dan seorang bendahara. Berapa banyak susunan kepengurusan yang mungkin?

Permutasi dan Filling Slot

Soal permutasi tidak selalu harus dikerjakan menggunakan rumus.

Misalnya tersedia tujuh orang untuk mengisi tiga jabatan.

Kita dapat langsung menulis:

ketua mempunyai \(\displaystyle 7\) pilihan;

sekretaris mempunyai \(\displaystyle 6\) pilihan;

bendahara mempunyai \(\displaystyle 5\) pilihan.

Maka,

\(\displaystyle 7\cdot6\cdot5=210\)

Hasilnya sama dengan permutasi.

Filling slot sering lebih mudah ketika soal mempunyai syarat khusus.

Permutasi Bersyarat

Permutasi menjadi lebih menarik ketika muncul syarat seperti:

• harus berada di ujung;
• tidak boleh berada di ujung;
• harus berdampingan;
• tidak boleh berdampingan;
• sebuah posisi sudah ditentukan;
• beberapa orang harus ditempatkan bersama.

Dalam situasi seperti ini, jangan terburu-buru menggunakan rumus permutasi.

Analisis syarat terlebih dahulu.

Kasus Seseorang Harus Berada di Posisi Tertentu

Soal 12

Enam siswa akan duduk pada enam kursi berjajar. Jika A harus duduk di kursi paling kiri, berapa banyak susunan yang mungkin?

Kasus Seseorang Harus Berada di Salah Satu Ujung

Jika terdapat enam orang dan A harus berada di salah satu ujung, A mempunyai dua pilihan posisi:

• ujung kiri;
• ujung kanan.

Setelah posisi A ditentukan, lima orang lainnya dapat disusun dalam

\(\displaystyle 5!\)

cara.

Totalnya

\(\displaystyle 2\cdot5!\)

\(\displaystyle 2\cdot120=240\)

Kasus Dua Orang Mengisi Kedua Ujung

Misalnya A dan B harus menempati dua kursi ujung.

A dan B dapat bertukar posisi dalam

\(\displaystyle 2!\)

cara.

Empat orang lainnya disusun di tengah dalam

\(\displaystyle 4!\)

cara.

Jumlahnya

\(\displaystyle 2!\cdot4!\)

\(\displaystyle 2\cdot24=48\)

Prinsip Komplementer pada Permutasi

Kadang jauh lebih mudah menghitung kejadian yang tidak diinginkan lalu mengurangkannya dari semua kemungkinan.

Misalnya enam orang disusun berjajar dan A tidak boleh berada di ujung.

Total semua susunan adalah

\(\displaystyle 6!=720\)

Jumlah susunan ketika A berada di salah satu ujung adalah

\(\displaystyle 2\cdot5!=240\)

Maka jumlah susunan ketika A tidak berada di ujung adalah

\(\displaystyle 720-240=480\)

Gagasan ini disebut prinsip komplementer.

Permutasi dengan Objek Harus Berdampingan

Jika dua objek harus berdampingan, kita dapat menganggap keduanya sebagai satu blok.

Misalkan enam orang A, B, C, D, E, F disusun berjajar dan A serta B harus berdampingan.

Anggap AB sebagai satu blok.

Kita sekarang mempunyai lima objek:

• blok AB;
• C;
• D;
• E;
• F.

Kelima objek dapat disusun dalam

\(\displaystyle 5!\)

cara.

Namun di dalam blok, A dan B dapat tersusun sebagai AB atau BA.

Jadi terdapat

\(\displaystyle 2!\)

susunan di dalam blok.

Jumlah seluruh susunan adalah

\(\displaystyle 5!\cdot2!\)

\(\displaystyle 120\cdot2=240\)

Soal 13

Tujuh orang duduk berjajar. Dua orang tertentu harus selalu berdampingan. Berapa banyak susunan yang mungkin?

Permutasi dengan Objek Tidak Boleh Berdampingan

Untuk kasus “tidak boleh berdampingan”, prinsip komplementer biasanya lebih efisien.

Jumlah yang dicari adalah

\(\displaystyle \text{semua susunan}-\text{susunan ketika berdampingan}\)

Untuk tujuh orang,

\(\displaystyle 7!=5040\)

Jumlah susunan dua orang tertentu berdampingan adalah

\(\displaystyle 6!\cdot2!=1440\)

Maka,

\(\displaystyle 5040-1440=3600\)

Permutasi dengan Unsur Sama

Sejauh ini kita menganggap semua objek berbeda.

Sekarang perhatikan huruf dalam kata MAMA.

Jumlah huruf adalah empat.

Jika semua dianggap berbeda, kita akan memperoleh

\(\displaystyle 4!=24\)

susunan.

Namun terdapat dua huruf M yang identik dan dua huruf A yang identik.

Menukar M pertama dengan M kedua tidak menghasilkan susunan baru.

Begitu pula menukar A pertama dan A kedua.

Karena itu, jumlah susunan yang benar-benar berbeda adalah

\(\displaystyle \frac{4!}{2!\cdot2!}\)

\(\displaystyle \frac{24}{4}=6\)

Rumus Permutasi dengan Unsur Sama

Jika terdapat \(\displaystyle n\) objek dan beberapa objek identik dengan banyak kemunculan

\(\displaystyle n_1,n_2,\ldots,n_k\)

maka jumlah susunan berbeda adalah

\(\displaystyle P=\frac{n!}{n_1!n_2!\cdots n_k!}\)

dengan

\(\displaystyle n_1+n_2+\cdots+n_k=n\)

Mengapa harus dibagi?

Karena pertukaran antarobjek identik sebenarnya tidak menciptakan susunan baru, tetapi ikut terhitung dalam \(\displaystyle n!\).

Soal 14

Berapa banyak susunan berbeda yang dapat dibuat dari huruf-huruf pada kata MATEMATIKA?

Permutasi dalam Pembagian Jabatan Sejenis

Permutasi unsur sama tidak hanya muncul pada huruf.

Misalkan tujuh siswa akan menempati jabatan:

• satu ketua;
• dua wakil;
• empat koordinator.

Jika dua wakil dianggap memiliki tingkat jabatan yang sama dan empat koordinator juga dianggap setara, strukturnya analog dengan menyusun simbol

\(\displaystyle ABBCCCC\)

Jumlah susunan pembagian perannya adalah

\(\displaystyle \frac{7!}{2!\cdot4!}\)

\(\displaystyle \frac{5040}{48}=105\)

Konsep ini menunjukkan bahwa permutasi unsur sama dapat digunakan pada posisi atau kategori yang identik, bukan hanya huruf yang sama.

Permutasi dengan Pengulangan Pilihan

Jangan mencampur dua konsep berikut:

Pertama, objek identik sudah tersedia, seperti huruf A muncul tiga kali. Ini menggunakan pembagian faktorial.

Kedua, objek boleh dipilih kembali untuk setiap posisi. Ini menghasilkan bentuk seperti

\(\displaystyle n^r\)

Contohnya kode empat digit yang setiap posisinya boleh menggunakan digit \(\displaystyle 0\) sampai \(\displaystyle 9\).

Setiap posisi mempunyai \(\displaystyle 10\) pilihan.

Jumlah kode adalah

\(\displaystyle 10^4=10000\)

Tidak ada pembagian faktorial pada kasus ini.

Permutasi Siklis

Susunan berjajar mempunyai posisi awal dan akhir.

Susunan melingkar berbeda.

Jika lima orang duduk mengelilingi meja bundar, seluruh orang dapat bergeser satu kursi dan hubungan relatif antarorang tetap sama.

Karena itu, susunan yang hanya berbeda akibat rotasi dianggap sama.

Permutasi seperti ini disebut permutasi siklis.

Rumus Permutasi Siklis

Jika terdapat \(\displaystyle n\) objek berbeda yang disusun melingkar, banyak susunannya adalah

\(\displaystyle (n-1)!\)

Mengapa Bukan \(\displaystyle n!\)?

Jika disusun berjajar, ada

\(\displaystyle n!\)

susunan.

Namun dalam lingkaran, satu pola yang sama dapat diputar ke \(\displaystyle n\) posisi.

Artinya setiap pola terhitung \(\displaystyle n\) kali dalam \(\displaystyle n!\).

Karena itu,

\(\displaystyle \frac{n!}{n}=(n-1)!\)

Cara yang lebih intuitif adalah menetapkan satu orang sebagai titik acuan.

Setelah satu orang dibuat tetap, kita hanya perlu menyusun \(\displaystyle n-1\) orang lainnya.

Soal 15

Delapan orang duduk mengelilingi sebuah meja bundar. Berapa banyak susunan duduk yang berbeda jika susunan yang hanya berbeda karena rotasi dianggap sama?

Rotasi dan Pencerminan

Perlu dibedakan antara susunan di meja bundar dan pola gelang.

Pada meja bundar, susunan yang hanya berbeda karena rotasi dianggap sama.

Namun bayangan cermin biasanya masih dianggap berbeda karena tetangga kiri dan kanan berubah.

Pada gelang atau kalung, kadang benda dapat dibalik sehingga bayangan cermin juga dianggap sama.

Jika semua objek berbeda dan pembalikan dianggap sama, jumlah pola dapat menjadi

\(\displaystyle \frac{(n-1)!}{2}\)

untuk kasus umum \(\displaystyle n>2\).

Baca pernyataan soal dengan cermat karena definisi “sama” menentukan model pencacahannya.

Permutasi Siklis dengan Unsur Sama

Misalkan sejumlah huruf disusun melingkar dan beberapa huruf identik.

Pada kasus sekolah yang tidak mempunyai simetri rotasi tambahan, perhitungannya dapat berbentuk

\(\displaystyle \frac{(n-1)!}{n_1!n_2!\cdots n_k!}\)

Namun perlu berhati-hati.

Jika pola mempunyai simetri rotasi khusus, pencacahan dapat menjadi lebih rumit.

Karena itu, pada soal tingkat dasar, periksa apakah pola pengulangannya menghasilkan konfigurasi yang tetap sama setelah diputar sebagian.

Dari Permutasi Menuju Kombinasi

Sekarang perhatikan situasi berbeda.

Dari lima siswa A, B, C, D, dan E akan dipilih tiga siswa sebagai tim.

Misalnya yang terpilih adalah A, B, dan C.

Urutan A-B-C tidak berbeda dari B-A-C atau C-B-A karena anggota timnya tetap sama.

Jika kita menggunakan permutasi, kelompok A, B, C akan terhitung

\(\displaystyle 3!=6\)

kali.

Karena urutan tersebut seharusnya dianggap sama, kita harus membagi hasil permutasi dengan \(\displaystyle 3!\).

Dari sinilah rumus kombinasi muncul.

Kombinasi

Kombinasi adalah pemilihan sejumlah objek tanpa memperhatikan urutan.

Jika yang dipilih A, B, dan C, urutan penulisannya tidak menghasilkan kelompok baru.

Rumus memilih \(\displaystyle r\) objek dari \(\displaystyle n\) objek adalah

\(\displaystyle {}^nC_r=\frac{n!}{(n-r)!r!}\)

dengan syarat

\(\displaystyle 0\le r\le n\)

Mengapa Rumus Kombinasi Dibagi \(\displaystyle r!\)?

Permutasi menghitung semua urutan dari \(\displaystyle r\) objek terpilih.

Namun dalam kombinasi, seluruh urutan tersebut dianggap sama.

Satu kelompok yang berisi \(\displaystyle r\) objek mempunyai

\(\displaystyle r!\)

urutan.

Karena itu,

\(\displaystyle {}^nC_r=\frac{{}^nP_r}{r!}\)

Substitusikan rumus permutasi.

\(\displaystyle {}^nC_r=\frac{\frac{n!}{(n-r)!}}{r!}\)

Sehingga,

\(\displaystyle {}^nC_r=\frac{n!}{(n-r)!r!}\)

Hubungan Permutasi dan Kombinasi

Dari hubungan sebelumnya,

\(\displaystyle {}^nP_r={}^nC_r\cdot r!\)

Maknanya sangat jelas.

Untuk membuat susunan terurut dari \(\displaystyle r\) objek:

1. pilih dahulu \(\displaystyle r\) objek;
2. susun objek yang telah dipilih.

Tahap pertama memberikan

\(\displaystyle {}^nC_r\)

kemungkinan.

Tahap kedua memberikan

\(\displaystyle r!\)

kemungkinan.

Maka hasilnya

\(\displaystyle {}^nC_r\cdot r!\)

Sifat Simetri Kombinasi

Kombinasi mempunyai sifat

\(\displaystyle {}^nC_r={}^nC_{n-r}\)

Mengapa?

Memilih \(\displaystyle r\) orang yang masuk tim sama dengan menentukan \(\displaystyle n-r\) orang yang tidak masuk tim.

Misalnya memilih tiga siswa dari sepuluh siswa sama dengan menentukan tujuh siswa yang tidak dipilih.

Karena itu,

\(\displaystyle {}^{10}C_3={} ^{10}C_7\)

Keduanya sama-sama bernilai

\(\displaystyle 120\)

Sifat ini sering digunakan agar perhitungan lebih pendek.

Nilai Khusus Kombinasi

\(\displaystyle {}^nC_0=1\)

Ada tepat satu cara memilih tidak satu pun objek.

\(\displaystyle {}^nC_n=1\)

Ada tepat satu cara memilih seluruh objek.

\(\displaystyle {}^nC_1=n\)

Ada \(\displaystyle n\) cara memilih tepat satu objek.

Soal 16

Dari delapan siswa akan dipilih lima siswa menjadi anggota sebuah tim tanpa jabatan berbeda. Berapa banyak tim yang dapat dibentuk?

Jangan Mengandalkan Kata “Memilih”

Kata “memilih” tidak otomatis berarti kombinasi.

Perhatikan dua soal.

Kasus pertama: dari delapan siswa dipilih dua siswa sebagai perwakilan kelas.

Tidak ada jabatan berbeda.

A dan B sama dengan B dan A.

Gunakan kombinasi.

Kasus kedua: dari delapan siswa dipilih seorang ketua dan seorang wakil.

A sebagai ketua dan B sebagai wakil berbeda dari B sebagai ketua dan A sebagai wakil.

Gunakan permutasi.

Jadi, pertanyaan yang harus diajukan bukan:

“Apakah soal menggunakan kata memilih?”

Melainkan:

Apakah posisi atau urutan hasil pemilihan penting?

Kombinasi Bersyarat: Seseorang Harus Terpilih

Soal 17

Dari sepuluh siswa akan dipilih empat siswa menjadi anggota tim. Seorang siswa tertentu harus terpilih. Berapa banyak tim yang dapat dibentuk?

Kombinasi Bersyarat: Seseorang Tidak Boleh Terpilih

Jika dari sepuluh siswa akan dipilih empat tetapi A tidak boleh terpilih, kita cukup mengeluarkan A dari kumpulan calon.

Tersisa sembilan siswa.

Jumlah tim adalah

\(\displaystyle {}^9C_4\)

Dua Orang Tidak Boleh Terpilih Bersama

Kasus ini sangat cocok menggunakan prinsip komplementer.

Hitung:

1. semua tim;
2. tim yang memuat kedua orang tersebut;
3. kurangkan.

Soal 18

Dari sepuluh siswa akan dipilih empat siswa. A dan B tidak boleh terpilih bersama-sama. Berapa banyak tim yang dapat dibentuk?

Kombinasi dengan Syarat Tepat

Misalnya terdapat enam laki-laki dan lima perempuan. Akan dipilih empat siswa dengan tepat dua perempuan.

Langkahnya:

pilih dua perempuan dari lima;

pilih dua laki-laki dari enam.

Banyak pilihan perempuan adalah

\(\displaystyle {}^5C_2\)

Banyak pilihan laki-laki adalah

\(\displaystyle {}^6C_2\)

Karena kedua tahap harus dilakukan, gunakan aturan perkalian.

\(\displaystyle {}^5C_2\cdot{}^6C_2\)

\(\displaystyle 10\cdot15=150\)

Kombinasi dengan Syarat Minimal

Kata minimal dua perempuan berarti:

• tepat dua perempuan;
• tepat tiga perempuan;
• tepat empat perempuan;
• dan seterusnya sesuai ukuran kelompok.

Karena setiap kasus merupakan alternatif terpisah, hasilnya dijumlahkan.

Kadang lebih mudah menggunakan komplemen.

Misalnya minimal dua perempuan berarti kita dapat menghitung:

\(\displaystyle \text{semua kelompok}-\text{nol perempuan}-\text{satu perempuan}\)

Soal 19

Terdapat enam siswa laki-laki dan lima siswa perempuan. Akan dipilih lima siswa. Berapa banyak kelompok yang dapat dibentuk jika minimal dua siswa perempuan harus terpilih?

Kombinasi dengan Pengulangan

Sekarang kita membahas situasi ketika:

• urutan tidak diperhatikan;
• suatu jenis objek boleh dipilih lebih dari sekali.

Misalnya tersedia empat rasa donat dan kita akan membeli tujuh donat.

Kita boleh membeli beberapa donat dengan rasa yang sama.

Masalah ini disebut kombinasi dengan pengulangan.

Jika terdapat \(\displaystyle n\) jenis objek dan kita memilih \(\displaystyle r\) objek dengan pengulangan diperbolehkan, banyak kemungkinan adalah

\(\displaystyle {}^{n+r-1}C_r\)

atau setara dengan

\(\displaystyle {}^{n+r-1}C_{n-1}\)

Mengapa Kombinasi dengan Pengulangan Menggunakan \(\displaystyle n+r-1\)?

Kita dapat memahami rumus melalui metode stars and bars.

Misalnya kita membeli tujuh donat dari empat rasa.

Tujuh donat dilambangkan dengan tujuh bintang.

Untuk memisahkan empat rasa, diperlukan tiga pembatas.

Total simbol yang harus disusun adalah

\(\displaystyle 7+3=10\)

Dari sepuluh posisi, kita dapat memilih tiga posisi untuk pembatas.

Jumlah kemungkinan adalah

\(\displaystyle {}^{10}C_3\)

Karena

\(\displaystyle {}^{10}C_3=120\)

terdapat \(\displaystyle 120\) kemungkinan komposisi pembelian.

Hubungan dengan Persamaan Bilangan Cacah

Kombinasi dengan pengulangan juga digunakan untuk menghitung banyak solusi bilangan cacah dari

\(\displaystyle x_1+x_2+\cdots+x_n=r\)

dengan setiap

\(\displaystyle x_i\ge0\)

Banyak solusinya adalah

\(\displaystyle {}^{n+r-1}C_r\)

Soal 20

Tentukan banyak solusi bilangan cacah dari \(\displaystyle x_1+x_2+x_3+x_4=10\).

Kombinasi dan Pencacahan Rute

Kombinasi mempunyai aplikasi yang sangat menarik pada pencacahan rute.

Misalkan seseorang bergerak dari titik A menuju titik B pada kisi.

Untuk mencapai B melalui rute terpendek, ia harus:

• bergerak lima langkah ke kanan;
• bergerak tiga langkah ke atas.

Total langkah adalah

\(\displaystyle 5+3=8\)

Setiap rute terpendek dapat dipandang sebagai susunan delapan langkah yang terdiri atas lima langkah kanan dan tiga langkah atas.

Karena lima langkah kanan identik dan tiga langkah atas identik, jumlah rute adalah

\(\displaystyle \frac{8!}{5!\cdot3!}\)

Ini sama dengan

\(\displaystyle {}^8C_3\)

atau

\(\displaystyle {}^8C_5\)

Hasilnya adalah

\(\displaystyle 56\)

Mengapa Rute Terpendek Berhubungan dengan Kombinasi?

Kita dapat memilih posisi mana dari delapan langkah yang akan diisi oleh tiga gerakan ke atas.

Begitu tiga posisi tersebut ditentukan, lima posisi lainnya otomatis merupakan gerakan ke kanan.

Karena hanya memilih posisi dan urutan pemilihannya tidak penting, muncul kombinasi.

Soal 21

Untuk berpindah dari A ke B melalui rute terpendek, seseorang harus bergerak enam kali ke kanan dan empat kali ke atas. Berapa banyak rute terpendek yang mungkin?

Rute yang Harus Melalui Titik Tertentu

Jika rute harus melalui titik C, perjalanan dapat dibagi menjadi:

1. A menuju C;
2. C menuju B.

Hitung banyak rute pada masing-masing tahap, kemudian kalikan.

Mengapa dikalikan?

Karena setiap rute A-C dapat dipasangkan dengan setiap rute C-B.

Soal 22

Dari A ke C diperlukan dua langkah ke kanan dan satu langkah ke atas. Dari C ke B diperlukan tiga langkah ke kanan dan dua langkah ke atas. Berapa banyak rute terpendek A ke B yang melalui C?

Rute yang Tidak Boleh Melalui Titik Tertentu

Jika sebuah rute tidak boleh melalui titik C, kita dapat menggunakan prinsip komplementer.

Hitung:

1. semua rute A-B;
2. semua rute A-B yang melalui C;
3. kurangkan.

Secara konseptual,

\(\displaystyle \text{rute yang tidak melalui C}=\text{semua rute}-\text{rute melalui C}\)

Strategi ini sering jauh lebih mudah daripada mencoba membuat rute yang menghindari C satu per satu.

Metode Penjumlahan pada Persimpangan

Tidak semua jaringan jalan membentuk persegi panjang sempurna.

Jika ada jalan terputus atau bentuk jaringan tidak beraturan, kita dapat menggunakan cara pencacahan pada setiap titik persimpangan.

Mulai dari titik awal dengan nilai \(\displaystyle 1\).

Untuk setiap titik berikutnya, jumlahkan banyak cara untuk sampai ke titik tersebut dari titik-titik sebelumnya.

Jika suatu titik dapat dicapai dari dua titik dengan masing-masing \(\displaystyle a\) dan \(\displaystyle b\) cara, maka banyak cara menuju titik tersebut adalah

\(\displaystyle a+b\)

Metode ini sebenarnya menggunakan aturan penjumlahan berulang.

Hubungan Kombinasi dengan Segitiga Pascal

Kombinasi mempunyai identitas penting:

\(\displaystyle {}^nC_r={} ^{n-1}C_{r-1}+{}^{n-1}C_r\)

Mengapa?

Bayangkan kita memilih \(\displaystyle r\) orang dari \(\displaystyle n\) orang dan memperhatikan seorang tertentu, misalnya A.

Ada dua kasus.

Kasus pertama: A terpilih.

Karena A sudah terpilih, kita tinggal memilih \(\displaystyle r-1\) orang dari \(\displaystyle n-1\) orang lainnya.

Jumlah caranya

\(\displaystyle {}^{n-1}C_{r-1}\)

Kasus kedua: A tidak terpilih.

Kita harus memilih seluruh \(\displaystyle r\) orang dari \(\displaystyle n-1\) orang lainnya.

Jumlah caranya

\(\displaystyle {}^{n-1}C_r\)

Kedua kasus saling terpisah, sehingga gunakan aturan penjumlahan.

\(\displaystyle {}^nC_r={} ^{n-1}C_{r-1}+{}^{n-1}C_r\)

Inilah pola yang membentuk Segitiga Pascal.

Cara Memilih Strategi Kombinatorika

Banyak siswa merasa kesulitan bukan karena tidak bisa menghitung, tetapi karena tidak tahu rumus mana yang harus digunakan.

Gunakan urutan berpikir berikut.

Langkah 1: Tentukan Apa yang Sedang Dihitung

Tanyakan:

Apakah kita sedang menghitung:

• pilihan;
• susunan;
• kode;
• bilangan;
• kelompok;
• jabatan;
• rute;
• distribusi objek?

Jangan menghitung sebelum jelas apa yang dianggap sebagai satu hasil.

Langkah 2: Tentukan Apakah Terdapat Beberapa Alternatif

Jika kita melakukan pilihan A atau B, periksa aturan penjumlahan.

Contoh:

memilih satu siswa dari kelas X atau XI.

Langkah 3: Tentukan Apakah Terdapat Beberapa Tahap

Jika harus melakukan tahap A dan kemudian tahap B, gunakan aturan perkalian.

Contoh:

memilih kemeja dan celana.

Langkah 4: Periksa Apakah Objek Boleh Berulang

Jika objek dapat digunakan kembali, jumlah pilihan dapat tetap sama.

Jika tidak boleh berulang, jumlah pilihan biasanya berkurang.

Langkah 5: Periksa Apakah Urutan Penting

Lakukan tes sederhana.

Tukar dua objek.

Jika hasil berubah, urutan penting.

Jika hasil tetap sama, urutan tidak penting.

Langkah 6: Periksa Syarat Khusus

Perhatikan kata seperti:

• harus;
• tidak boleh;
• tepat;
• minimal;
• maksimal;
• berdampingan;
• di ujung;
• melalui;
• tidak melalui.

Syarat tersebut sering menentukan strategi utama.

Langkah 7: Pertimbangkan Komplemen

Jika menghitung langsung sangat rumit, tanyakan:

“Apakah lebih mudah menghitung semua kemungkinan kemudian mengurangi kemungkinan yang tidak diinginkan?”

Peta Keputusan Cepat

Jika ada beberapa pilihan alternatif, gunakan aturan penjumlahan.

Jika ada beberapa tahap, gunakan aturan perkalian.

Jika terdapat posisi-posisi yang harus diisi, gunakan filling slot.

Jika urutan penting dan tidak ada pengulangan, gunakan permutasi.

Jika seluruh objek disusun, gunakan faktorial.

Jika terdapat objek identik, gunakan permutasi dengan unsur sama.

Jika objek disusun melingkar, periksa permutasi siklis.

Jika urutan tidak penting, gunakan kombinasi.

Jika urutan tidak penting dan pengulangan diperbolehkan, periksa kombinasi dengan pengulangan.

Jika terdapat syarat “tidak”, “minimal”, atau “tidak boleh bersama”, pertimbangkan prinsip komplementer.

Kesalahan Umum pada Faktorial

Menganggap \(\displaystyle (a+b)!=a!+b!\)

Pernyataan tersebut salah.

Contoh:

\(\displaystyle (2+3)!=5!=120\)

Sedangkan

\(\displaystyle 2!+3!=2+6\)

\(\displaystyle 2!+3!=8\)

Jelas

\(\displaystyle 120\ne8\)

Faktorial tidak dapat didistribusikan terhadap penjumlahan.

Menganggap \(\displaystyle \frac{8!}{5!}=\frac{8}{5}\)

Ini juga salah.

Yang benar,

\(\displaystyle \frac{8!}{5!}=8\cdot7\cdot6\)

\(\displaystyle \frac{8!}{5!}=336\)

Menganggap \(\displaystyle 0!=0\)

Yang benar adalah

\(\displaystyle 0!=1\)

Kesalahan Umum pada Filling Slot

Kesalahan pertama adalah lupa mengurangi pilihan ketika objek tidak boleh berulang.

Jika terdapat enam objek dan satu telah digunakan, posisi berikutnya tidak lagi memiliki enam pilihan.

Kesalahan kedua adalah tidak memperhatikan digit nol pada posisi pertama suatu bilangan.

Kesalahan ketiga adalah mengisi slot dari kiri ke kanan meskipun slot lain mempunyai syarat lebih ketat.

Strategi terbaik sering kali adalah memulai dari slot yang paling terbatas.

Kesalahan Umum pada Permutasi

Kesalahan pertama adalah menggunakan permutasi pada masalah ketika urutan sebenarnya tidak penting.

Kesalahan kedua adalah menggunakan \(\displaystyle n!\) walaupun hanya sebagian objek yang disusun.

Kesalahan ketiga adalah melupakan susunan internal blok pada kasus berdampingan.

Kesalahan keempat adalah menggunakan \(\displaystyle n!\) pada susunan melingkar.

Untuk objek berbeda pada lingkaran, gunakan

\(\displaystyle (n-1)!\)

Kesalahan kelima adalah tidak membagi akibat objek identik.

Kesalahan Umum pada Kombinasi

Kesalahan pertama adalah menganggap kata “memilih” selalu berarti kombinasi.

Jika objek terpilih mempunyai jabatan berbeda, urutan penting.

Kesalahan kedua adalah lupa memperbarui banyak objek setelah seseorang diwajibkan terpilih.

Jika tim beranggota empat dan A sudah wajib masuk, kita tinggal memilih tiga anggota tambahan.

Kesalahan ketiga adalah salah memahami kata minimal.

Minimal dua berarti dua atau lebih, bukan tepat dua.

Membandingkan Empat Pola Penting

Urutan Penting dan Pengulangan Diperbolehkan

Jika terdapat \(\displaystyle n\) pilihan untuk setiap posisi dan terdapat \(\displaystyle r\) posisi,

\(\displaystyle n^r\)

Urutan Penting dan Tanpa Pengulangan

\(\displaystyle {}^nP_r=\frac{n!}{(n-r)!}\)

Urutan Tidak Penting dan Tanpa Pengulangan

\(\displaystyle {}^nC_r=\frac{n!}{(n-r)!r!}\)

Urutan Tidak Penting dan Pengulangan Diperbolehkan

\(\displaystyle {}^{n+r-1}C_r\)

Memahami perbedaan empat pola tersebut akan menyelesaikan sebagian besar kebingungan awal dalam kombinatorika.

Contoh HOTS: Memilih Strategi

Soal 23

Dari digit \(\displaystyle 0,1,2,3,4,5,6\) akan dibuat bilangan empat angka tanpa pengulangan. Berapa banyak bilangan genap yang lebih besar dari \(\displaystyle 3000\)?

Soal ini memperlihatkan bahwa kita tidak selalu dapat menggunakan satu rumus tunggal.

Kita menggunakan:

• pembagian kasus;
• filling slot;
• aturan perkalian;
• aturan penjumlahan.

Inilah esensi pemecahan masalah kombinatorika.

Contoh HOTS: Kombinasi dan Komplemen

Soal 24

Dari delapan siswa laki-laki dan enam siswa perempuan akan dipilih lima siswa. Berapa banyak kelompok yang dapat dibentuk jika kelompok harus memuat sedikitnya satu siswa laki-laki dan sedikitnya satu siswa perempuan?

Cek Pemahaman

Soal 25

Hitung nilai \(\displaystyle \frac{12!}{10!}\).

Soal 26

Sebuah PIN terdiri atas empat digit. Setiap posisi dapat diisi digit \(\displaystyle 0\) sampai \(\displaystyle 9\) dan pengulangan diperbolehkan. Berapa banyak PIN yang dapat dibuat?

Soal 27

Dari sembilan siswa akan dipilih seorang ketua, seorang wakil, dan seorang sekretaris. Berapa banyak susunan kepengurusan yang mungkin?

Soal 28

Dari sembilan siswa akan dipilih tiga siswa menjadi anggota delegasi tanpa jabatan. Berapa banyak delegasi yang dapat dibentuk?

Soal 29

Enam orang duduk mengelilingi meja bundar. Dua orang tertentu harus berdampingan. Berapa banyak susunan yang mungkin?

Refleksi

1. Mengapa rumus permutasi sebenarnya dapat dibangun langsung dari metode filling slot?
2. Mengapa kombinasi diperoleh dengan membagi permutasi dengan \(\displaystyle r!\)?
3. Mengapa syarat “tidak boleh” sering lebih mudah diselesaikan menggunakan prinsip komplementer?
4. Jika suatu soal pemilihan tim diubah menjadi pemilihan ketua, sekretaris, dan bendahara, bagian mana dari model pencacahannya yang berubah?

Kesimpulan

Kombinatorika adalah ilmu tentang menghitung kemungkinan. Meskipun banyak rumus muncul dalam materi ini, seluruh gagasannya dapat dibangun dari prinsip pencacahan yang sederhana.

Kita memulai dari faktorial.

\(\displaystyle n!=n(n-1)(n-2)\cdots2\cdot1\)

Hubungan

\(\displaystyle n!=n(n-1)!\)

membantu menyederhanakan pecahan dan ekspresi faktorial tanpa menghitung bilangan yang sangat besar.

Nilai

\(\displaystyle 0!=1\)

bukan aturan yang dibuat sembarangan. Nilai tersebut mengikuti hubungan rekursif dan memiliki makna kombinatorik sebagai satu susunan kosong.

Selanjutnya, aturan penjumlahan digunakan ketika kita memilih satu dari beberapa alternatif.

Jika alternatif mempunyai \(\displaystyle p\) dan \(\displaystyle q\) kemungkinan, jumlahnya menjadi

\(\displaystyle p+q\)

Aturan perkalian digunakan ketika suatu hasil harus melalui beberapa tahap.

Jika tahap pertama mempunyai \(\displaystyle p\) pilihan dan tahap kedua mempunyai \(\displaystyle q\) pilihan, jumlah hasil lengkap adalah

\(\displaystyle p\cdot q\)

Metode filling slot membuat aturan perkalian menjadi lebih visual. Kita menentukan jumlah pilihan untuk setiap posisi, kemudian mengalikannya.

Jika pengulangan diperbolehkan, jumlah pilihan dapat tetap.

Jika tidak boleh berulang, jumlah pilihan biasanya berkurang setelah setiap slot terisi.

Dari filling slot kita memperoleh konsep permutasi.

Jika urutan penting,

\(\displaystyle {}^nP_r=\frac{n!}{(n-r)!}\)

Jika semua objek disusun,

\(\displaystyle P(n)=n!\)

Jika terdapat objek identik,

\(\displaystyle P=\frac{n!}{n_1!n_2!\cdots n_k!}\)

Jika objek berbeda disusun melingkar,

\(\displaystyle P=(n-1)!\)

Sebaliknya, jika urutan tidak diperhatikan, kita menggunakan kombinasi.

\(\displaystyle {}^nC_r=\frac{n!}{(n-r)!r!}\)

Permutasi dan kombinasi mempunyai hubungan

\(\displaystyle {}^nP_r={}^nC_r\cdot r!\)

Artinya, permutasi dapat dipandang sebagai proses memilih objek terlebih dahulu, kemudian menyusunnya.

Kombinasi juga dapat diperluas menjadi kombinasi dengan pengulangan dan digunakan untuk menghitung distribusi maupun rute terpendek.

Hal terpenting dalam belajar kombinatorika adalah tidak langsung bertanya:

“Rumus apa yang harus digunakan?”

Tanyakan terlebih dahulu:

• apa yang sedang dihitung?
• apakah ada pilihan alternatif?
• apakah ada beberapa tahap?
• apakah pengulangan diperbolehkan?
• apakah urutan penting?
• apakah terdapat syarat khusus?
• apakah komplemen lebih mudah dihitung?

Ketika struktur masalah sudah dipahami, rumus biasanya menjadi konsekuensi alami dari cara berpikir tersebut.

FAQ Kombinatorika

Apa itu kombinatorika?

Kombinatorika adalah cabang matematika yang mempelajari pencacahan, penyusunan, pemilihan, dan pengelompokan objek diskret.

Tujuan utamanya adalah menghitung banyak kemungkinan secara efisien tanpa harus menuliskan semua hasil satu per satu.

Apa perbedaan aturan penjumlahan dan aturan perkalian?

Aturan penjumlahan digunakan ketika kita memilih satu dari beberapa alternatif.

Aturan perkalian digunakan ketika suatu hasil dibentuk melalui beberapa tahap yang semuanya harus dilakukan.

Misalnya memilih satu minuman berupa teh atau kopi menggunakan penjumlahan.

Memilih satu baju dan satu celana menggunakan perkalian.

Apa itu filling slot?

Filling slot adalah metode pencacahan dengan membayangkan posisi-posisi yang harus diisi.

Kita menentukan jumlah pilihan untuk setiap posisi, kemudian mengalikan jumlah pilihan tersebut.

Metode ini sangat berguna untuk kata sandi, PIN, bilangan, kode, susunan orang, dan berbagai soal bersyarat.

Apa perbedaan permutasi dan kombinasi?

Permutasi memperhatikan urutan.

Kombinasi tidak memperhatikan urutan.

Jika A-B berbeda dengan B-A, gunakan permutasi.

Jika kelompok A dan B tetap sama dengan B dan A, gunakan kombinasi.

Mengapa \(\displaystyle 0!=1\)?

Dari hubungan

\(\displaystyle 1!=1\cdot0!\)

dan fakta bahwa

\(\displaystyle 1!=1\)

diperoleh

\(\displaystyle 0!=1\)

Secara kombinatorik, terdapat tepat satu cara menyusun nol objek, yaitu susunan kosong.

Apakah kata “memilih” selalu berarti kombinasi?

Tidak.

Jika objek yang dipilih mendapatkan posisi atau jabatan berbeda, urutan tetap penting.

Memilih ketua dan sekretaris adalah permutasi.

Memilih dua anggota tim tanpa jabatan adalah kombinasi.

Kapan menggunakan permutasi dengan unsur sama?

Permutasi dengan unsur sama digunakan ketika beberapa objek identik sehingga pertukarannya tidak menghasilkan susunan baru.

Rumus umumnya adalah

\(\displaystyle P=\frac{n!}{n_1!n_2!\cdots n_k!}\)

Apa itu permutasi siklis?

Permutasi siklis adalah penyusunan objek secara melingkar.

Untuk \(\displaystyle n\) objek berbeda dengan susunan yang hanya berbeda karena rotasi dianggap sama,

\(\displaystyle P=(n-1)!\)

Kapan prinsip komplementer digunakan?

Prinsip komplementer sangat berguna ketika lebih mudah menghitung hasil yang tidak diinginkan.

Misalnya untuk menghitung susunan ketika dua orang tidak berdampingan, kita dapat menghitung semua susunan lalu mengurangi susunan ketika keduanya berdampingan.

Bagaimana cara menghitung rute terpendek?

Jika dari A ke B harus bergerak \(\displaystyle p\) kali ke kanan dan \(\displaystyle q\) kali ke atas, jumlah langkah adalah

\(\displaystyle p+q\)

Jumlah rute terpendek dapat dihitung dengan

\(\displaystyle {}^{p+q}C_p\)

atau

\(\displaystyle {}^{p+q}C_q\)

Keduanya memberikan hasil yang sama.

Bagaimana cara cepat menentukan metode pencacahan?

Gunakan pertanyaan berikut secara berurutan.

Apakah terdapat beberapa alternatif? Pertimbangkan penjumlahan.

Apakah terdapat beberapa tahap? Pertimbangkan perkalian.

Apakah terdapat posisi yang harus diisi? Gunakan filling slot.

Apakah urutan penting? Pertimbangkan permutasi.

Apakah urutan tidak penting? Pertimbangkan kombinasi.

Apakah ada objek identik, pengulangan, syarat berdampingan, syarat minimal, atau larangan tertentu? Sesuaikan strategi sebelum menghitung.